首页 > > 程序设计 > C/C++ >

约瑟夫环队列+链表

2018-06-18 04:05:41来源：未知阅读 ()

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

【算法分析】

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

1、建立循环链表。

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

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

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

4、重复３，直到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 }