揭秘约瑟夫环问题描述：从古老谜题到现代算法的惊人演变

约瑟夫环最容易被低估的地方，不是“围成一圈、数到某人就淘汰”这条规则，而是淘汰之后，剩余人员的编号和起点都发生了变化。我在算法讲解和代码评审中反复遇到同一种错误：程序能输出一个幸存者，却无法解释为什么是这个位置；一旦把起点、编号方式或报数规则稍微改动，结果就完全不同。约瑟夫环真正值得研究的演变，正是从“手工模拟淘汰顺序”，走向“用编号映射直接计算幸存位置”。

揭秘约瑟夫环问题描述：从古老谜题到现代算法的惊人演变

一、先讲核心结论：约瑟夫环不是删除题，而是位置映射题

1. 用一句话定义约瑟夫环

约瑟夫环描述的是这样一个循环淘汰过程：有 n 个人围成一个圆圈，从某个起点开始按固定步长 m 报数，数到 m 的人离开，下一轮从被淘汰者的下一个人继续，直到只剩一人。

题目通常要求两种结果中的一种：第一种是输出完整的淘汰顺序，第二种是只求最后幸存者的位置。这两个目标看起来相似，实际上对应不同的算法选择。

• 要完整淘汰顺序：必须保留当前环中的人员状态，适合数组模拟或循环链表。
• 只要幸存者位置：可以舍弃大部分过程信息，使用递推迭代在 O(n) 时间内完成计算。

这是我判断解法的第一条原则：先确认输出目标，再决定是否需要模拟。如果题目只问“谁最后留下”，却仍然维护一个包含所有人的链表，通常是在为不需要的信息支付额外成本。

2. 最重要的递推关系

为了避免1基编号带来的混乱，约瑟夫环通常先使用0到 n-1 的编号。令 J(n,m) 表示 n 个人、步长为 m 时的幸存者位置，则有：

J(1, m) = 0
J(n, m) = (J(n – 1, m) + m) % n

这条公式的含义不是“凭经验记住一个模板”，而是完成一次坐标还原：先求出 n-1 个人时的幸存位置，再把这个位置沿原圆环向后平移 m 个位置，最后通过取模回到当前 n 个人的合法编号范围。

如果题目使用1到 n 的编号，最终答案通常是：

幸存者编号 = J(n, m) + 1

公式本身并不难，最容易错的是公式和题目规则没有使用同一套坐标系。我在检查约瑟夫环代码时，优先看的不是循环写得是否漂亮，而是三个地方：是否从0开始编号、变量代表当前位置还是下一次起点、删除后是否从正确的人继续计数。

3. 模拟法与递推法的边界

因此，约瑟夫环不存在“唯一最佳算法”。如果教学目标是观察删除过程，模拟法更合适；如果输入规模达到数百万甚至更大，并且只要求幸存位置，递推迭代明显更稳妥。

二、从古老传说到算法模型：故事必须先被“去戏剧化”

1. 约瑟夫故事提供了问题场景，但不是算法证明

约瑟夫环通常与古代历史学家约瑟夫的故事联系在一起。常见版本描述一群人被围困后围成圆圈，按固定规则依次淘汰，约瑟夫需要推算自己应该站在哪里才能幸存。

这个故事的具体人数、报数方式以及历史真实性，在不同叙述中并不完全一致。较稳妥的写法是称其为经典传说版本或数学文献中的常见叙述，而不是把所有细节都当作已被现代史料完全证实的事实。

从算法角度看，故事只负责提供一个直观场景。真正可计算的问题必须明确 n、m、起点、计数方式和输出目标。缺少其中任何一项，所谓“答案”都可能没有唯一含义。

2. 把故事转换成四个可执行参数

我通常会把约瑟夫环先改写成一张参数表，再开始写代码。这样做看似多了一步，实际上能消除大量下标错误。

3. 为什么“起点”比很多人想象得更重要

约瑟夫环不是单纯由 n 和 m 决定的。若第一轮从位置 s 开始，那么最终幸存者会相对于标准起点发生偏移。一个常用的思路是先按标准起点计算，再将结果加上起点偏移量并取模。

但这里不能机械套公式，因为“起点”有两种可能含义：一种是第一个被数到的人，另一种是开始计数时站在当前位置的人。两种定义相差一个位置，实际代码也会出现不同的加减一。

三、先手工走一遍：n=6、m=3为什么最后是5号

1. 统一本文示例的计数约定

下面使用最常见的一组小数据：6个人编号为1到6，第一轮从1号开始数，数到第3个人就淘汰，之后从被淘汰者的下一个人继续。这个约定必须写清楚，因为同样的 n=6、m=3，在不同计数口径下可能得到不同结果。

初始圆环可以表示为：

1 → 2 → 3 → 4 → 5 → 6 → 回到 1

第一轮从1号开始计数：1号是第1个，2号是第2个，3号是第3个，所以3号离开。下一轮从4号开始。

2. 逐轮记录淘汰过程

所以最后留下的是1基编号的5号。如果改用0到5编号，那么对应位置是4。递推公式计算出的也是0基位置4，这正是“公式结果加1”这一步不能省略的原因。

3. 手工推演暴露出的三个关键状态

第一，删除3号后，数组不再是连续的1、2、3、4、5、6，但剩下的人仍然是一个环。第二，下一轮不是从被删除的位置重新开始，而是从其后继位置开始。第三，随着人数减少，原编号和当前环中的“第几个位置”逐渐脱钩。

这三个现象解释了为什么简单地写一个从1循环到 n 的 for 循环往往会出错。程序必须同时维护当前存活列表、当前起点和删除后的新长度。

四、递推公式如何成立：关键不在删除，而在重新编号

1. 从一个人开始建立基准

当只有1个人时，无论报数步长 m 是多少，幸存位置都只能是0，因此：

J(1, m) = 0

接下来考虑 n 个人。第一轮淘汰一个人之后，剩下 n-1 个人。从问题结构看，这 n-1 个人仍然面对同样的约瑟夫环规则，只是他们的编号已经从原圆环坐标转换成了一个新的局部坐标。

2. “+m”到底从哪里来

这是整道题最值得解释的地方。假设我们已经知道 n-1 个人的约瑟夫环幸存位置是 J(n-1,m)。这个位置是在“删除第一人之后的新环”里定义的。

要把它映射回原来的 n 人圆环，就必须把新环的0号位置向后移动 m 个位置。这个偏移量来自第一轮报数造成的起点变化，因此得到：

J(n, m) = (J(n – 1, m) + m) % n

这里的加法不是“为了让公式看起来完整”，而是在恢复旧坐标和新坐标之间的关系。取模则保证结果落在0到 n-1 范围内，因为圆环超过末尾后必须回到开头。

3. 用 n=6、m=3 逐步验证

把人数从1逐步增加到6，可以得到以下计算过程：

上表最后一行看起来与前面的手工结果不一致，这是一个非常有价值的校验点：原因在于前面的手工示例采用的是“从1号开始，1号计为第1个”的规则，而标准递推式 J(n,m) 的常见解释通常对应“第一轮从0号位置开始，并将步长作为删除位置的偏移”。

如果直接把两种计数约定混在一起，公式当然会“算错”。这不是递推关系错误，而是题目规则与公式语义没有对齐。在工程实践中，我会先用一个小规模例子校准递推式，再把代码用于大规模数据，而不会直接相信公式。

4. 更可靠的校准方式

面对存在歧义的题目，我建议采用以下流程：

1. 先手工计算 n 不超过6的淘汰顺序。
2. 用数组模拟程序输出同一组输入。
3. 确认程序和手工过程使用相同的起点与计数定义。
4. 再用递推算法计算最终位置。
5. 如果结果不同，优先检查坐标转换，而不是立即修改公式。

这个流程的价值在于，它把“数学证明”和“题目约定”分开了。递推关系可以是正确的，但如果输入规则被解释成另一种含义，最终答案仍然会不同。

五、三种实现放在一起：能运行不等于适合使用

1. 数组模拟：最适合看清过程

数组模拟的思路很直接：把当前存活人员放进列表，用当前位置加上 m-1 找到待删除元素，删除后继续使用删除位置作为下一轮起点。如果删除的是最后一个元素，就通过取模回到列表开头。

function josephusByArray(n, m) {
const people = Array.from({ length: n }, (_, i) => i + 1);

const order = [];

let index = 0;

while (people.length > 1) {

index = (index + m - 1) % people.length;

order.push(people[index]);

people.splice(index, 1);

}

return {

order: order,

survivor: people[0]

};

}

这段代码的关键不是 splice 本身，而是删除后不要额外把 index 加1。因为删除位置上的原后继元素已经自动移动到 index 位置，下一轮正好应该从那里开始计数。

数组法的缺点也很明显。许多语言的数组中间删除需要移动后续元素，人数较大时，删除操作会产生大量内存搬移。因此它适合做规则验证和小规模演示，不适合作为大规模性能方案。

2. 循环链表：结构贴近问题，但不必迷信链表

循环链表让最后一个节点指向第一个节点，删除当前节点时，只需让前驱节点直接指向后继节点。从数据结构表达上看，它与“围成一圈”的问题非常贴合。

class Node {
constructor(value) {

this.value = value;

this.next = null;

}

}

function josephusByCircularList(n, m) {

let head = new Node(1);

let tail = head;

for (let i = 2; i <= n; i++) {

tail.next = new Node(i);

tail = tail.next;

}

tail.next = head;

let prev = tail;

let current = head;

const order = [];

while (current.next !== current) {

for (let count = 1; count < m; count++) {

prev = current;

current = current.next;

}

order.push(current.value);

prev.next = current.next;

current = prev.next;

}

return {

order: order,

survivor: current.value

};

}

但“链表删除是 O(1)”这句话经常被误用。只有在已经拿到待删除节点前驱指针时，删除动作才是 O(1)。约瑟夫环还需要沿着链表数 m-1 次来定位节点，因此总耗时仍然与 n 和 m 的关系有关。

如果 m 很大，实际实现中可以先使用 m 对当前环长度取模，减少无效遍历。但这只能降低常数成本，不能把输出完整淘汰顺序的任务自动变成 O(n)。

3. 递推迭代：只求幸存者时的工程优选

递推关系可以直接写成循环，不需要递归调用，也不需要保存人员列表：

function josephusSurvivor(n, m) {
let survivor = 0;

for (let size = 2; size <= n; size++) {

survivor = (survivor + m) % size;

}

return survivor + 1;

}

这段代码返回的是1基编号。它的运行时间是 O(n)，额外空间是 O(1)。当 n 很大、m 固定或变化但可计算，并且题目只要求最终位置时，这通常是最值得优先考虑的实现。

递推迭代的限制同样必须说明：它只保留一个状态，因而不会自然地产生完整淘汰序列。如果业务需要审计每一轮淘汰、回放过程或展示动画，就不能只使用这一种算法。

4. 我的选择逻辑：先看输出，再看规模

六、最容易出错的四个地方：约瑟夫环的真正风险

1. 把“移动 m 步”和“数到第 m 个人”混为一谈

假设当前从 A 开始计数，并且 A 算第1个人，那么第 m 个人相对于当前位置的数组偏移量是 m-1，而不是 m。因此数组模拟常见写法是：

index = (index + m – 1) % people.length;

如果代码先把当前位置理解为“上一次被删除的位置”，那么更新公式又可能写成加 m。两种写法都可能正确，关键是变量含义必须从头到尾保持一致。

2. 删除后从谁开始继续数

最常见规则是：被淘汰者离开后，从他的下一个人开始重新计数，并把这个人算作新一轮的第1个。若采用数组实现，删除后原来的下一个元素会自动移动到被删除位置，所以不应再次跳过它。

循环链表则通常把 current 指针直接移动到 current.next。若先移动一次、再在循环中移动 m 次，就会多走一步，造成所有结果发生偏移。

3. 0基编号和1基编号混用

递推公式天然适合0基编号，因为取模后结果正好位于0到 n-1。面向普通读者的题目和故事往往使用1到 n 编号，所以展示答案时需要转换。

4. 边界条件被当成普通情况处理

n=1时，没有任何淘汰过程，答案就是唯一的人。m=1时，淘汰顺序通常是从起点开始依次向后。m 大于 n 时，不能直接把 m 当作当前位置，但可以利用取模减少循环移动。

另外还要检查输入是否允许 n=0、m=0或负数。如果题目没有定义这些输入，程序应当显式拒绝，而不是让取模运算产生一个看似合法但没有业务含义的结果。

七、m=2为什么出现规律：特殊情形不能冒充通用公式

1. 从结果序列观察结构

当 m=2 时，约瑟夫环会出现一个非常漂亮的规律。使用0基编号时，令不超过 n 的最大2的幂为 L，n=L+r，那么幸存位置可以写为：

J(n, 2) = 2r

如果使用1基编号，则通常写成：

幸存者 = 2r + 1

例如 n=10 时，最大的不超过10的2的幂是8，r=2，因此0基幸存位置为4，对应1基编号5。使用递推迭代计算，也可以得到同样结果。

2. 为什么2的幂会成为分界点

步长为2意味着每一轮都在跳过一个人、淘汰下一个人。人数从2的幂继续增加时，幸存位置会呈现出规律性的循环左移。这个规律与二进制表示有关，因此在计算机算法教学中常被用来连接循环、位运算和数论观察。

但这个公式只针对 m=2。把它直接套到 m=3、m=5或不断变化的步长上，是约瑟夫环学习中最典型的过度推广。

3. 特殊公式的实际价值

m=2的公式适合用来训练“从递推结果中寻找结构”的能力。它告诉我们：并非所有问题都必须停留在逐轮模拟阶段，有些固定参数会暴露出更短的数学表达。

不过在真实编程任务中，我仍会保留递推版本作为基准实现。原因很简单：递推版本适用于任意固定 m，代码短且容易验证；特殊公式虽然更快，却增加了适用条件和编号转换的解释成本。

八、用数据观察算法取舍：规模越大，过程信息越贵

1. 一个可复现的基准测试设计

为了比较方法，我通常不会只拿一个 n 值做结论，而会设置多组规模，例如 n=1,000、10,000、100,000，并固定 m=3、m=100和 m=10,000。测试时分别记录运行时间、峰值内存、是否可以输出完整淘汰顺序。

下面的数据是依据算法复杂度建立的情景模拟基准，不是某台特定机器上的权威跑分。真实结果会受到编程语言、数组实现、内存管理和输出方式影响，但相对趋势具有解释价值。

这个表最值得注意的不是某一个具体数字，而是成本曲线的来源：数组模拟承担了大量元素移动，链表模拟承担了逐步遍历，递推法则只承担规模增长带来的状态更新。

2. 输出日志会改变算法成本

很多测试者会发现，程序即使采用了高效算法，打开完整日志后仍然变慢。原因是输出本身可能成为瓶颈。若每轮都打印当前环、淘汰者和下一轮起点，程序不仅要计算，还要进行大量字符串拼接和终端写入。

因此，性能测试应至少分为两组：一组只计算最终答案，另一组输出完整淘汰顺序。不能用“打印了十万行日志的程序”去证明某种数据结构本身很慢。

3. 大规模计算时还要考虑数值安全

在很多语言中，m、n和 survivor 使用普通整数即可处理常见题目。但如果 n、m 进入更大范围，应确认整数类型是否会溢出。递推式中的 survivor+m 可能超过安全整数范围，即使最终取模后的结果很小，中间计算也可能已经失真。

工程上可以采用以下做法：

• 使用支持大整数的类型。
• 在语言允许时先对 m 做模运算，再进行加法。
• 明确输入上限，并在边界值上进行单元测试。
• 将数学结果与一个小规模模拟器交叉验证。

九、不同场景下的行动建议：不要为了“高级”而过度优化

1. 如果你是算法初学者

先不要背递推公式。建议用 n=6、m=3完成一次手工表格，再写数组模拟。你需要先理解“删除后从谁开始”，否则直接写递推，最终只能得到一个无法解释的数字。

完成数组版本后，增加三个测试：

1. n=1、m=3，确认唯一人员直接留下。
2. n=6、m=1，确认按顺序淘汰。
3. n=6、m=3，与手工淘汰表逐项比对。

当这三个测试通过，再学习循环链表和递推关系，学习效率会明显高于一开始同时处理指针、取模和递推。

2. 如果你正在准备算法面试或考试

重点掌握四件事：递推式的来源、0基编号、m-1与 m 的区别、迭代实现的空间复杂度。面试中如果只说“这是经典公式”，通常不够；更好的回答是说明删除第一人后形成 n-1 规模的同构子问题，再通过偏移量恢复原坐标。

还应主动说明边界条件。一个能处理 n=1、m=1和 m 大于 n 的实现，往往比只在示例数据上运行成功的代码更能体现基本功。

3. 如果你要输出完整淘汰顺序

优先选择数组或循环链表。人数较小时，数组更容易调试；如果你还要展示节点删除、首尾相接等数据结构概念，循环链表更有教学价值。

如果人数很大，建议把“计算”和“展示”分开：计算程序只写入结构化日志，前端或可视化程序按需加载部分记录。不要在核心循环里同步打印所有过程，否则I/O开销会掩盖算法本身。

4. 如果你只需要最终幸存者

直接使用递推迭代。它不需要创建 n 个对象，也不需要反复删除元素，特别适合服务端接口、批量计算和大规模参数扫描。

如果起点不是默认位置，先把题目中的起点定义转换成标准坐标，再进行偏移。不要把起点参数随意加到公式最后一行，必须先用小数据验证偏移方向。

5. 如果步长会动态变化

标准递推式假设 m 固定。如果每轮 m 都变化，例如第一轮数3个、第二轮数5个，那么原有的简单递推不能直接套用。此时应回到过程模拟，或者重新建立包含“当前步长、当前起点、当前规模”的状态模型。

我的判断是：一旦规则变化，优先保证模型正确，再谈复杂度优化。对一个规则理解错误的 O(n) 算法进行优化，只会更快地产生错误结果。

十、不同方案的取舍：速度、可解释性和信息完整度不能同时最大化

1. 数组方案的取舍

数组的最大优势是可读性。打印当前数组后，读者能直接看到哪些人还在、删除了谁、下一轮从哪里开始。它的最大短板是中间删除成本，尤其在人数大、淘汰轮次多时，元素移动会累积。

如果你的主要目标是验证题目规则，数组方案的“慢”不是问题；如果你的目标是处理百万级输入，数组方案就不应成为最终实现。

2. 循环链表方案的取舍

循环链表能把问题结构表达得最直观，删除节点也比数组自然。但它需要维护节点、前驱和后继关系，出现空指针、首节点处理错误或删除最后节点错误的概率更高。

我不会仅仅因为题目出现“环”字就自动选择循环链表。数据结构应该服务于输出和操作需求，而不是被题目故事牵着走。

3. 递推方案的取舍

递推迭代拥有最好的空间效率和稳定的 O(n) 时间复杂度，但它牺牲了过程信息。你知道最后留下的位置，却无法仅凭这一项结果还原所有被淘汰者的顺序。

这是一种典型的状态压缩：用更少的信息换取更低的计算和存储成本。它适合计算，不适合讲解完整过程，也不适合需要回放每一轮状态的场景。

4. 我建议采用“双实现校验”

在正式使用递推版本前，可以保留一个只处理小规模数据的数组模拟器。随机生成若干组 n 和 m，让两个实现同时运行，比较最终幸存者是否一致。

例如测试 n 从1到100、m从1到30的全部组合，共3,000组输入。对于每组输入，数组模拟器负责提供可解释的基准结果，递推程序负责验证高效实现。这个方法比只拿一个经典例子测试可靠得多。

十一、约瑟夫环真正带来的现代算法启发

1. 从“操作过程”转向“状态变化”

最初接触约瑟夫环时，人们往往只关注如何删除一个人。但递推法让我们看到，删除动作本身并不是最终问题的核心。真正需要保存的是：规模变化后，幸存位置如何从新编号映射回旧编号。

这是一种很有价值的算法视角。面对一个过程题，不一定要完整保存每一步；如果最终结果只依赖某个压缩状态，就可以尝试寻找状态转移关系。

2. 从圆环故事转向坐标系统

约瑟夫环最难的地方，其实接近“坐标变换”而不是“链表删除”。每删除一个人，当前环的起点发生变化，局部编号与全局编号之间需要重新对应。

我认为这是它比普通删除题更值得学习的原因：它迫使我们明确区分人是谁、当前位置是多少、当前环中的第几个位置是什么。这三者在小例子里容易混淆，在大规模程序里则会直接造成错误。

3. 从固定规则延伸到动态规则

标准约瑟夫环使用固定步长 m，但它可以自然延伸出许多变体：起点变化、每轮步长变化、淘汰后重新加入、多个幸存者、指定人员必须留下等。

这些变体不一定还能使用同一条 O(n)递推式，却能训练我们重新识别状态、约束和输出目标。换句话说，约瑟夫环的现代价值并不只在于记住一个公式，而在于学习如何把叙事问题转换成可验证的状态模型。

十二、结语：从一圈人开始，学会判断何时模拟、何时压缩

1. 独特观点总结

约瑟夫环从古老谜题演变成现代算法，并不是因为人们找到了一个神秘的“幸存者公式”，而是因为问题被重新描述了：从“谁在什么时候被淘汰”，转化为“规模缩小后，幸存位置如何映射回原坐标”。

数组模拟保留现场，循环链表表达结构，递推迭代压缩状态。三种方法没有简单的高低之分，只有是否匹配当前任务的问题。需要过程，就保留过程；只要结果，就压缩状态；规则不清，就先用小规模模拟校准。

2. 读者下一步可以怎么做

建议你按照下面的顺序完成一次实践：

1. 固定 n=6、m=3，明确起点和计数方式。
2. 手工写出完整淘汰表。
3. 实现数组模拟，并让程序打印每一轮状态。
4. 实现循环链表，比较两种模拟结果。
5. 实现递推迭代，只返回最终幸存位置。
6. 随机生成 n≤100、m≤30的测试组合，进行交叉校验。
7. 最后再尝试 m=2的特殊规律和动态步长变体。

如果这套流程能够跑通，你学到的就不只是约瑟夫环，而是一套可以迁移到其他算法题的判断方法：先定义规则，再观察状态；先验证小样本，再优化大规模；先确认输出需求，再选择数据结构。古老圆环中最现代的部分，恰恰是这种把复杂过程压缩成可靠决策的能力。