数据结构实验报告（约瑟夫环问题）.doc

需求分析本程序要求采用数组的方法,计算并输出约瑟夫环的问题。环中总人数n和数到的数字m由用户输入,m和n为正整数。在Dos界面输出环中依次被淘汰的人的编号。测试数据输入103输出3  6  9  2  7  1  8  5  10  4概要设计抽象数据类型为实现上述程序的功能,应以整数存储用户的输入,以及计算出的结果。算法的基本思想根据题目要求,采用线性表的基本操作来实现约瑟夫环问题。定义一个数组,用于计算约瑟夫环的位置。先给数组赋值,让数组的每个值就是这个元素的编号,然后定义一个标志k,当K等于N的时候,表示到达约瑟夫环的最后位置。不停的取数组的下一个元素,如果这个元素没有被标记为0,说明这个位置还没有被排除,j加1,进入下一个循环;如果标志K等于n,说明约瑟夫环的循环到达最后一个位置,跳出While死循环。否则,把这个位置的元素设为零,标志它被排除。最后输出约瑟夫环到达的最后一个位置。程序的流程程序由三个模块组成:(1)输入模块:完成两个正整数的输入,存入变量n和m中。(2)计算模块:用循环的方式设计算法计算出依次被淘汰的序列数。(3)输出模块:屏幕上显示依次被淘汰的人的编号。三、详细设计物理数据类型题目要求输入的正整数的取值范围为正整数,在这里定义为整型即可。intm,n;算法的时空分析:时间复杂度:O(n2);空间复杂度:O(n2);四、源程序:#include<iostream>usingnamespacestd;main(){inta[100]; intn; cout<<"请输入环中总人数n:"; cin>>n; intm;cout<<"请输入所报数m:"; cin>>m; for(intj=0;j<n;j++)