CSP-J 2021 第一轮 第 38 题：Josephus问题：⑤处应填

题目

（1）（Josephus 问题）  有 $n$ 个人围成一个圈，依次标号 $0$ 至 $n - 1$。从 $0$ 号开始，依次 $0 , 1 , 0 , 1 , \dots$ 交替报数，报到 $1$ 的人会离开，直至圈中只剩下一个人。求最后剩下人的编号。

试补全模拟程序。

#include <iostream>
using namespace std;

const int MAXN = 1000000;
int F[MAXN];

int main() {
    int n;
    cin >> n;
    int i = 0, p = 0, c = 0;
    while (①) {
        if (F[i] == 0) {
            if (②) {
                F[i] = 1;
                ③;
            }
            ④;
        }
        ⑤;
    }
    int ans = -1;
    for (i = 0; i < n; i++)
        if (F[i] == 0)
            ans = i;
    cout << ans << endl;
    return 0;
}

⑤处应填（ ）

选项

• A. i++
• B. i = (i + 1) % n
• C. c++
• D. p ^=1

答案

B

题解

选 B：i = (i + 1) % n。

Josephus（约瑟夫）问题中，所有人围成一个圈。变量 i 表示当前访问的人的编号，每轮都应移动到下一个人，并在到达末尾后回到开头。

例如 n = 5，编号的变化为：

0 → 1 → 2 → 3 → 4 → 0 → ……

(i + 1) % n 正好实现这种循环。若只写 i++，访问完最后一个人后就无法回到编号 0。

另外，⑤位于 if (F[i] == 0) 外面，因此无论当前人是否已被淘汰，都会继续向后移动。