【例2-3】围圈报数

题目描述

$n$ 个人围成一圈，编号 $1\sim n$ 。从第 $1$ 个人开始顺时针报数，数到第 $m$ 的人出列，然后从下一位重新开始报数，直到所有人出列。输出出列顺序。

输入： $n$ 和 $m$ 。输出：出列顺序。数据范围： $n\leqslant 100$ 。

思路

把当前在圈内的人按顺序放进队列。每次取队头报数，未数到 $m$ 就放回队尾，数到 $m$ 就出列输出，直到队列为空。

参考代码

Python 版：

python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35#!/usr/bin/env python3
# Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
# rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
# rainboy的学习导航网站: https://idx.roj.ac.cn
# create_at: 2026-09-30 05:43
# update_at: 2026-09-30 05:43

import sys
from collections import deque


def josephus(n: int, m: int) -> list[str]:
    """模拟围圈报数，返回出列顺序。"""
    q: deque[int] = deque(range(1, n + 1))
    ans: list[str] = []
    cnt = 0
    while q:
        x = q.popleft()
        cnt += 1
        if cnt == m:
            ans.append(str(x))
            cnt = 0
        else:
            q.append(x)
    return ans


def solve() -> None:
    data = iter(map(int, sys.stdin.buffer.read().split()))
    n, m = next(data), next(data)
    print(' '.join(josephus(n, m)))


if __name__ == "__main__":
    solve()

C++ 版（同一算法）：

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-05 10:10
 * update_at: 2026-10-05 10:11
 */
#include <iostream>
#include <queue>
using namespace std;

typedef long long ll;

queue<ll> q; // 当前仍在圈内的人，队头为正在报数的人

int main() {
    ll n, m;
    cin >> n >> m;
    for (ll i = 1; i <= n; ++i) q.push(i); // 初始围圈顺序 1~n

    ll cnt = 0; // 当前已报数到第几个
    while (!q.empty()) {
        ll x = q.front();
        q.pop();
        ++cnt;
        if (cnt == m) { // 正好数到第 m 个人，出列输出
            cout << x;
            cnt = 0;
            if (!q.empty()) cout << ' ';
        } else { // 未数到 m，回到队尾等待下一轮
            q.push(x);
        }
    }
    cout << '\n';
    return 0;
}

【例2-3】围圈报数

目录

题目描述

思路

参考代码