问题：有 N个小朋友围成一圈玩报数游戏，将小朋友编号为 1∼N，从 1号开始进行1,2,3 …报数，每当一个小朋友报到M时，该小朋友出局，下一个小朋友继续从1开始报数，直到所有小朋友出局为止。请问，最后一个出局的小朋友的编号是多少？

方法一：队列

• 由于队列的特性是队头删除，队尾插入，相当于形成一个循环链表
• 首先将元素弹出
• 若此时idx == M，则 该元素不用再入队并将idx = 1
• 若idx不为3则 idx ++,且将该元素入队（插入队尾）

C++代码如下：

#include <bits/stdc++.h>

using namespace std;

int n, m;
queue<int> q;

int main()
{
    cin >> n >> m;
    for (int i = 1; i <= n; i++) q.push(i);
    int idx = 1;
    while (q.size() > 1)
    {
        auto t = q.front();
        q.pop();
        if (idx == m)
        {
            idx = 1;
            //cout << t << ' ';
            continue;
        } else
        {
            q.push(t);
            idx++;
        }
    }
    cout << q.front() << endl;
    return 0;
}

方法二：数组模拟循环链表

与法一同样的思路，每次直接将结点删除

C++代码如下：

#include <bits/stdc++.h>

using namespace std;

const int N = 1e2 + 7;

int n, m, ne[N];

int main()
{
    cin >> n >> m;
    for (int i = 1; i <= n; ++i)
        ne[i] = i + 1;
    ne[n] = 1;

    int k = 1, p = 1;
    while (n)
    {
        k++;
        if (k == m)
        {
            k = 1;
            //cout << p << ' ';
            ne[p] = ne[ne[p]];
            n--;
        }
        p = ne[p];
    }
    cout << p << endl;
    return 0;
}