《数据结构实验报告（约瑟夫环问题）》由会员分享，可在线阅读，更多相关《数据结构实验报告（约瑟夫环问题）（4页珍藏版）》请在金锄头文库上搜索。
1、一、 需求分析1 本程序要求采用数组的方法，计算并输出约瑟夫环的问题。2 环中总人数n和数到的数字m由用户输入，m和n为正整数。3 在 Dos 界面输出环中依次被淘汰的人的编号。4 测试数据输入 10 3输出 36927185104二、 概要设计 抽象数据类型 为实现上述程序的功能，应以整数存储用户的输入，以及计算出的结果。 算法的基本思想 根据题目要求，采用线性表的基本操作来实现约瑟夫环问题。定义一个数组，用于计算约瑟夫环的位置。先给数组赋值，让数组的每个值就是这个元素的编号，然后定义一个标志k，当K等于N的时候，表示到达约瑟夫环的最后位置。不停的取数组的下一个元素，如果这个元素没有被标记为
2、0，说明这个位置还没有被排除，j加1，进入下一个循环；如果标志K等于n，说明约瑟夫环的循环到达最后一个位置，跳出While死循环。否则，把这个位置的元素设为零，标志它被排除。最后输出约瑟夫环到达的最后一个位置。 程序的流程 程序由三个模块组成： （1） 输入模块：完成两个正整数的输入，存入变量 n 和m 中。 （2） 计算模块：用循环的方式设计算法计算出依次被淘汰的序列数。（3） 输出模块：屏幕上显示依次被淘汰的人的编号。三、详细设计 物理数据类型 题目要求输入的正整数的取值范围为正整数，在这里定义为整型即可。 int m，n；算法的时空分析： 时间复杂度：O（n2）； 空间复杂度：O（n2）
3、；四、源程序： #includeusing namespace std;main() int a100;int n;coutn;int m; coutm;for(int j=0;jn;j+)aj=j+1;int k=1;int i=-1;while(1)for(j=0;jm;)i=(i+1)%n;if(ai!=0)j+; if(k=n)break;coutaiendl;ai=0;k+; return 0;五、测试结果 输入 10 3 输出 3 6 9 2 7 1 8 5 10 4六、心得体会 做这次数据结构实验，不仅让我对这段时间内所学的知识有了更好的理解，而且对自己的编程能力也有所提高。发现在解决问题的过程中还有很多不会地方，在编程和写报告的过程中曾多次遇到各种各样的问题，发现自己的编程能力亟待提高。通过与同学们的交流以及自己思考，最终得到解决并顺利的完成了此次作业。
