1．本程序要求采用数组的方法，计算并输出约瑟夫环的问题。

2．环中总人数n和数到的数字m由用户输入，m和n为正整数。

3．在 Dos 界面输出环中依次被淘汰的人的编号。

4．测试数据

输入  10  3

输出  3  6  9  2  7  1  8  5  10  4

二、概要设计

  抽象数据类型 

为实现上述程序的功能，应以整数存储用户的输入，以及计算出的结果。

  算法的基本思想

     根据题目要求，采用线性表的基本操作来实现约瑟夫环问题。

定义一个数组，用于计算约瑟夫环的位置。先给数组赋值，让数组的每个值就是这个元素的编号，然后定义一个标志k，当K等于N的时候，表示到达约瑟夫环的最后位置。不停的取数组的下一个元素，如果这个元素没有被标记为0，说明这个位置还没有被排除，j加1，进入下一个循环；如果标志K等于n，说明约瑟夫环的循环到达最后一个位置，跳出While死循环。否则，把这个位置的元素设为零，标志它被排除。最后输出约瑟夫环到达的最后一个位置。

  程序的流程 

程序由三个模块组成： 

（1） 输入模块：完成两个正整数的输入，存入变量 n 和m 中。 

（2） 计算模块：用循环的方式设计算法计算出依次被淘汰的序列数。

（3） 输出模块：屏幕上显示依次被淘汰的人的编号。

三、详细设计 

物理数据类型 

题目要求输入的正整数的取值范围为正整数，在这里定义为整型即可。

     int m，n；

算法的时空分析：

       时间复杂度：O（n2）；

       空间复杂度：O（n2）；

四、源程序：

      #include

using namespace std;

main()

{

            int a[100];

    int n;

cout<<"请输入环中总人数n：";

cin>>n;

    int m;

cout<<"请输入所报数m：";

cin>>m;

for(int j=0;j        a[j]=j+1;

    int k=1;

    int i=-1;

    while(1){

     for(j=0;j        {

            i=(i+1)%n;

            if(a[i]!=0)

                j++;

         }

        if(k==n)

            break;

     cout<        a[i]=0;

        k++;

        }

    return 0;

}

五、测试结果 

  输入 10   3 

  输出  3  6  9  2  7  1  8  5  10  4

六、心得体会

  做这次数据结构实验，不仅让我对这段时间内所学的知识有了更好的理解，而且对自己的编程能力也有所提高。发现在解决问题的过程中还有很多不会地方，在编程和写报告的过程中曾多次遇到各种各样的问题，发现自己的编程能力亟待提高。通过与同学们的交流以及自己思考，最终得到解决并顺利的完成了此次作业。下载本文