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

答案

C

题解

选 C．c++。

F[i] == 0 表示第 i 个人还未出局。当满足淘汰条件②时：

``cpp F[i] = 1; // 标记这个人出局 c++; // 已出局人数加 1 ``

这里 c 用来统计已出局人数，方便循环判断是否只剩最后一人。

A、B 都是在改变当前访问的位置 i；D 是切换 p 的值，都不是此处需要的操作。