CSP-J 2021 第一轮 第 35 题：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 % 2 == 0
• B. i % 2 == 1
• C. p
• D. !p

答案

C

题解

选 C．p。

F[i] == 0 表示第 i 个人还未出局。p 用来交替记录报数状态，每遇到一个未出局的人，就通过④处的 p = !p 切换一次：

• 第一个人：p = 0，条件不成立，不出局。
• 第二个人：p = 1，条件成立，执行 F[i] = 1，出局。
• 第三个人：p = 0，不出局。
• 第四个人：p = 1，出局。

因此，②填 p，实现“每数到第二个仍在圈内的人，就让他出局”。

不能用 i % 2，因为 i 是固定编号，随着人员出局，报数的奇偶性不再等于编号的奇偶性。