约瑟夫环 队列+链表

软件设计 2017-03-28

设有n个人依次围成一圈,从第1个人开始报数,数到第m个人出列,然后从出列的下一个人开始报数,数到第m个人又出列,…,如此反复到所有的人全部出列为止。设n个人的编号分别为1,2,…,n,打印出列的顺序。

【算法分析】

       本题我们可以用数组建立标志位等方法求解,但如果用上数据结构中循环链的思想,则更贴切题意,解题效率更高。n人围成一圈,把一人看成一个结点,n人之间的关系采用链接方式,即每一结点有一个前继结点和一个后继结点,每一个结点有一个指针指向下一个结点,最后一个结点指针指向第一个结点。这就是单循环链的数据结构。当m人出列时,将m结点的前继结点指针指向m结点的后继结点指针,即把m结点驱出循环链。

1、建立循环链表。

       当用数组实现本题链式结构时,数组a[i]作为"指针"变量来使用,a[i]存放下一个结点的位置。设立指针j指向当前结点,则移动结点过程为j=a[j],当数到m时,m结点出链,则a[j]=a[a[j]]。 当直接用链来实现时,则比较直观,每个结点有两个域:一个数值域,一个指针域,当数到m时,m出链,将m结点的前继结点指针指向其后继结点;

2、设立指针,指向当前结点,设立计数器,计数数到多少人;

3、沿链移动指针,每移动一个结点,计数器值加1,当计数器值为m时,  则m结点出链,计数器值置为1。

4、重复3,直到n个结点均出链为止。

1 #include<iostream>
 2 #include<cstdio>
 3 using namespace std;
 4 int a[10000001];
 5 int tot=1;
 6 int main()
 7 {
 8     int n,m;
 9     cin>>n>>m;
10     int j=n;
11     for(int i=0;i<n;i++)
12     {
13         a[i]=i+1;
14     }
15     a[n]=1;
16     int k=1;//报数 
17     while(tot<=n)
18     {
19         while(k<m)
20         {
21             j=a[j];
22             k++;
23         }
24         //cout<<a[j]<<" ";
25         printf("%d ",a[j]);
26         a[j]=a[a[j]];
27         k=1;
28         tot++;
29     }
30     return 0;
31 }

相关推荐