主要内容 #

1. 围圈报数
2. 算法分析
3. 参考代码

1. 围圈报数 #

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

2. 算法分析 #

本题我们可以用数组建立标志位等方法求解，如果使用循环链表的思想求解，效率更高。n个人围成一圈，把每一个人看成一个节点，n个人之间的关系采用链接方式，即每一节点又一个前继节点和一个后继节点，每个节点都有一个指针指向下一节点，最后一个节点的指针指向第一个节点。这就是单循环链的数据结构。当第m个人出列时，将m节点的前继节点指针指向m节点的后继节点指针，即把m节点驱除循环链。
1. 建立循环表
当使用数组实现本题链式结构时，数组a[i]作为“指针”变量来使用，a[i]存放下一个节点的位置。设立指针j指向当前节点，则移动节点过程j=a[i]，当数到m时m节点出链，则a[j]=a[a[j]]。当直接用链来实现时，比较直观，每个节点有两个域：一个是数值域，一个指针域；当数到m时，m出链，将m节点的前继节点的指针指向其后继节点；
2. 设立指针
设立指针，指向当前节点，设立计数器，计数数到多少人；
3. 移动指针
沿着链移动指针，每移动一个节点，计数器加1，当计数器数值为m时，则m节点出链，计数器数值置为1。
4. 重复
重复步骤3直到n个节点均出链为止。

3. 参考代码 #

#include<iostream>
using namespace std;

int main(){
    int n, m;
    cin >> n >> m;
    int a[100], k = 1, p = 0, j = n;   
    for(int i = 1; i < n; ++i){
        a[i] = i + 1; //设置链表指针
    }
    a[n] = 1;  //第n人指向第1人，形成一个环
    while(p < n){ //n个人均出队为止
        while(k < m){ //报数，计数器加1
            j = a[j];
            k++;
        }
        cout << a[j] << ' '; //数到m，此人出队，计数器置为1
        p++;
        a[j] = a[a[j]];
        k = 1;
    }
    return 0;
}