软件设计 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 }