设有ｎ个人依次围成一圈，从第１个人开始报数，数到第ｍ个人出列，然后从出列的下一个人开始报数，数到第ｍ个人又出列，…，如此反复到所有的人全部出列为止。设ｎ个人的编号分别为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 }
我不去想是否能够成功，既然选择了远方，便只顾风雨兼程！
