约瑟夫问题三种C++实现：从循环链表到数学递推优化

约瑟夫问题Josephus Problem是算法学习里非常经典的一道题几乎每个学 C 数据结构的同学都会在链表章节碰到它。我第一次接触的版本是这样的N 个人围成一圈从某个位置开始报数报到 M 的人出圈接着从下一个人继续从 1 报数直到最后只剩一个人求这个人的编号。当时的课堂解法毫无悬念是“循环链表 删节点”代码写出来很长但逻辑很容易理解。后来我自己在竞赛准备阶段又碰到同一题数据范围从十几个直接变成上百万链表写法怎么跑都超时这时候才意识到约瑟夫问题的价值不在“会不会删节点”而在“同一个物理模型可以用完全不同的复杂度去解决”。这篇文章会把三种 C 实现从头到尾讲一遍自写循环链表、容器模拟、数学递推。不仅给代码还会把每一步的思路、复杂度、坑和适用场景都说清楚最后附带一些变体题的处理方向。1. 约瑟夫问题的本质和为什么总在 C 题里出现先把这个模型定义严格一点。假设有编号0, 1, ..., n-1的人按顺序围成一个环从 0 号开始报数。报数过程是从当前人开始计1下一个人计2一直数到m数到m的人出圈然后从出圈者的下一个人重新从1开始报数。重复这个过程直到环里只剩一个人。我们要求的就是最后剩下那个人在初始环中的编号。这个描述看着很简单但有以下几种常见变体只求最终幸存者编号要求按顺序输出所有人的出圈顺序编号从1开始而不是从0开始报数方向是逆时针报数起点不是 0 号。这些变体处理起来差别不小尤其是“输出完整出圈顺序”这个版本它没法直接用一步到位的最优递推公式必须老老实实模拟删除过程。这也是为什么面试或比赛里约瑟夫问题常被设计成“给一个大 N问你怎么优化”因为如果你只会写模拟数据一大就抓瞎。C 在这类问题里很占优势因为标准库提供了vector、list、queue同时又有指针和手动链表这种“硬核”写法解法可以从最底层的节点操作一直写到最抽象的公式推导非常适合拿来练复杂度思维。2. 两种主流解法物理模拟与数学递推2.1 模拟法顺着真实过程硬做模拟法的核心就是“照做”。你有一个环每次数到 m 就删一个人删完以后再接着数。这样写代码很直观尤其适合处理“要输出出圈顺序”的场合。用 C 实现模拟常见的具体写法有好几种自己定义链表节点手动维护成环结构用标准库vector配合erase用标准库list配合迭代器删除用一个queue把没被淘汰的人依次旋转到队尾这样也能模拟“围成一圈”的效果。四种写法都有人用但复杂度其实有差别。手动链表删除是 O(1) 的但遍历到第 m 个人是 O(m) 的最坏情况总复杂度是 O(n×m)vector的erase会搬移元素每次删除都要把后面的元素整体往前挪复杂度更糟糕整体可能是 O(n²)queue版本是每次把队头移到队尾相当于每轮走 m 次整体也是 O(n×m)。所以模拟法适合的数据范围一般是n 1000这种小规模。一旦n到10^5、m不等于 1模拟法基本跑不动。2.2 数学递推倒着看问题数学解法思路完全不同。我们不真的去删除人而是想办法把“n 个人时的幸存者编号”和“n-1 个人时的幸存者编号”联系起来。先做一个约定所有人编号从0开始报数从0号开始报到m的人出圈。当有 n 个人时第一轮出圈的人是谁从 0 号开始数数到第 m 个人这个人编号是(m-1) % n。他出圈后环里剩下 n-1 个人。关键点来了原来的m % n号成了“新一轮的第 0 号”因为他是被淘汰者的下一个人下一轮要从他这里报数。也就是说n 个人的圈子删掉一个人之后剩下的 n-1 个人其实又组成了一个“新的约瑟夫环”只是每个人的编号都变了。如果我们已经知道在这个新的环里幸存者的编号f(n-1)那么把它映射回原来的编号公式就是f(n) (f(n-1) m) % n边界条件是f(1) 0因为当只有一个人时剩下的那个人一定是 0 号。这个公式需要慢慢体会。很多资料直接甩公式不解释m和%n从哪里来我第一次看的时候是完全懵的。你可以拿 n5、m3 手动走一遍初始环0 1 2 3 4第一轮删除2然后从3开始重新数此时的环等价于[3, 4, 0, 1]也就是四个人的新环起点是 3如果知道四人的环里幸存者是第几个就能算回原始编号。注意这里“新的环”起点变了但公式里的%n会保证编号回绕不会越界。手动验证一下m3时f(1) 0f(2) (0 3) % 2 1f(3) (1 3) % 3 1f(4) (1 3) % 4 0f(5) (0 3) % 5 3所以 n5、m3 时0-based 的最后幸存者编号是 3也就是 1-based 里的 4 号。你手动模拟验证一下结果确实如此。3. C 实现落地三种写法逐行拆解3.1 教科书式自写循环链表先看最传统的写法。自己定义一个Node每个节点保存一个人编号和一个指向下一个节点的指针最后让尾节点指向头节点形成闭环。#include iostream struct Node { int val; Node* next; Node(int v) : val(v), next(nullptr) {} }; int josephusLinkList(int n, int m) { // 创建 n 个节点编号 1...n 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; Node* before prev; // before 永远指向 cur 的前一个节点 while (cur-next ! cur) { // 从 cur 开始数数到第 m 个人时删除 for (int count 1; count m; count) { before cur; cur cur-next; } // 删除 cur 节点 before-next cur-next; delete cur; cur before-next; } int ans cur-val; delete cur; return ans; }这个写法的优点是逻辑清晰每一步就是“走 m-1 步删当前节点”。缺点是代码量大而且要注意内存管理。new出来的节点必须delete如果中间忘了一次就会内存泄漏如果在循环里删除头节点还要小心指针悬空。另外如果你刷的是 LeetCode 这类在线 OJ有时候输入数据特别大手动链表会在new的地方直接超时——不是算法慢而是你创建上万个节点本身就花费了很大代价。3.2 用 vector erase 模拟删除用vector写模拟更贴近日常竞赛代码因为写起来短不需要自己管理内存。#include vector #include numeric int josephusVector(int n, int m) { std::vectorint people(n); std::iota(people.begin(), people.end(), 0); // 填 0...n-1 int idx 0; while (people.size() 1) { idx (idx m - 1) % people.size(); people.erase(people.begin() idx); } return people.front(); }核心就两步先算出这次要删的元素位置idx注意这里为什么是(idx m - 1) % size因为idx本身是这一轮计数的起点从它开始要数 m 个人但当前起点算“第一个人”所以再往后走 m-1 步就到了被删除的人。如果用(idx m) % size会直接跳过要删的人这是最常见的错误之一。erase的代价是 O(n)因为要把后面的元素整体搬移。所以这写法在 n 很大的时候非常慢只适合小规模数据和“输出完整删除序列”这类需要真实模拟的场景。如果你要处理“从 1 开始编号”的问题只需在初始iota时导入1...n或者在people.front()上直接加 1二者等价。3.3 数学递推一行 for 循环解决数学解法把问题从 O(n²) 或 O(n×m) 降到 O(n)代码也非常短int josephusMath(int n, int m) { int survivor 0; // f(1, m) 0 for (int i 2; i n; i) { survivor (survivor m) % i; } return survivor; // 0-based 编号 }循环从i2一直算到in每一步都在算“当前有 i 个人时幸存者的 0-based 编号”。这个算法的时间是 O(n)空间是 O(1)。n 即使达到10^7、10^8也能扛得住只要最后答案在整数范围内。如果你要求 1-based 编号直接返回survivor 1即可。很多人有个疑问为什么公式里是% i而不是% n因为在循环第 i 步时我们求的是“i 个人围成的环”的答案模数当然要是 i。等你循环到 in这时候模数才是 n。理解这个就不容易把变量写错。3.4 输出完整出圈顺序的模拟函数有些题目不满足于只给幸存者它要求按出圈顺序输出所有编号。这种情况不得不用模拟法因为你必须真实地“删”出每个人。vector版本最容易写#include vector #include numeric std::vectorint josephusOrder(int n, int m) { std::vectorint people(n); std::iota(people.begin(), people.end(), 1); // 用 1-based 编号 std::vectorint order; int pos 0; while (!people.empty()) { pos (pos m - 1) % (int)people.size(); order.push_back(people[pos]); people.erase(people.begin() pos); } return order; }注意这里people.size()是无符号整数和pos有符号整数做%时会产生类型转换风险。我在代码里显式(int)people.size()就是为避开警告。这个问题在小数据上不会出错但一旦 size 变得特别大无符号和有符号混用可能出现意想不到的行为。这种代码的缺点是复杂度较高如果 n 很大erase会导致元素搬移整体性能会明显降低。可以考虑换std::list来删除但list是双向链表定位到第 m 个人也需要 O(m) 时间整体还是 O(n×m)。因此“输出完整顺序”这个问题本身就没有 O(n) 解法的时候别指望能又快又好地把序列全部打印出来。4. 实测表现把三种写法拉到同一数据下对比光看复杂度没感觉我实际写代码测过。机器环境就是一个普通开发机C17Release 模式测的是 n100000、m7 和 n1000000、m7 两组数据。结果大致如下方案n10^5 耗时n10^6 耗时额外内存手动链表模拟数百毫秒级数秒甚至更久O(n)vector erase明显卡顿基本不可用O(n)数学递推几乎为 0 毫秒依然毫秒级O(1)上面的数值具体是多少不重要平台不同差异也很大但数量级的差距是真实存在的。尤其是 n 达到一百万时vector的erase版本会频繁搬移元素光是把一百万个 int 反复挪位置就已经非常吃力手动链表虽然删除是 O(1)但每次要遍历 m 步在 n 很大、m 也不小的情况下照样非常慢。那次测试之后我的结论很明确只问最终幸存者时永远优先数学递推问出圈顺序时先看 n 范围再决定用什么模拟方式不要硬写一个无穷跑不完的循环。5. 实践里最容易踩的坑和我的处理办法5.1 编号从 0 还是从 1 开始这是约瑟夫问题最大的坑没有之一。数学递推公式默认 0-based 编号最后的答案直接拿到 1-based 的题目里往往错一位。我的建议是所有代码一开始统一用 0-based 解决最后输出时按题目的要求加 1 或保持原样。不要在中间来回切换否则你怎么排查都查不明白。如果是自写链表节点里存的编号通常直接从 1 开始因为创建链表的习惯是存 1~n。这时候返回的就是 1-based 答案。两种方式都要会但别混着用。5.2 删除后的下一轮起点删人之后下一轮从被删者的“下一个人”开始报数不是从被删者自己开始也不是从下下个人开始。如果你用idx (idx m - 1) % size来模拟删除后不需要额外修正idx因为idx此时恰好指向被删元素的下一个位置vector 删除后后面的元素会自动补到当前位置。这其实是很精妙的一点原来的 idx 就是下一轮起点因为被删元素已经没了原地变成了原来的 next。但如果你写的是“先找到起点再走 m 步删除”那种逻辑就很容易多走一步或少走一步。我的习惯是直接在代码里测试n5, m3答案如果是 41-based说明起点没有算错如果是别的就回头检查m-1还是m1。5.3 erase 之后的迭代器失效问题如果你用std::list或std::vector要清楚地知道erase会让迭代器失效。vector中被删除元素之后的所有迭代器都会失效不只是正在使用的那个list中被删除元素的迭代器失效但其他迭代器不受影响。实战中我被这个坑过用vector写循环明明删完以后重新把iter指向了begin() idx结果后面又用了一个之前保存的迭代器直接判错。解决方案是不要在删除后保留任何旧的迭代器永远重新计算。5.4 m1 和 m 大于 n 的边界情况当 m1 时报数第一个人就出圈所以最终幸存者是最后一个人。数学公式依然正确0-basedn-11-basedn但如果你的模拟代码里用了m-1作为步长m1 时步长为 0看起来没问题但你要检查循环条件避免死循环或越界。当 m 大于 n 时也很容易出问题。比如 n5、m7第一轮删除的人其实是7%52也就是 2 号。如果你在模拟中直接让idx m再取模虽然结果对但数值很大时要小心溢出。(idx m - 1)如果 m 是2^31级别的数加上 idx 后可能超出 int 范围。这种情况最好用long long或先取模。5.5 递归写法在大 n 下的栈溢出递推公式还可以写成递归int josephusRecursive(int n, int m) { if (n 1) return 0; return (josephusRecursive(n - 1, m) m) % n; }代码短很多但你敢在 n100000 时调用这个函数吗递归深度是 n达到十万层就可能爆栈。如果你只是课堂作业n 很小递归没问题如果是线上评测n 稍微一大就可能直接栈溢出或超时。我的建议是记公式用 for 循环别写递归。递归看着优雅但在约瑟夫问题上是自找麻烦。6. 几个重要的扩展方向6.1 当 m2 时有一个 O(1) 特解如果题目限定 m 恒等于 2约瑟夫问题存在一个非常漂亮的闭合解。原理是当人数是 2 的幂时一圈删下来恰好回到起点如果不是 2 的幂先删掉多余人数剩下的问题会变成一个“从某个位置开始的 2 的幂人数问题”。结论是设p为不超过 n 的最大 2 的幂即p 2^floor(log2(n))那么幸存者的 1-based 编号为ans 2 * (n - p) 1C 实现#include algorithm int josephusM2(int n) { int p 1; while (p n) { p 1; } p 1; return 2 * (n - p) 1; }这里p就是不超过 n 的最大 2 的幂。验证一下 n5p4答案2*(5-4)13。手动模拟 m2 时幸存者确实是 3 号1-based 编号。如果你只会通用公式那 m2 时就是 O(n)会了这个特解直接 O(1) 出结果。面试时这种“条件一限制复杂度还能再降”的思路很加分它说明你不是背公式而是理解了公式背后的结构。6.2 约瑟夫问题在大数场景下的注意事项当 n 很大比如10^9级别时普通的 O(n) 数学递推也扛不住这时候往往要结合“每次跳过一大段”的分段优化技巧。核心观察是如果 n 很大但每轮的 m 固定那么第 i 步的删除过程其实是周期性的。你可以一次性算出连续多个人的出圈位置而不是一个个走。这是进阶题“约瑟夫问题 n 达到 10^9m 很小”的常见套路。写起来比较复杂但原理就是从递推公式里发现连续若干次更新都是(survivor m * k) % (i k)当survivor m*k始终小于当前人数时可以加速累加。遇到这种扩展题时建议先掌握基本公式再尝试理解加速原理。直接看复杂推导很容易劝退但一步一步跟下来其实还是循环加模运算。6.3 约瑟夫模型在真实场景中的影子很多人觉得约瑟夫问题只是纸上谈兵其实不是。我在实际项目中见过类似模型的地方就有几处第一个是环形队列的公平调度。比如一组任务轮流排队每次处理固定数量后把某个任务移出队列并重新排队这本质上就是一个约瑟夫式的过程。第二个是缓存淘汰策略里的近似实现在某些简化模型里大家围着“环”淘汰一个数据删除后从下一个位置继续也和约瑟夫问题同构。第三个是游戏开发里的回合制死亡判定按固定间隔淘汰玩家逻辑框架可以直接复用约瑟夫问题的代码思路。当然现实项目里这些场景往往不是严格“只剩一个人”的设定经常会剩多个比如“每轮淘汰前 30%”。但理解了约瑟夫问题的核心——环状结构 按步长删除 删除后重置起点——你很容易把它改造成各种业务逻辑。7. 说说我调试时的几个小技巧如果你正在刷题或者做作业建议按这个顺序来第一步不管 n 多大先用暴力模拟写出正确答案拿小数据算。第二步用数学递推再写一遍和暴力结果对拍确保公式没写错。第三步再考虑 m2 这类特解看能否进一步优化。对拍是在小范围内跑两组代码一组笨但一定正确一组聪明但需要验证。把 n 从 1 跑到 50m 从 1 跑到 50两组结果完全一致才放心。这个习惯帮我抓出过至少两次“编号 1-based 和 0-based 混用”的问题强烈建议你也这样干。还有一个小技巧是先在纸上手动算一遍 n4, m5因为 m 大于 n能帮你确认取模逻辑是否正确。很多新手遇到 m 大于 n 就直接懵其实第一步删除的是(m-1) % n号不是 m-1 本身。最后再分享一个关于 C 代码风格的体会约瑟夫问题的解法可以很花哨但真正面试或比赛时你要的是稳。能用 for 循环一行解决的就不要写链表能用标准库解决的就不要手搓内存管理能在注释里写清 0-based 和 1-based 的就不要让读代码的人去猜。把代码写得像数学公式一样干净反而是最硬的竞争力。