CSP-J 2021 第一轮 第 37 题：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

答案

D

题解

选 D．p ^= 1。

这段程序用 F[i] == 0 表示第 i 个人还没出局。④在这个判断内部，所以它的作用是：每遇到一个还没出局的人，就更新一次报数状态。

p ^= 1 表示把 p 与 1 做异或，令它在 0 和 1 之间交替：

``text p：0 → 1 → 0 → 1 → … ``

这样就能实现 Josephus 问题中“每隔一个人淘汰一个人”的报数过程。即使当前这个人刚被淘汰，也要更新报数状态。

其他选项中：

• c++ 用来统计出局人数，应放在③。
• i = (i + 1) % n 用来循环走到下一个人，应放在⑤。
• i++ 无法在到达末尾后回到开头。

因此④填 p ^= 1。