深蓝黑背景品牌封面：居中大标题「围成一圈报数出局」，副标题「最后留下的是谁：约瑟夫环」；下方原创装饰——一个圆环上均匀分布十枚小圆点，其中三枚被打叉标灰寓意出局，一枚青色高亮寓意幸存者，圆心画一枚问号；左上标注「经典题解析 · 算法」，右上标注「Day 09 · 10-17」 图 1：本文封面，一圈人里最后留下的那个，就是这道题的全部所求。

先说明属性：这是一篇经典题解析，题目出自本地历史面试资料（原题要求输入 M、N，从 1 至 N 循环报数、逢 M 出局并依次输出，写 C 程序），与任何公司的当前招聘无关。它就是著名的约瑟夫环问题，入门但不好糊弄——会背公式的人不少，被追问「为什么加 k」时能讲清楚的不多。

想象面试现场：「n 个人围成一圈，从 1 号开始报数，报到 k 的人出局，下一个人重新从 1 报。最后留下的是几号？」

核心结论一句话

两条路。模拟法：用数组当圈，每出局一人删一个位置，忠实复现过程，好写好调，时间 O(n×k)。递推公式：把 n 人环的幸存者记作 f(n)，删掉一人后剩下的还是同构的环、只是编号平移了 k 位，于是 f(n) = (f(n−1) + k) % n，从 f(1) = 0 一路推到 f(n)，时间 O(n)、空间 O(1)。面试的得分节奏是：先写模拟证明正确性，再递推出公式展示思维深度。

递推公式怎么来的，别背，推一遍。

关键观察只有一句：出局一人后，剩下的人围成的还是同一种环。n 人环里第一个出局的是第 k 个报数位置，之后从它的下一位重新报 1——这等价于一个 n−1 人环，只是所有人的编号整体平移了 k 位。设 n−1 人环的幸存者在新编号里是 f(n−1)，换回旧编号就是 (f(n−1) + k) % n。边界是 f(1) = 0（只剩一个人，编号 0 就是幸存者），注意这里用 0 起编号，最后答案加 1 转回 1 起。识别出「子问题同构」，模拟就升级成了公式——这比公式本身值钱。

写出可运行代码并实测。

下面这份实现包含模拟法、递推公式和两法对拍，用 Node.js 22.15.0 直接运行（node josephus.js）即可：

'use strict';

// 解法一：模拟法。数组当圈，每出局一人就删掉，cur 指向下一个报 1 的人。
// n 个人编号 1..n 围成一圈，从 1 开始报数，报到 k 的人出局，返回出局顺序。
function simulate(n, k) {
  const people = Array.from({ length: n }, (_, i) => i + 1);
  const order = [];
  let cur = 0; // 当前从 people[cur] 开始报 1
  while (people.length > 0) {
    cur = (cur + k - 1) % people.length; // 报 k 的人出局
    order.push(people[cur]);
    people.splice(cur, 1); // 删人后，同一位置自动成为下一个报 1 的人
  }
  return order;
}

// 解法二：递推公式。f(1)=0，f(n)=(f(n-1)+k)%n，返回 0 起编号，+1 转成 1 起。
function survivor(n, k) {
  let f = 0;
  for (let i = 2; i <= n; i++) f = (f + k) % i;
  return f + 1;
}

// 对拍：模拟法最后一名出局者必须等于递推公式的幸存者
for (let n = 1; n <= 200; n++) {
  for (let k = 1; k <= 7; k++) {
    const last = simulate(n, k).at(-1);
    if (last !== survivor(n, k)) {
      console.log(`FAIL n=${n} k=${k}: 模拟=${last} 递推=${survivor(n, k)}`);
      process.exit(1);
    }
  }
}
console.log('对拍通过：n=1..200、k=1..7 共 1400 组，两法全部一致');
console.log('n=10, k=3 出局顺序：', simulate(10, 3).join(' → '));
console.log('n=10, k=3 幸存者：', survivor(10, 3));

// 两种解法的耗时差距（n 大时模拟法的 splice 是 O(n)，总代价 O(n²)）
for (const n of [1000, 100000]) {
  let t = process.hrtime.bigint();
  simulate(n, 3);
  const simMs = Number(process.hrtime.bigint() - t) / 1e6;
  t = process.hrtime.bigint();
  survivor(n, 3);
  const recMs = Number(process.hrtime.bigint() - t) / 1e6;
  console.log(`n=${n}：模拟 ${simMs.toFixed(1)}ms，递推 ${recMs.toFixed(2)}ms`);
}

实测输出（耗时数值随机器波动，比例关系稳定）：

对拍通过：n=1..200、k=1..7 共 1400 组，两法全部一致
n=10, k=3 出局顺序： 3 → 6 → 9 → 2 → 7 → 1 → 8 → 5 → 10 → 4
n=10, k=3 幸存者： 4
n=1000：模拟 0.1ms，递推 0.00ms
n=100000：模拟 884.7ms，递推 0.29ms

1400 组对拍全部一致，两个解法的正确性互相背书。耗时对比更值得看：n 到十万时，模拟法因为每次 splice 都要搬动数组，总代价逼近 O(n²)，跑了近 900 毫秒；递推公式 0.3 毫秒不到，差出三个数量级。面试里主动提一句这个差距，比默写公式更能证明你理解复杂度。

双解法对比图：左列模拟法——用链表或环形数组忠实复现报数出局过程，每出局一人就删一个节点，时间复杂度 O(n×k)，好写好调但人数一大就慢；适合先写出让面试官看到正确性。右列递推公式——把 n 人环的答案记作 f(n)，出局一人后问题化归为 n−1 人环，幸存者在新环里的位置与旧环相差 k 位，于是 f(n) = (f(n−1) + k) mod n，从 f(1)=0 一路推到 f(n)，时间与空间都是 O(n) 还能再压成 O(1)。中部连接两列的桥：递推的本质是「删掉一人后，剩下的人围成的还是同一种环」——识别出子问题同构，模拟就升级成了公式。底部提示：工程里环形缓冲、轮询调度、clock 淘汰算法都在复用这个环 图 2：模拟与递推的对照，桥接点是「子问题同构」。

可能的追问与易错点。

「如果只要出局顺序呢？」那模拟法就是正解，递推公式只给幸存者给不了全过程。「k 比人数还多怎么办？」取模天然处理，代码里已经覆盖。易错点有三：一是 0 起与 1 起编号混用，公式内部用 0 起、出口加 1，差一错误全藏在这里；二是模拟时取下标忘记数组在变短，必须先加 k−1 再对当前长度取模；三是只会背 f(n)=(f(n−1)+k)%n，被追问「为什么是加 k」时卡壳——记住推导的那座桥：删掉一人后还是同构的环，编号平移了 k 位。工程里这个环一直在复用：环形缓冲的读写指针、轮询调度的下一个节点、缓存淘汰的 clock 算法，都是「取模绕圈」的变体。

你做约瑟夫环时用的是模拟还是公式？推导卡在哪一步了？欢迎聊聊。