约瑟夫环C++代码及实验报告

实验一约瑟夫环问题实验报告通信二班雷鹤20100820207李春阳20100820208李孟琪20100820209一、问题描述设编号为1-n的n(n0)个人按顺时针方向围成一圈．首先第1个人从1开始顺时针报数．报m的人(m为正整数)．令其出列。然后再从他的下一个人开始，重新从1顺时针报数，报m的人，再令其出列。如此下去，直到圈中所有人出列为止。求出列编号序列。二、需求分析1、需要基于线性表的基本操作来实现约瑟夫问题2、需要利用数组来实现线性表3、测试用例输入：10，3输出：36927185104三、概要设计抽象数据类型为实现上述程序的功能，应以整数存储用户的输入，以及计算出的结果。算法的基本思想利用数组来代表一个环，然后模拟报号出圈的过程，直到所有人都出圈。程序的流程程序由三个模块组成：（1）输入模块：完成两个正整数的输入，存入变量n和m中。（2）计算模块：计算这n个数的输出序列（3）输出模块：屏幕上显示这n个数的输出序列。四、详细设计程序代码：#includeiostreamusingnamespacestd;main(){intn,m,k,j;//n为总人数，m为出列编号cinnm;int*listArray=newint[n];//将n个人放在大小为n的数组中int*outArray=newint[n];//用以存放依此出列的人的编号for(inti=0;in;i++)listArray[i]=i+1;//对n个人进行编号for(i=1,j=k=0;kn;j=++j%n)//i为报数编号，初始值为1，循环访问数组元素，即数组元素循环报数{if(listArray[j]!=0){if(i==m)//报数编号和出列编号相同时{outArray[k]=listArray[j];//将该元素放置到出列数组里，并输出coutoutArray[k];k++;listArray[j]=0;//将出列元素置0i=1;//下一个元素从1开始重新报数}elsei++;//报数编号与出列编号不同时，继续报数}}cout'\n';return0;}物理数据类型队列元素及出列序列都以整型数组方式存储算法的具体步骤（1）将队列里的元素编号（2）循环访问数组元素（3）第一个元素从1开始报数，报数编号与出列编号相同时出列，并将该元素置为0（4）下一个元素重新从1开始报数，依次循环输入和输出的格式输入格式：n，m输出格式1：在字符界面上输出这n个数的输出序列输出格式2：将这n个数的输出序列写入到文件中五、测试结果其他程序代码程序1#includestdio.h#includestdlib.htypedefinttype;//结点数据域类型为整型typedefstructLNode//结点类型定义{structLNode*next;//结点的指针域typea;//结点的数据域}link;voidinitLink(link*&l){l=(link*)malloc(sizeof(link));//在内存的动态存储区申请链表长度的连续空间//初始化链表l-next=l;}voidinsert(link*&l)//在其后插入新成员{link*p;p=(link*)malloc(sizeof(link));p-next=l-next;l-next=p;}voiddestory(link*&l)//删除其后面的元素{link*t;t=l-next;l-next=l-next-next;free(t);}intmain(){intm,n;charp;while(scanf(%d%c%d,&n,&p,&m)!=EOF){link*head;link*temp;initLink(head);temp=head;for(inti=0;in;i++){insert(temp);temp-next-a=i+1;//创建链表temp=temp-next;}temp-next=NULL;temp=head;while(head-next!=NULL){for(inti=1;im;i++)//模拟约瑟夫过程{{if(temp-next==NULL)temp=head;}temp=temp-next;}if(temp-next==NULL){printf(%d,head-next-a);destory(head);}else{printf(%d,temp-next-a);destory(temp);}}printf(\n);}}程序2#includeiostreamusingnamespacestd;voidmain(){intn,m,a[100001],k,i,j;cinn;if(n100000){cout请重输;return;}cinm;for(i=1;i=n;i++){a[i]=1;}j=0;k=0;for(i=1;i=n;i++){if(a[i]==1){j=j+a[i];if(j==m){j=0;a[i]=0;k++;couti;}}if(i==n)i=0;}}七、实验心得李孟琪：该实验利用数组实现线性表，算法简便，但产生很多不必要的消耗，下一步可以尝试采用单链表，双链表实现该问题。李春阳：通过利用链表编写约瑟夫环，进一步掌握了约瑟夫环的原理，加深了对链表使用的理解雷鹤：这次实验遇到的最大问题是拘泥于基本要求中的利用数组来实现线性表，并用线性表来实现约瑟夫环问题，在尝试用链表实现后问题变得简单了些；在插入元素这一步费不少时间，头尾节点的移动关系也需要理解