约瑟夫环，光听名字可能觉得是个数学史冷知识，但它在计算机领域里出现的频率高得吓人——算法题里是常客，面试笔试里是经典款，连游戏策划设计活动抽奖逻辑时都得绕不开它。标题里那句“吃鸡”调侃其实很贴切：n个人围成一圈，从头报数，报到一个数就从圈里出去，剩下的人继续，直到最后剩一个。这不就是决赛圈机制吗？只不过吃鸡靠的是装备和天命圈，约瑟夫环靠的是位置和数学规律。
这篇文章我打算把约瑟夫环从定义到推导、从暴力模拟到数学递推、从经典场景到变体玩法一次讲透。你不需要多高深的数学底子，只要能数数、会一点基础的循环逻辑就够了。我会用吃鸡决赛圈来打比方，把每一步的问题、思路、代码和踩坑全摆出来，保证你可以直接复制代码去跑，也能理解每一行背后到底在干什么。
1. 约瑟夫环到底是什么问题
1.1 从历史故事到编程考题
约瑟夫环的故事流传很多版本，核心梗概是这样的：一群被围困的人决定站成一个圆圈，按顺序报数，报到某个数字的人就出局，直到只剩最后一个人为止。传说中有人算了半天，挑了个“绝对安全”的位置站好，最后活了下来。
这个故事听上去和吃鸡决赛圈的逻辑惊人相似——圈里人慢慢出局，你得确保自己不是被报数点到的那个人。
而到了编程领域，约瑟夫环被抽象成一个非常标准的问题：
有n个人围成一圈，从某个位置开始报数，每次报到m的人离开圈子，之后从下一个人重新报数，求最后剩下的那个人的原始编号。
这个“圈”的结构是关键，它天然对应了循环链表、环形队列、环形数组这些数据结构。再加上“不断删除节点后再继续”的过程，让解法可以从多个角度切入，所以非常受出题人欢迎。
1.2 数学定义和参数拆解
先给一个规范化的定义，方便后面推导：
- n：总人数
- m：报数的步长，也就是数到几出局
- k：从编号k开始报数（通常k=1，有的题目从0开始，后面会专门说这个坑）
- 结果：出局顺序，或者最后幸存者的编号
举个例子，n=5，m=2，从1开始报数。过程是：
- 初始圈：1 2 3 4 5
- 从1开始报数，1报1，2报2，于是2出局
- 从3重新开始报数，3报1，4报2，于是4出局
- 从5重新开始报数，5报1，1报2，于是1出局
- 从3重新开始报数，3报1，5报2，于是5出局
- 剩下3，它就是最后幸存者
这个例子会贯穿全文，你可以反复对照理解，它就像调试代码时的最小用例。
1.3 它和“决赛圈”究竟哪里像
先解释一下为什么标题会用“吃鸡”来比喻。决赛圈的核心机制是：毒圈不断收缩，圈外的人被淘汰，圈内的人继续竞争，直到只剩一队或一个人“吃到鸡”。约瑟夫环的核心机制是：报数不断循环，报到m的人被淘汰，剩下的继续报数，直到只剩一个人。
把两者对比，你会发现结构高度同构：
- 毒圈收缩 → 报到m的人出局
- 存活玩家重新组局 → 从下一个人重新报数
- 最后剩一个 → 幸存者就是“吃鸡”的那个人
所以这个比喻不是一个玩笑，它其实说明了同一个抽象模型的两种现实映射。理解这个映射对解题很有帮助——至少你不会再把“循环一圈”想成线性数组扫一遍了。
2. 最直观的解法：用循环链表和数组模拟报数
2.1 模拟思路：你把它当成一个真实的游戏去推演
想解决约瑟夫环，最自然、最容易理解的方式其实就是直接模拟整个过程。就像你在纸上画5个人，然后用笔画掉每一个出局的人，再从上一个人旁边重新开始数一样。程序只不过是把“画圈”和“数数”这两件事用代码表达出来。
这种模拟法在数据结构和算法里有一个非常贴切的原型：循环链表。每个人是一个节点，节点的next指向圈里的下一个人，出局就是删除节点。删除后从下一个节点继续，这个操作简直就像循环链表天生为约瑟夫环设计的一样。
不过我先把用数组实现的最笨但最直观的版本写出来，因为它更容易照做实验，也更适合理解过程。
def josephus_array(n, m): people = list(range(1, n + 1)) idx = 0 out_order = [] while people: # 从当前节点开始数m-1个人，因为自己算第一个 # 注意用取模处理循环 idx = (idx + m - 1) % len(people) out_order.append(people.pop(idx)) return out_order print(josephus_array(5, 2)) # 输出 [2, 4, 1, 5, 3]这代码里最容易出错的点就是idx + m - 1这个表达式，很多人一上来写idx + m，结果出局顺序整个错位。原因是：当前这个人在报数时已经算第一个位置了，所以要数到第m个人，只需要往前走m-1步。拿n=5、m=2来验证一下：初始idx=0指向1号，0+2-1=1，指向2号，2号出局，完全正确。
2.2 数组模拟的短板
上面这个版本虽然易懂，但有一个致命的性能问题：people.pop(idx)这一步，数组在删除中间某个元素时，需要把它后面的所有元素整体左移一位。也就是说，每次删除一个人，平均O(n)的时间浪费在挪位置上，整体复杂度是O(n²)。
n等于1000的时候没感觉，n等于10万、100万的时候，跑起来能给你一种代码卡死的错觉。所以数组模拟只适合做题理解思路、验证其他解法正确性的工具。
如果要改善性能，可以用循环链表避免数组的“整体搬家”，删除节点本身是O(1)，遍历m步是O(m)，总复杂度降为O(n*m)。很多文章里常用C++的list或 Python 的deque来做，但说实话，从实际工程角度看，纯链表删除在n和m都很大的时候依旧不够用。真正的杀器是下一节的数学递推。
2.3 循环链表代码参考
如果想练习一下循环链表，可以试试下面这段 C++ 写法。它和数组模拟的差异主要在删除方式，但整体逻辑是一样的。
#include <iostream> struct Node { int val; Node* next; Node(int v) : val(v), next(nullptr) {} }; int josephus_linked_list(int n, int m) { Node* head = new Node(1); Node* prev = head; for (int i = 2; i <= n; i++) { prev->next = new Node(i); prev = prev->next; } prev->next = head; // 成环 Node* cur = head; while (cur->next != cur) { for (int i = 1; i < m; i++) { prev = cur; cur = cur->next; } prev->next = cur->next; Node* del = cur; cur = cur->next; delete del; } int result = cur->val; delete cur; return result; }注意这里的循环删除操作：我们要走到第m个节点，所以从当前节点开始走m-1步，然后把这个节点摘下来。这里有个不容易察觉的细节——如果m比较小，比如m=1，那显然每次都直接删除当前节点跳过即可。这类边界条件先记住，后面我们还会在公式法里遇到它的坑。
3. 高效解法：数学递推公式的完整推导
3.1 核心洞察：淘汰一个人之后，问题被降维了
现在来看真正让约瑟夫环从“模拟题”变成“数学题”的那个关键洞察。
假设n个人围一圈，编号从0到n-1（先别急着抱怨，用0开头是有数学好处的，待会会解释）。从0号开始报数，报数报到m的那个人出局。注意，这样编号之后，第m个人在正整数1到n编号下对应的编号是 m-1（如果m≤n），因为0号对应1号。这个人出局后，从它的下一个节点开始重新报数。
也就是说，淘汰一个人之后，剩下的人仍然围成一个圈，只不过起始点变了。这个“新圈”本质上还是约瑟夫环问题，但是规模从n变成了n-1，且起点从0变成了出局者后一位。
那么问题来了：新圈里最后活着的人的“新编号”，和它在原圈里的“旧编号”之间，有没有一个简单的换算关系？
有，就是加m再取模。
3.2 递推关系是怎么来的
用一个很具体的例子来理解。
假设n=5，m=2，编号0到4。第一次出局的是1号（对应上一节的2号，这里编号差1，别慌，后面会专门讲换算），出局后剩下的是0、2、3、4。从2开始重新报数，这时候如果把这一圈重新编号成0、1、2、3，映射关系是这样的：
- 老2号 → 新0号
- 老3号 → 新1号
- 老4号 → 新2号
- 老0号 → 新3号
发现没有，映射关系恰好是：新编号加上出局者编号+1（也就是步长m），再对n取模，就变成了老编号。在这个例子里就是 新编号+2 再对5取模。
于是可以得到一个非常重要的结论：
如果我知道了n-1规模问题的幸存者新编号，那我用上面这个映射关系，就能把它转换回n规模问题的幸存者老编号。
由此可推出递推公式。
定义一个函数 f(n) 表示：n个人（编号0到n-1），从0号开始，报数到m出局的最后幸存者编号。
那么有：
- f(1) = 0，因为只有一个人的时候，活下来的就是他自己。
- f(n) = (f(n-1) + m) % n
这条公式是整个约瑟夫环高效解法的灵魂。
3.3 为什么递推公式是对的
这个递推的证明一点都不复杂，用归纳法非常好理解。
当规模为n时，第一轮出局的人是 (m-1) mod n（在0到n-1编号下，报数为1的人是0，第m个人就是m-1，如果超过了就取模）。出局之后，剩下的人形成的新圈，其实就是规模为n-1的约瑟夫环，只不过它的起始编号变了。如果我知道n-1规模的幸存者在新编号体系下的编号是 f(n-1)，那么我通过“新编号+第一轮出局者位置+1”的映射还原成老编号。
第一轮出局者是 (m-1) % n，从它的下一位开始，也就是 (m-1)%n + 1。所以映射就是：
old 编号 = (new 编号 + (m-1)%n + 1) % n
= (new 编号 + m) % n
因为 (m-1)%n + 1 在模n意义下就等于 m（这个结论可以直接展开验证，注意如果 m 恰好是 n 的倍数，原来位置是 n-1，下一个位置是0，加上new编号后取模依然等于 m%n 的偏移）。
于是结论就是 f(n) = (f(n-1) + m) % n。
这个推导过程你要是第一次看觉得绕，那就静下心在纸面上把n=5、m=2的手动过程再对比一遍。我当年第一次学的时候，自己也推了一整个草稿纸才接受它。
3.4 从0号编号到1号编号的换算
现在解释最容易被忽略也最常出错的一个点：上面所有推导都用0到n-1编号，但人类习惯用1到n编号。
这其实是计算数学里一个很经典的小技巧：用0开头，取模运算直接生效，不需要额外处理边界。
最终的换算逻辑是：
- 通过递推得到幸存者在0到n-1编号下的编号 f(n)
- 把它加上1，就得到1到n编号下的编号
举个例子：n=5，m=2。
从f(1)=0开始：
- f(2) = (0+2) % 2 = 0
- f(3) = (0+2) % 3 = 2
- f(4) = (2+2) % 4 = 0
- f(5) = (0+2) % 5 = 2
所以0到4编号的幸存者是2号，换成1到5编号就是3号。和我们第一节手动模拟的结果完全一致。
这就是数学递推的威力：只需要O(n)次循环，没有任何数组操作，也不需要模拟删除。
你要是在百度搜过约瑟夫环的文章，大概率看到过这段代码：
def josephus_formula(n, m): res = 0 for i in range(2, n + 1): res = (res + m) % i return res + 1代码就这么短。那个赋值里的res就是当前的 f(i)，一步一步从2推到n。你要是明白了前面的推导，这段代码的每个字符都能看懂。
4. 进阶变体与真实系统里的约瑟夫环
4.1 步长为2时的神奇规律
约瑟夫环有一个特别有名的特殊情况——每次报到2就出局，也就是m=2。
此时递推公式变成了 f(n) = (f(n-1) + 2) % n，你可以拿它推几组数字：
- f(1) = 0
- f(2) = 0
- f(3) = 2
- f(4) = 0
- f(5) = 2
- f(6) = 4
- f(7) = 6
- f(8) = 0
注意观察这些数，似乎有一个非常漂亮的规律：如果n恰好是2的幂，那么最后幸存者永远是0号（也就是1号玩家）。如果不是2的幂，就有一个额外的偏移。
更精确的规律是：把n写成二进制，找到它的最高位，n = 2^a + b（其中 0 ≤ b < 2^a），最后的幸存者是 2b。这个结论可以通过递推归纳很简洁地证明。
这个规律本身挺有意思，但它真正的价值在于告诉你一个问题：看上去“暴力模拟越来越慢”的场景里，往往埋着数学结构。掌握了这个结构，很多看似要跑半天的循环，实际上一个公式就能出答案。
把这条用代码表示就是：
def josephus_power_of_two(n): # m = 2 的情况 highest = 1 while highest * 2 <= n: highest *= 2 b = n - highest return 2 * b + 1 # 转成1号编号你拿n=5去算，highest=4，b=1，结果是3，完全正确。
4.2 每轮淘汰多人的扩展版本
约瑟夫环不是只有“最后剩一个人”一种玩法，还有一类常见变体是：每轮可能淘汰一批人，或者某人复活，或者找到出局顺序而不是最后一个人。这些变体往往会把递推公式打破，让你不得不回到模拟思路上。
一个最典型的变体是“约瑟夫环输出出局序列”：给出n、m，要求把所有出局人的顺序列出来。这种问题递推公式没法直接给出完整序列，因为递推公式只回答了“最后剩谁”。
遇到这种变体，建议完全用链表模拟来实现，原因很实在：递推公式算不出顺序，但模拟可以；n在合理范围内时，链表模拟的O(n*m)时间完全能接受。
下面是一段针对“输出完整出局序列”的Python实现：
def josephus_full_sequence(n, k): people = list(range(1, n + 1)) idx = 0 seq = [] while people: idx = (idx + k - 1) % len(people) seq.append(people.pop(idx)) return seq和前面那个数组模拟几乎一样。复杂度是O(n²)，但由于pop操作虽然会搬元素，但它很快。绝大多数比赛、面试场景都能过。
4.3 约瑟夫环思想在真实系统里的影子
别看约瑟夫环像是纯面试题，其实它在实际系统设计中也有存在感。最直接的是环形队列里的淘汰策略。
举个例子，某个服务器集群有n台机器，请求按顺序轮流打到每台机器上，遇到某台机器超时或故障，就要把它从轮转池里“删掉”。这个“删除后从下一位继续”的过程，和处理约瑟夫环时删除节点的思路是完全一致的。
还有抽奖系统、九宫格积分任务、直播间的“炸弹礼物”逻辑，都可能是变相约瑟夫环：每多少个人参与就抽一次奖，抽中后重新计数；或者每多少个用户点赞后触发某个事件，触发后计数清零。这种需求里不会有人去写复杂递推公式，而是一个循环链表或数组加计数器就能搞定，但这个“加计数器跳过已删除项”的思路，确实是从约瑟夫环这个经典问题里学来的。
游戏领域更是如此。所谓“大逃杀”玩法的底层逻辑，除了地图缩圈，本质上也是在反复从“存活玩家集合”里淘汰一些人，最后剩下的那个就是赢家。理解约瑟夫环，等于理解了这类规则的核心抽象。
5. 常见问题、易错点和面试避坑指南
5.1 最容易踩的坑：编号从0开始还是从1开始
我的经验是，约瑟夫环代码里90%以上的bug都出在这一个点上。
如果题目里人从1编号，你用0开始编号推公式得出结果之后忘了加1，最后答案就差1。反之，如果题目从0编号，你非要套1编号的公式，也会得到错误的起点。
实用建议是：写代码时不要想着保持人类习惯，而是按照数学公式的约定来，一律走0到n-1的编号体系，最后输出的时候再加1切换成题目要求的格式。这样写着是最不容易出错的，因为取模运算在0编号体系下不需要任何额外处理。
就连很多教科书上也有模棱两可的例子，所以你在测验里看到某个解答跟自己答案差1，先别怀疑自己算错了，大概率是编号旗标没对齐。
5.2 大n小m和大m小n的性能差异
很多人都以为递推公式是无敌的，其实不然。f(n) = (f(n-1) + m) % n这个式子需要循环n次，当n非常大的时候也是会O(n)的。如果n等于10亿，这个O(n)基本上也跑不动。
但如果m特别小（比如m=2），二进制解法直接O(log n)就出来了；而m特别大时，你会希望直接用模拟法，因为模拟法的复杂度是O(n*m)里被m主导的那个m，可是递推法不受m大小影响，始终是O(n)。
换个角度：当n巨大但m也很巨大，我们其实还可能有更优的做法，比如在递推过程中适当跳过那些不会导致更新的区间。网上有些算法博客会把这个问题叫“大数约瑟夫环”，有兴趣的可以自己查一查。
而现实业务场景中，n通常在一万以内，m也不会离谱到千万级，所以O(n)的递推公式是绝对够用的。真遇到千万级的n，那就需要考虑分段跳跃优化，或者直接用模拟链表在机器能承受的范围内凑合。
5.3 面试时如何把这道题答出层次感
如果你刷面试题刷到约瑟夫环，千万别上来就给递推公式，那样反而容易让面试官觉得你只是在背题。
建议分三步回答：
第一步，先讲朴素模拟法。用自己的话说清楚怎么用循环链表或数组模拟报数出局，不管效率如何，证明你理解了问题本身。
第二步，再主动给出数学递推法。这时候把“n规模如何转化为n-1规模”的映射关系讲清楚，让面试官看出你明白公式为什么成立，而不是只会背结论。
第三步，主动提一下m=2时的二进制解法，或者提一下如果题目要求出局顺序怎么办。这一步非常加分，因为它在展示你对知识边界的理解——你知道什么场景下递推公式不适用，什么场景下模拟法反而更合适。
最后补一个面试敲代码的时候非常实用的小贴士：面试环境里千万别急着写最终版本，而是先用 n=5、m=2 这个小案例把预期输出手动算一遍，拿这个用例去驱动你写代码和调试。我自己面试和实际写代码时都是用这个套路，能少走好多弯路。
5.4 真实场景复现时的调试技巧
假设你拿到一段约瑟夫环代码，运行结果不对，但又不知道哪里错了。
最好的办法是加打印，或者直接在纸上把 n=5、m=2、0号编号 的淘汰过程手推一遍，然后和代码输出对比。这个例子是黄金用例，因为规模小到你肉眼能跟完每一步。
我见过的其他常见报错还包括：
idx + m忘了减1，导致每次都多走一步- 取模运算没加括号，比如
idx = idx + m - 1 % len(people)会先算取模再加减，结果直接错 - 链表中在删除节点后忘了把当前指针指向被删节点的下一个位置
- 递归写法没有处理n=1的边界
只要把 n=5、m=2 这个用例跑通，这些错误基本都会原形毕露。
结尾
约瑟夫环这个题目，我一直觉得它是算法学习路上一个非常好的“分水岭”题型——暴力模拟和数学递推之间差了整整一个思维层级。我自己当年第一次接触时，也是一步步从数组模拟开始，吃尽O(n²)的苦头，才去弄懂递推公式的来龙去脉。后来在工作中写轮询逻辑、写抽奖逻辑，发现那些循环里派生的删改思维，其实都带着约瑟夫环的影子。
最后分享一个实用小技巧：当你在纸上手推约瑟夫环的时候，一定要养成用“0号编号”当主视角的习惯，这就是避免差一错误的秘诀。把所有公式推完、代码跑通之后，再统一换算成题目的编号体系，而不是在每一步都来回切换。这个小习惯，真的能在调试时省下很多时间。
如果你看完自己手动写了一遍，发现输出和预期完全一致，恭喜你，这道经典题你已经正式过关了。后面再遇到它的变体，比如输出出局序列、每轮多人出局，只要用起来这套“模拟打底、公式提速、边界谨慎”的组合思路，基本都能顺利搞定。
