实验一基于约瑟夫环问题的算法设计--计科一班钟祯穆20100810127一、问题描述设编号为1-n的n(n>0)个人按顺时针方向围成一圈．首先第1个人从1开始顺时针报数．报m的人(m为正整数)．令其出列。然后再从他的下一个人开始，重新从1顺时针报数，报m的人，再令其出列。如此下去，直到圈中所有人出列为止。求出列编号序列。二、需求分析1、需要基于线性表的基本操作来实现约瑟夫问题2、需要利用顺序表来实现线性表3、测试用例输入：10，3输出：36927185104三、概要设计抽象数据类型为实现上述程序的功能，应以整型（int）数据存储用户的输入，以及输出的结果。算法的基本思想利用数组来模拟一个环，然后模拟报号出圈的过程让数组元素循环报数，当报数编号和用户所输入的出列编号相同时，则输出此数，重复此过程，直到所有人都出列。程序由三个模块组成：输入模块：完成两个整数的输入，存入变量n和m中。计算模块：循环计算出这n个数的输出序列输出模块：按序列输出这n个数。四、详细设计物理数据类型队列元素以及出列序列皆以整型数组方式存储算法的具体步骤给输入输出序列元素编号开始循环访问数组元素从第一个元素开始报数，当报数编号与出列编号相同时即让该数输出。将下一个元素置1，即又重新从1开始报数，重复此循环过程，直至所有数输出。算法的时间复杂度程序中循环语句为单程循环，无嵌套，时间复杂度为O（n）输入和输出的格式输入格式：n，m输出格式1：在字符界面上输出这n个数的输出序列输出格式2：将这n个数的输出序列写入到文件中五、运行结果六、源代码(此程序在DevC++上运行)/*求解约瑟夫环问题*/#include<iostream>usingnamespacestd;intmain(){intm,n,k,i,j;//n表示总人数，m是出列编号cout<<"请输入总人数及出列编号"<<endl;cin>>n>>m;int*listarray=newint[n];//将这n个人存入数组int*outarray=newint[n];//存放依此出列的人的编号for(inti=0;i<n;i++)listarray[i]=i+1;//对这n个人进行编号/*开始循环报数，并输出出列元素*/for(i=1,j=k=0;k<n;j=++j%n)//i为报数编号，初始值为1，循环访问数组元素，即数组元素循环报数，k为出列元素序号{if(listarray[j]!=0){if(i==m)//若报数编号和出列编号相同{outarray[k]=listarray[j];//则将该元素放置到出列数组，并输出cout<<outarray[k]<<"";k++;listarray[j]=0;//将出列元素置0i=1;//将i置1，用以让下一个元素从1开始重新报数}elsei++;//若报数编号与出列编号不同，继续报数}}cout<<'\n';system("pause");}