约瑟夫问题

有 \(n\) 个人，编号为 \(1 \sim n\) 按顺序围成一圈，从第一个人开始报数，数到 \(m\) 的人出列，再由下一个人从 \(1\) 开始报数，数到 \(m\) 再出列，以此类推。

请依次输出出列人编号。

输入格式

两个整数分别代表 \(n,m\) 。

输出格式

\(n\) 个整数，按顺序输出每个出列人的编号。

数据范围

\(1 \leq n, m \leq 100\)。

循环链表

先生成 \(1 \sim n\) 的链表，尾巴要指向头节点，出头节点依次开始数，数到 \(m\) 出链表，知道只剩最后一个节点为止，此时 p = p->ne

循环链表代码参考

#include <iostream>

using namespace std;

const int N = int (1e7 + 10);

struct Node
{
    int v; Node* ne;
    Node(int val = 0, Node* next = nullptr) : v(val), ne(next) {}
};

Node* head, *p, *q;

int n, m, cnt;

int main(void)
{
    cin >> n >> m;
    p = head = new Node();
    for (int i = 1; i <= n; i ++)
    {
        p->ne = new Node(i);
        p = p->ne;
    }
    p->ne = head->ne;
    while (p != p->ne)
    {
        if (++cnt == m) 
        {
            cout << p->ne->v << ' ';
            p->ne = p->ne->ne;
            cnt = 0;
        }
        else
            p = p->ne;
    }
    cout << p->v << endl;

    return 0;
}

标记法

由于数据量很少，可以给出列的人打上一个标记并过滤掉即可

打标记过滤

#include <iostream>

using namespace std;
const int N = int (1e7 + 10);

int a[N];
int n, m, cnt, sum;

int main(void)
{
    cin >> n >> m;
    for (int i = 1; sum != n; i = i % n + 1) 
        if (!a[i] && ++cnt == m)
            cout << i << ' ', sum ++, cnt = 0, a[i] = 1;
    cout << endl;

    return 0;
}