约瑟夫问题学过算法的人几乎都绕不开。洛谷的P1996“约瑟夫问题”是这道经典题最标准的模板n个人围成一圈从1号开始报数报到m的人出圈然后从下一个人重新从1报数直到所有人出圈按顺序输出出圈人编号。题目本身不难尤其n、m都不大的时候怎么写都能过。但我这几年带新人刷题发现越是这样看起来“简单”的题越容易在循环边界、回卷、出圈后起点这些细节上翻车。这篇文章不打算只贴一份能AC的代码而是把这道题涉及的几种典型解法——数组模拟、链表模拟、队列模拟、数学递推——全部拆开讲一遍顺便聊聊各自的适用场景和容易踩的坑希望你看完之后不只是会做P1996而是真正把约瑟夫问题的“套路”吃透。1. 题目到底在问什么先把约瑟夫问题的逻辑捋清1.1 从洛谷P1996的原题描述说起题目原文大致这样有 n 个人编号 1 到 n按顺时针围成一圈。从第 1 个人开始报数数到第 m 个人该人出圈然后从出圈人的下一个人开始继续从 1 报数依旧数到 m 的人出圈。重复这个过程直到圈内所有人都出圈。要求按出圈顺序输出每个人的编号。这道题最核心的动作有两个一个是“周期性报数”另一个是“删除节点”。周期性体现在人始终在围成一个环报数报到末尾要绕回开头删除体现在一旦有人报到 m他就再也不能参与后续报数。这两点对应到代码里就是环状遍历和标记删除很多解法都是围绕这两个动作展开的。1.2 手跑一遍n5、m3的完整过程光看文字容易晕我们先拿小数据手推一遍。假设 n5m3初始圈内是 1、2、3、4、5从 1 开始报数报数过程1报“1”2报“2”3报“3”所以3号出圈。从4号开始重新报14报“1”5报“2”1报“3”所以1号出圈。注意这轮1号还没出圈只是绕回来了。圈里剩2、4、5从2号开始2报“1”4报“2”5报“3”5号出圈。圈里剩2、4从2号开始2报“1”4报“2”2报“3”2号出圈。最后剩4号直接出圈。最终出圈顺序是3、1、5、2、4。我建议你先自己在纸上把这个过程画一遍再对照后面的代码你会发现所有边界问题都能通过这种手工推演找到答案。等会调试代码的时候这份手推结果就是最好的“标准答案”。1.3 数据范围与考点定位P1996这类模板题给出的数据范围通常都很小一般来说 n、m 都在 100 以内甚至更小。这意味着哪怕是三重循环的暴力写法也能轻松跑完。但正是这种“怎么写都过”的题最适合拿来对比不同解法的思路。从小白视角看这道题考的是“循环引用”的模拟能力从进阶视角看它可以引出链表删除、队列旋转、数学递推、树状数组找第k个幸存者等一串知识点。所以别因为它简单就只交一份代码了事把这四种解法都亲手写一遍比刷十道同类题更有价值。2. 数组标记模拟最直观的入门写法2.1 思路与误区数组版的核心思路非常朴素开一个 bool 数组 outout[i] true 表示 i 号已经出圈false 表示还在圈内。再用一个游标 cur 从头到尾扫描配合一个计数器 cnt 记录当前已经数到了几。扫描的时候遇到 out 为 true 的人直接跳过只有 out 为 false 的人才算一次报数当 cnt 达到 m 时就把当前这个人标记为 true 并输出。这个思路最容易犯的错误有两个。一个是把已经出圈的人也数进去了导致出圈顺序错乱另一个是 cur 走到数组末尾之后忘了回卷到 1导致数组越界或者跳过前面的人。前者靠“先判断再计数”解决后者靠取模或者 if 判断解决。注意数组版报数时必须先判断 out[cur] 是否为 false再决定是否让 cnt 加一。否则已经出圈的人也会被算进报数里这是最常见的错误。2.2 C参考实现下面这份代码是 0-indexed 写法也就是说数组下标 0 对应编号 1最后输出时把下标加 1#include bits/stdc.h using namespace std; const int MAXN 105; bool out[MAXN]; int main() { int n, m; cin n m; int cur 0; // 当前报数位置0-indexed for (int i 0; i n; i) { int cnt 0; while (cnt m) { if (!out[cur]) { cnt; if (cnt m) break; } cur (cur 1) % n; // 向前走走到末尾自动回卷 } out[cur] true; printf(%d , cur 1); cur (cur 1) % n; // 从下一个人重新开始报数 } return 0; }关键点在 while 循环里只有 out[cur] 为 false 才让 cnt 自增这样已经出圈的人不会“浪费报数”。一旦 cnt 数到 mbreak 出来后当前 cur 就是要删除的人。删除之后 cur 再前进一位作为下一轮的报数起点。这里补一份 Python 版本给用 Python 刷题的同学参考n, m map(int, input().split()) out [False] * n cur 0 for _ in range(n): cnt 0 while cnt m: if not out[cur]: cnt 1 if cnt m: break cur (cur 1) % n out[cur] True print(cur 1, end ) cur (cur 1) % n2.3 为什么先学这种“笨办法”虽然数组做法的时间复杂度是 O(n*m)但它最大的优点是把题目逻辑平铺直叙地翻译成了代码一个圈就是一个数组一个人是否在场就是一个布尔值报数就是一个循环。对刚接触算法竞赛的新人来说这种“直译”能力很重要它能帮你建立代码和题意的一一对应关系之后再学链表、队列这些抽象结构才知道它们到底优化了什么。我自己带新人的时候一定会要求先把数组版写对跑通再谈优化。原因很简单数组版调试最容易每行代码都能和题目步骤对上号。万一出了 bug你甚至可以开着单步调试一行一行看 cur 和 cnt 怎么变化这是链表版很难做到的。3. 链表模拟用删除操作去贴合题目本质3.1 数组和链表在“淘汰”这一步的差别数组版虽然好懂但有一个很别扭的地方每次“淘汰”一个人只是把它标记成 true并没有真正把人从圈里拿走。后续遍历时还得反复跳过这些“尸体”如果 n、m 很大这些无效扫描会拖慢程序。链表模拟的思路就自然多了用一个单向链表把 n 个人串成一个环报到 m 的人直接把节点从链表中摘掉。删除操作只需要改指针时间复杂度 O(1)。对 P1996 这种 n≤100 的题链表在性能上没什么优势但它更贴合“出圈删除节点”这一语义。不过这里我要提醒一点竞赛里我几乎不推荐用 new/delete 动态建链表因为容易内存泄漏而且每个节点单独分配很慢。更常用的做法是“静态链表”——用一个 nxt 数组模拟 next 指针效果和动态链表一样但速度更快、更好调试。3.2 静态链表的参考实现#include bits/stdc.h using namespace std; const int MAXN 105; int nxt[MAXN]; int main() { int n, m; cin n m; for (int i 1; i n; i) nxt[i] i 1; nxt[n] 1; // 尾接到头形成环 int pre n; // pre 始终指向“待删除节点的前驱” for (int i 0; i n; i) { for (int j 1; j m; j) { pre nxt[pre]; // 走 m-1 步pre 停在待删节点的前驱 } int out nxt[pre]; // out 就是要出圈的人 printf(%d , out); nxt[pre] nxt[out]; // 跳过 out完成删除 } return 0; }解释一下核心逻辑初始时 pre 指向 n也就是 1 号节点的前驱这样报数走 m-1 步后pre 自然停在待删除节点的前一个节点上。比如 n5、m3 时第一次循环 pre 依次变成 1、2最后 out nxt[2] 3正是第一个出圈的3号。删除操作就是一行nxt[pre] nxt[out]把前驱的指针直接接到 out 的下一个节点out 就从环里剥出去了。还有一个细节当 m1 时内层 for 循环一次都不走pre 保持 nout nxt[n] 1所以第一个出圈的是1号符合“报到1就出圈”的语义。这个边界在很多写法里容易被忽略。3.3 复杂度与这个解法的优缺点静态链表模拟的时间复杂度仍然是 O(n*m)但常数比数组版小因为它不用跳越已删除节点。空间复杂度 O(n)。优点是语义清晰删除就是改一行指针而且可以直观地看到剩下的节点仍然是一条完整的环。缺点是如果 m 很大、n 很大这个写法同样会超时这时候就要考虑数学递推或数据结构优化。另外静态链表这种“用数组模拟指针”的手法本身就很值得掌握。很多竞赛题目里的“前驱后继”“环形结构”都可以用 nxt、pre 这种数组来建模代码简洁且不容易内存越界。4. 队列模拟代码最短的优雅解法4.1 队列做法的核心思想如果说链表是“人还在圈里我直接把他摘走”那么队列的做法就是“让圈自己转起来”。具体来说用队列保存当前还在圈里的所有人队首就是下一个要报数的人。每次报数时把前 m-1 个人依次从队首弹出、再塞回队尾这样他们相当于“报完了 1 到 m-1”并且安全地转到了队列末尾。此时队首的人就是第 m 个报数的直接弹出并输出就完成了一次淘汰。这个做法妙在完全不需要记录位置、不需要判断是否已出圈因为出圈的人已经被 pop 掉了队列里剩下的永远都是活人。对新手来说这是我见过最不会写错的一种解法。4.2 参考实现#include bits/stdc.h using namespace std; int main() { int n, m; cin n m; queueint q; for (int i 1; i n; i) q.push(i); while (!q.empty()) { for (int i 1; i m; i) { q.push(q.front()); // 队首的人“报完数”去队尾排队 q.pop(); } printf(%d , q.front()); q.pop(); } return 0; }以 n5、m3 为例初始队列 1 2 3 4 5。第一次内层循环弹出 1、压入队尾再弹出 2、压入队尾队列变成 3 4 5 1 2此时队首是 3弹出输出。第二轮队列是 4 5 1 2弹 4 压尾、弹 5 压尾变成 1 2 4 5队首是 1……整个过程和手推完全一致。4.3 什么时候可以无脑用队列只要是“循环报数、出圈即删除”的约瑟夫问题并且 n、m 在百万级别以内队列解法基本就是最优解之一。它代码量小逻辑直观空间 O(n)时间 O(n*m)。提示如果 m 特别大队列版里可以先执行(m - 1) % q.size()次旋转减少无效循环。while (!q.empty()) { int steps (m - 1) % (int)q.size(); while (steps--) { q.push(q.front()); q.pop(); } printf(%d , q.front()); q.pop(); }取模优化的原理很简单队列里一共 q.size() 个人转一整圈之后所有元素回到原位置报数效果不变。所以只需要关心余下的那几步这个技巧在 m 大到 10^9 时会非常有用。三种模拟解法可以简单对比一下解法时间复杂度空间复杂度代码量主要易错点数组标记O(n*m)O(n)中等跳过已出圈的人、末尾回卷静态链表O(n*m)O(n)较短pre 与 nxt 指针关系队列模拟O(n*m)O(n)最短m 大时忘记取模优化如果是比赛里快速AC我一般首选队列 取模优化代码短、逻辑清楚不容易出边界错。5. 数学递推O(n)求出最后幸存者5.1 递推公式与推导前面几种解法都在模拟过程但约瑟夫问题其实藏着一个非常漂亮的数学结构只求最后幸存者时不需要模拟每一轮直接 O(n) 递推就能算出来。先约定编号从 0 开始。设 f[i] 表示 i 个人围成一圈、从 0 号开始报数时最后幸存者的编号。i1 时显然 f[1] 0。当有 i 个人时第一轮报到 m 的人会出圈。因为 0 号先报 1所以出圈的是第 m 个人它的编号是 (m-1) % i我们记这个编号为 k。出圈之后剩下的 i-1 个人从 k1 开始重新报数。如果我们把 k1 映射成 0、k2 映射成 1、……那么这 i-1 个人就完全等价于一个全新的 i-1 人约瑟夫问题它的幸存者编号就是 f[i-1]。最后把这个幸存者从“新编号”映射回“老编号”只需要加上 k1 再对 i 取模f[i] (f[i-1] k 1) % i (f[i-1] m) % i这里解释一下为什么括号里是 m因为 k1 (m-1)%i 1与 f[i-1] 相加后对 i 取模等价于整体加 m。这一步推导我建议你自己推一遍理解之后就不会忘。5.2 实现代码#include bits/stdc.h using namespace std; int main() { int n, m; cin n m; int s 0; // f[1] 0 for (int i 2; i n; i) { s (s m) % i; } printf(%d\n, s 1); // 转回 1-indexed return 0; }测试一下 n5、m3s0i2 时 s(03)%21i3 时 s(13)%31i4 时 s(13)%40i5 时 s(03)%53最终输出 s14。对应前面手推的结果最后剩下的是4号完全正确。5.3 这道题为什么不能直接套递推看到这里你可能有个疑问洛谷 P1996 要求输出完整的出圈顺序不是一个幸存者编号那这个递推还有什么用直接拿这个递推没法输出完整顺序但有两个重要的应用场景。第一当题目改成“只问最后剩下谁”时O(n) 解法是碾压所有模拟法的。比如 n10^7、m10^9任何模拟都会超时只有这个递推能在一秒内跑完。第二如果你想用数学方法求完整顺序可以把递推公式包装成“删除第几个幸存者”的定位问题配合线段树、树状数组这类数据结构在 O(n log n) 内解决。这就引出了下面这个进阶解法。5.4 进阶树状数组二分求完整出圈顺序思路是这样用树状数组维护“当前还未出圈的人”每个位置初始为 1出圈后置 0。再用一个变量 pos 表示“当前报数起点在整个剩余序列中的下标”0-indexed。每一轮要出圈的人就是当前剩余序列中下标为 (pos m - 1) % remain 的人。由于树状数组存储的是前缀和我们要找的就是“前缀和第一次达到该下标1”的位置。找这个位置可以用树状数组的经典“二分定位”操作通常叫 kth。整体的伪代码框架如下#include bits/stdc.h using namespace std; const int MAXN 100005; int n, m; int bit[MAXN]; void add(int x, int v) { for (; x n; x x -x) bit[x] v; } int sum(int x) { int s 0; for (; x 0; x - x -x) s bit[x]; return s; } int kth(int k) { int idx 0; int step 1; while (step 1 n) step 1; for (; step; step 1) { int nxt idx step; if (nxt n bit[nxt] k) { idx nxt; k - bit[nxt]; } } return idx 1; } int main() { cin n m; for (int i 1; i n; i) add(i, 1); int remain n; int pos 0; while (remain) { pos (pos m - 1) % remain; int out kth(pos 1); printf(%d , out); add(out, -1); remain--; if (remain) pos % remain; } return 0; }这段代码的核心难点在 pos 的理解上。你可以把它想象成“指针”在剩余序列上的位置删除一个人后他后面的元素会整体前移一位所以如果删除的是序列中最后一个元素下一个起点会自然回到序列开头也就是 pos 要对新的 remain 取模。这里我建议你拿 n5、m3 手动走一遍体会 pos 的变化过程比听我讲十遍都管用。这种写法在 n 达到 10^5、10^6m 也很大时依然能跑是竞赛里处理大规模约瑟夫问题的常用手段。如果 n 再往上走树状数组的空间也可能吃紧届时要考虑更专门的数学优化不过那就超出 P1996 的讨论范围了。6. 常见问题与调试实录6.1 懵圈率最高的三个坑第一个坑把已出圈的人算进报数。数组版里最常见报数循环没有判断 out[cur]导致明明已经出圈的人还在“报数”出圈顺序全乱。解决办法就是计数前先判断是否在场。第二个坑回卷时机不对。用 0-indexed 时cur (cur 1) % n写一次就够了问题往往出在“出圈后还要再往前走一步”这个动作上。很多人会在循环里外各写一次 cur1结果第二轮直接跳过了人。我建议把“找第 m 个人”和“确定下一轮起点”看成两件事前者在 while 循环里完成后者在出圈后用一句cur (cur 1) % n单独完成。第三个坑m1 这类边界。很多人测试的时候只测 m1 的情况导致 m1 时数组版输出错链表版反而对。m1 时应该从1号开始一个接一个出圈即输出 1 2 3 ... n。队列版里 m1 时内层循环一次不转直接弹出队首天然正确。6.2 调试与对拍方法对于这种模拟题最推荐的调试方法就是“小数据手工推演 代码逐步对照”。把 n5、m3 的手推出圈顺序写在注释里然后在代码里加一行输出当前 cur 或队列状态的调试信息跑一遍看看和手推过程是否一致。更工程化的方法是写对拍。用一份你觉得绝对正确的暴力代码比如队列版当“标准答案”随机生成 n 和 m跑 1000 组数据比较输出是否一致。对拍脚本很简单生成随机数据、分别跑两个程序、diff 结果一旦不一致就把那组数据拿出来单步调试。这个方法我从入门用到现在几乎所有逻辑题的小 bug 都是这么抓出来的。6.3 特殊数据自测清单我整理了一份小小的自测清单每次写完约瑟夫相关代码都会跑一遍数据期望结果n1, m11n5, m11 2 3 4 5n5, m33 1 5 2 4n2, m31 2n7, m44 1 6 5 7 3 2最后一行我手推验证过初始1到7m4第一轮数到4号出圈之后从5号重新开始后续出圈顺序为1、6、5、7、3最后剩2。你写完任何一版代码都可以拿这张表快速自测全对的话基本就稳了。7. 变式与延伸从这道题出发还能学什么7.1 常见变式约瑟夫问题的变式非常多我列几个常见方向只求最后幸存者编号直接用 5.2 的递推。从第 k 个人开始报数而不是第 1 个模拟法只需要把 cur 初始值改成 k递推法需要加偏移。报数方向改为逆时针把环的方向反过来代码里把cur (cur 1) % n改成cur (cur - 1 n) % n。每个人出圈后 m 会变化比如第 i 轮报 m_i 个出圈这时递推公式失效一般只能模拟或者用有序集合/树状数组优化。求某个人是第几个出圈的可以在模拟过程中记录 order[编号] 出圈次序。不管哪种变式底层的思考方式都一样搞清楚“报数起点”如何更新、“删除位置”如何计算。这两个问题想明白了剩下的就是套数据结构。7.2 大数据场景当 n 是 10^5 以上m 也很大时O(n*m) 的模拟完全跑不动。此时如果只要幸存者用递推 O(n)如果要完整顺序用树状数组/线段树 O(n log n)。我之前遇到过一道加强版题目n10^6、m10^9队列模拟直接跑到怀疑人生换成树状数组后几百毫秒出结果。这也是为什么我不建议只会一种写法的原因——模板题虽然简单但它后面缀着的“加强版”往往就是区分选手的分水岭。7.3 编程竞赛里的“一题串讲”站在学习角度P1996 是一道非常适合“一题多解”的题。数组是入门链表是理解删除队列是锻炼抽象思维递推是数学建模树状数组是数据结构进阶。一道题把数据结构课里最基础的内容几乎串了个遍这也是我为什么愿意花这么长篇幅写它。如果你正处在学习算法的初级阶段我强烈建议你把这几种做法都写一遍跑同样的测试数据感受一下不同解法的代码量差距和思路差异。最后分享一点我自己的习惯。每次做约瑟夫问题我不管数据范围多大都会先在草稿纸上把 n5、m3 整个流程手推一遍再把这份手推结果当作“测试用例”去验证代码。这看起来机械但恰恰是这类模拟题最稳的提防手段——很多 bug 不是逻辑没想到而是手指比脑子快。至于解法选择我的原则很简单n 小就用队列模拟代码短又不容易错n 大只想求幸存者就用递推n 大还要完整顺序就用树状数组。把这套组合拳打熟约瑟夫问题再怎么出变体你心里都有底。