中 · 模拟
约瑟夫环
规则残酷地简单：从当前的人开始数 k 个还活着的人，第 k 个离圈，然后从他身后的人重新数。没有公式、没有机灵 —— 只有忠实的记账，而这正是计算机的用武之地。
一句话答案维护 <code>alive[n]</code> 和一个游标。沿圈走、只数活人；数到第 k 个，打印、标记死亡，并从下一个位置重新数（<code>cur = (cur + 1) % n</code>）。
题目
输入: 一行两个整数 n 和 k（1 ≤ n ≤ 100，1 ≤ k ≤ 100）。人员编号 1..n；从 1 号开始报数，每数到第 k 个存活者就出列，如此反复直到无人剩余。
输出: 出列顺序：n 个数字、单个空格隔开（最后一个是幸存者）。
样例:
| 输入 | 输出 |
|---|---|
5 3 | 3 1 5 2 4 |
1 7 | 1 |
n = 5、k = 3 时：数 1、2、3 —— 3 号出列。从 4 重新数：4、5、1 —— 1 号出列。从 2 数：2、4、5 —— 5 号出列。再从 2 数（此时只剩 2、4）：2、4、2 —— 2 号出列；幸存者是 4 号。
你的解答
「运行我的输入」用的自定义输入
判题在浏览器本地运行。死循环会在 3 秒后被自动中断 —— 但还是确保每个循环都有出口。代码随打随存。
卡住了？提示
提示 1 — 圆圈不过是取模
第 i 个人住在下标 i−1，下标 n−1 的下一个位置是 0：cur = (cur + 1) % n。这一个表达式就是整个圆圈。你今后遇到的所有环形问题 —— 环形缓冲区、轮询调度 —— 都是这件衣服里的同一个取模。
提示 2 — 只数活人
内层走圈时，死人的位置要跳过且不耗次数：if (alive[cur]) { count++; ... } 然后前进。如果死人也耗次数，出列就会重复，第三轮起整个顺序自我毁灭 —— 判题样例立刻就能抓住。
提示 3 — 从倒下者的下一位重新数
出列 p 之后，下一次报数从 p 身后的人开始 —— 游标正指着 p，所以进入下一轮前再来一次 cur = (cur + 1) % n。「从 p 重新数」在 p 的邻居都活着时碰巧同答案……之后悄悄分岔。先手推样例，再谈相信。
题解（先自己试试！）
#include <iostream>
using namespace std;
bool alive[105];
int main() {
int n, k;
cin >> n >> k;
for (int i = 0; i < n; i++) alive[i] = true;
int cur = 0;
for (int round = 0; round < n; round++) {
int count = 0;
while (true) {
if (alive[cur]) {
count++;
if (count == k) break;
}
cur = (cur + 1) % n;
}
alive[cur] = false;
cout << cur + 1;
if (round < n - 1) cout << " ";
cur = (cur + 1) % n;
}
cout << endl;
return 0;
}撑起整道题的是两个记账思想：布尔数组作为「谁还在」的唯一事实，取模作为「圆圈」。两者都是老黄牛 —— 同一个 alive[] 模式在 素数计数 里驱动筛法标记，同一个取模驱动环形缓冲区。当一个故事可以逐步重演时，模拟不是幼稚的选择，而是可验证的选择。
深度解析
为什么这样做对
这个规模不需要闭式公式 —— 规则简单到可以忠实重演。alive[] 布尔数组是「谁还在」的唯一事实;圆圈就是 (cur + 1) % n;报数只数活人。模拟把谜题变成记账,而记账不会和判题器争辩。
代价
最坏 O(n × k)(每轮最多走 k 步),空间 O(n) —— n = 100、k = 100 时是一万步,毫无压力。
常见错法
- 把死人的位置也算进报数:出列开始重复,顺序自我毁灭 —— 样例里第三次出列就能看见。
- 从刚出列的人重新报数,而不是从他身后的人:前一 two 轮碰巧正确,之后悄悄分岔。
- k 的差一:「数到第 k 个」包含起报者(k = 1 时每轮出列的都是当前起报者,得到 1 2 … n)。
记住这两句
- 圆圈 = 数组 + (cur + 1) % n,仅此而已。
- 规则简单而公式够不着时,模拟是诚实(且可验证)的工具。
🐞 这段是错的 —— 点开,亲手让它挂一次
死人也照数 —— 出列开始重复,顺序自我毁灭
#include <iostream>
using namespace std;
bool alive[105];
int main() {
int n, k;
cin >> n >> k;
for (int i = 0; i < n; i++) alive[i] = true;
int cur = 0;
for (int round = 0; round < n; round++) {
for (int step = 0; step < k; step++) { // bug: no alive check
cur = (cur + 1) % n;
}
cur = (cur - 1 + n) % n; // compensate — still wrong
alive[cur] = false;
cout << cur + 1;
if (round < n - 1) cout << " ";
cur = (cur + 1) % n;
}
cout << endl;
return 0;
}