实验1约瑟夫环问题1．需求分析(1) 输入的形式和输入值的范围：每一次输入的值为两个正整数，中间用逗号隔开若分别设为n,m,贝V输入格式为：“n,m”不对非法输入做处理，即假设输入都是合法的2) 输出的形式：输出格式1：在字符界面上输出这n个数的输出序列输出格式2：将这n个数的输出序列写入到文件中(3) 程序所能达到的功能：对于输入的约瑟夫环长度n和间隔m,输出约瑟夫环的出列顺序4) 测试数据：包括正确的输入及其输出结果和含有错误的输入及其输出结果正确：输入：10,3输出：36927185104输入：41,3输出：3691215182124273033363915101419232832374171320263440817293811252224351631错误：输入：103输出：687134295102．概要设计(1) 抽象数据类型的定义：为实现上述程序的功能,可以用整数存储用户的输入并将用户输入的值存储于线性表中线性表ADT定义如下：ADTlist数据对象：整形数据关系：线性关系卩vai,ai+1>(0WaVn)基本操作：boolremove(int&elem)/移除一个元素，被移除的元素赋给elem〃如果操作成功，返回true，否则返回falseboolisEmpty()//判断数组的元素是否清空，空返回true，否则返回falseboolsetPos(intplace)〃设置当前元素的位置,设置成功返回true,否则返回falseintgetLength()〃获取数组的实际长度2）算法的基本思想：约瑟夫环问题中的数据是人所在的位置，而这种数据是存在“第一元素、最后元素”，并且存在“唯一的前驱和后继的”，符合线性表的特点。
由于需要模拟约瑟夫环的出列问题，可以采用顺序表来实现线性表，完成出列顺序的输出核心算法主要分为两步：1、确定需要删除的位置，2、设置并删除该位置已知报数间隔m,我们可以把当前位置加上m获得需要删除的位置，如果获得的位置超过顺序表中实际元素的总长度，则可以通过减去数组的实际长度来修正（即模拟环状计数）然后把顺序表中的当前指向位置设置为该位置，继而删掉该位置反复进行上述确定位置和删除位置的操作，直到顺序表为空3）主程序的流程：程序由三个模块组成：（1）输入模块：无提示语句，直接输入总人数n和报数次数m,中间用逗号隔开2）处理模块：将元素储存于顺序表中在主函数中根据报数间隔确定需要删除的元素的位置，在顺序表中设置该位置并删除该位置，同时输出该位置的值反复设置并删除直到表空3）输出模块：分别在DOS下和文件中，按移除元素的顺序依次显示其位置4）各程序模块之间的层次（调用）关系：主函数会按设计的方法调用顺序表中“获取实际长度”、“设置需要删除元素的位置”、“移除该位置元素”和“判断是否为空表”四种方法方法，使元素依次出列，并正确结束程序3．详细设计（1）实现概要设计中定义的所有数据类型（物理数据结构）：1、用整形存储用户输入的整数。
2、用顺序表实现线性表：classAList{private:int*listArray;〃指向数组的指针intrealSize;//数组中含有元素的实际长度intfence;//指向当前元素下标public:AList（ints）//构造函数，初始化数组{listArray=newint[s];for（inti=0;i=0&&place<=realSize){fence=place;returntrue;}returnfalse;}intgetLength()〃获取数组长度{returnrealSize;}};#(2) 算法的具体步骤：在主函数中调用上述模块的方法：ofstreamfout;//文件流fout.open("C:\\Josephus.txt");〃设置文件路径intn,m,elem,point=0;scanf("%d,%d",&n,&m);〃获得用户输入AListalist(n);//创建顺序表对象while(!alist.isEmpty())〃如果顺序表不为空，继续删除{m=m%alist.getLength();〃调整计数的长度if(m==0)m=alist.getLength();if(point+m-1
但是用顺序表实现时，每次其移除的方法是时间复杂度为®(k)的(k与实际长度有关)，所以处理部分总的结果是(匕凹)的，化简后时间复杂度仍然为®(n2)2综上，该算法的时间代价为®(n2)PS：如果是用循环查找，在n次定位中每次都使用了m次的循环，至少是&(n*m)，然后再用顺序表的移除方法，总的复杂度应该是®(m*n2)的)事实上要用线性表来完成这道题，其复杂度最好也是@(n2)的，毕竟对于n个数据，每个都要进行时间复杂度为®(n)的删除工作欲到达©(n)的效率除非不用线性表来实现4)画出函数的调用关系图:输入人数n,报数间隔m,创建顺序表对象确定需要删除的位置Remove()〃调用删除方法DOS和文本输出显示结果主程序！isEmpty()//顺序表不为空(5) 输入和输出的格式：输入：10,3输出：36927185104(文本中的输出)：3692718510444、测试结果41,35101419232832374171320263440□6912151821242736333639817293811252224351631请按任意键继续-#。