约瑟夫环光听名字可能觉得是个数学史冷知识但它在计算机领域里出现的频率高得吓人——算法题里是常客面试笔试里是经典款连游戏策划设计活动抽奖逻辑时都得绕不开它。标题里那句“吃鸡”调侃其实很贴切n个人围成一圈从头报数报到一个数就从圈里出去剩下的人继续直到最后剩一个。这不就是决赛圈机制吗只不过吃鸡靠的是装备和天命圈约瑟夫环靠的是位置和数学规律。这篇文章我打算把约瑟夫环从定义到推导、从暴力模拟到数学递推、从经典场景到变体玩法一次讲透。你不需要多高深的数学底子只要能数数、会一点基础的循环逻辑就够了。我会用吃鸡决赛圈来打比方把每一步的问题、思路、代码和踩坑全摆出来保证你可以直接复制代码去跑也能理解每一行背后到底在干什么。1. 约瑟夫环到底是什么问题1.1 从历史故事到编程考题约瑟夫环的故事流传很多版本核心梗概是这样的一群被围困的人决定站成一个圆圈按顺序报数报到某个数字的人就出局直到只剩最后一个人为止。传说中有人算了半天挑了个“绝对安全”的位置站好最后活了下来。这个故事听上去和吃鸡决赛圈的逻辑惊人相似——圈里人慢慢出局你得确保自己不是被报数点到的那个人。而到了编程领域约瑟夫环被抽象成一个非常标准的问题有n个人围成一圈从某个位置开始报数每次报到m的人离开圈子之后从下一个人重新报数求最后剩下的那个人的原始编号。这个“圈”的结构是关键它天然对应了循环链表、环形队列、环形数组这些数据结构。再加上“不断删除节点后再继续”的过程让解法可以从多个角度切入所以非常受出题人欢迎。1.2 数学定义和参数拆解先给一个规范化的定义方便后面推导n总人数m报数的步长也就是数到几出局k从编号k开始报数通常k1有的题目从0开始后面会专门说这个坑结果出局顺序或者最后幸存者的编号举个例子n5m2从1开始报数。过程是初始圈1 2 3 4 5从1开始报数1报12报2于是2出局从3重新开始报数3报14报2于是4出局从5重新开始报数5报11报2于是1出局从3重新开始报数3报15报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步。拿n5、m2来验证一下初始idx0指向1号02-11指向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比较小比如m1那显然每次都直接删除当前节点跳过即可。这类边界条件先记住后面我们还会在公式法里遇到它的坑。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 递推关系是怎么来的用一个很具体的例子来理解。假设n5m2编号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。这个推导过程你要是第一次看觉得绕那就静下心在纸面上把n5、m2的手动过程再对比一遍。我当年第一次学的时候自己也推了一整个草稿纸才接受它。3.4 从0号编号到1号编号的换算现在解释最容易被忽略也最常出错的一个点上面所有推导都用0到n-1编号但人类习惯用1到n编号。这其实是计算数学里一个很经典的小技巧用0开头取模运算直接生效不需要额外处理边界。最终的换算逻辑是通过递推得到幸存者在0到n-1编号下的编号 f(n)把它加上1就得到1到n编号下的编号举个例子n5m2。从f(1)0开始f(2) (02) % 2 0f(3) (02) % 3 2f(4) (22) % 4 0f(5) (02) % 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就出局也就是m2。此时递推公式变成了 f(n) (f(n-1) 2) % n你可以拿它推几组数字f(1) 0f(2) 0f(3) 2f(4) 0f(5) 2f(6) 4f(7) 6f(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号编号你拿n5去算highest4b1结果是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特别小比如m2二进制解法直接O(log n)就出来了而m特别大时你会希望直接用模拟法因为模拟法的复杂度是O(n*m)里被m主导的那个m可是递推法不受m大小影响始终是O(n)。换个角度当n巨大但m也很巨大我们其实还可能有更优的做法比如在递推过程中适当跳过那些不会导致更新的区间。网上有些算法博客会把这个问题叫“大数约瑟夫环”有兴趣的可以自己查一查。而现实业务场景中n通常在一万以内m也不会离谱到千万级所以O(n)的递推公式是绝对够用的。真遇到千万级的n那就需要考虑分段跳跃优化或者直接用模拟链表在机器能承受的范围内凑合。5.3 面试时如何把这道题答出层次感如果你刷面试题刷到约瑟夫环千万别上来就给递推公式那样反而容易让面试官觉得你只是在背题。建议分三步回答第一步先讲朴素模拟法。用自己的话说清楚怎么用循环链表或数组模拟报数出局不管效率如何证明你理解了问题本身。第二步再主动给出数学递推法。这时候把“n规模如何转化为n-1规模”的映射关系讲清楚让面试官看出你明白公式为什么成立而不是只会背结论。第三步主动提一下m2时的二进制解法或者提一下如果题目要求出局顺序怎么办。这一步非常加分因为它在展示你对知识边界的理解——你知道什么场景下递推公式不适用什么场景下模拟法反而更合适。最后补一个面试敲代码的时候非常实用的小贴士面试环境里千万别急着写最终版本而是先用 n5、m2 这个小案例把预期输出手动算一遍拿这个用例去驱动你写代码和调试。我自己面试和实际写代码时都是用这个套路能少走好多弯路。5.4 真实场景复现时的调试技巧假设你拿到一段约瑟夫环代码运行结果不对但又不知道哪里错了。最好的办法是加打印或者直接在纸上把 n5、m2、0号编号 的淘汰过程手推一遍然后和代码输出对比。这个例子是黄金用例因为规模小到你肉眼能跟完每一步。我见过的其他常见报错还包括idx m忘了减1导致每次都多走一步取模运算没加括号比如idx idx m - 1 % len(people)会先算取模再加减结果直接错链表中在删除节点后忘了把当前指针指向被删节点的下一个位置递归写法没有处理n1的边界只要把 n5、m2 这个用例跑通这些错误基本都会原形毕露。结尾约瑟夫环这个题目我一直觉得它是算法学习路上一个非常好的“分水岭”题型——暴力模拟和数学递推之间差了整整一个思维层级。我自己当年第一次接触时也是一步步从数组模拟开始吃尽O(n²)的苦头才去弄懂递推公式的来龙去脉。后来在工作中写轮询逻辑、写抽奖逻辑发现那些循环里派生的删改思维其实都带着约瑟夫环的影子。最后分享一个实用小技巧当你在纸上手推约瑟夫环的时候一定要养成用“0号编号”当主视角的习惯这就是避免差一错误的秘诀。把所有公式推完、代码跑通之后再统一换算成题目的编号体系而不是在每一步都来回切换。这个小习惯真的能在调试时省下很多时间。如果你看完自己手动写了一遍发现输出和预期完全一致恭喜你这道经典题你已经正式过关了。后面再遇到它的变体比如输出出局序列、每轮多人出局只要用起来这套“模拟打底、公式提速、边界谨慎”的组合思路基本都能顺利搞定。