CSP-J 2021 第一轮 第 34 题：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 < n
• B. c < n
• C. i < n - 1
• D. c < n - 1

答案

D

题解

选 D．c < n - 1。

这段程序中，i 表示当前检查的人的编号，c 表示已经离开的人数。共有 n 人，要剩下 1 人，就需要让 n - 1 人离开，所以循环条件是：

``cpp while (c < n - 1) ``

可以结合循环内部理解：

``cpp if (F[i] == 0) { // 当前这个人还在圈中 if (p == 1) { // 报到 1，离开 F[i] = 1; c++; // 离开人数加 1 } p = 1 - p; // 0、1 交替报数 } i = (i + 1) % n; // 沿着圈走到下一个位置 ``

i 会在 0 到 n - 1 之间反复循环，因此不能用它判断是否只剩一个人；应根据离开人数 c 判断。