约瑟夫问题四种解法详解：从数组模拟到数学递推

约瑟夫问题，学过算法的人几乎都绕不开。洛谷的P1996“约瑟夫问题”是这道经典题最标准的模板：n个人围成一圈，从1号开始报数，报到m的人出圈，然后从下一个人重新从1报数，直到所有人出圈，按顺序输出出圈人编号。题目本身不难，尤其n、m都不大的时候，怎么写都能过。但我这几年带新人刷题发现，越是这样看起来“简单”的题，越容易在循环边界、回卷、出圈后起点这些细节上翻车。这篇文章不打算只贴一份能AC的代码，而是把这道题涉及的几种典型解法——数组模拟、链表模拟、队列模拟、数学递推——全部拆开讲一遍，顺便聊聊各自的适用场景和容易踩的坑，希望你看完之后不只是会做P1996，而是真正把约瑟夫问题的“套路”吃透。

1. 题目到底在问什么：先把约瑟夫问题的逻辑捋清

1.1 从洛谷P1996的原题描述说起

题目原文大致这样：有 n 个人，编号 1 到 n，按顺时针围成一圈。从第 1 个人开始报数，数到第 m 个人，该人出圈；然后从出圈人的下一个人开始，继续从 1 报数，依旧数到 m 的人出圈。重复这个过程，直到圈内所有人都出圈。要求按出圈顺序输出每个人的编号。

这道题最核心的动作有两个：一个是“周期性报数”，另一个是“删除节点”。周期性体现在人始终在围成一个环，报数报到末尾要绕回开头；删除体现在一旦有人报到 m，他就再也不能参与后续报数。这两点对应到代码里，就是环状遍历和标记删除，很多解法都是围绕这两个动作展开的。

1.2 手跑一遍n=5、m=3的完整过程

光看文字容易晕，我们先拿小数据手推一遍。假设 n=5，m=3，初始圈内是 1、2、3、4、5，从 1 开始报数：

• 报数过程：1报“1”，2报“2”，3报“3”，所以3号出圈。
• 从4号开始重新报1：4报“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 数组 out，out[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 数到 m，break 出来后当前 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) % n

2.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 自然停在待删除节点的前一个节点上。比如 n=5、m=3 时，第一次循环 pre 依次变成 1、2，最后 out = nxt[2] = 3，正是第一个出圈的3号。删除操作就是一行nxt[pre] = nxt[out]，把前驱的指针直接接到 out 的下一个节点，out 就从环里剥出去了。

还有一个细节：当 m=1 时，内层 for 循环一次都不走，pre 保持 n，out = 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; queue<int> 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; }

以 n=5、m=3 为例：初始队列 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 时会非常有用。

三种模拟解法可以简单对比一下：

如果是比赛里快速AC，我一般首选队列 + 取模优化，代码短、逻辑清楚，不容易出边界错。

5. 数学递推：O(n)求出最后幸存者

5.1 递推公式与推导

前面几种解法都在模拟过程，但约瑟夫问题其实藏着一个非常漂亮的数学结构：只求最后幸存者时，不需要模拟每一轮，直接 O(n) 递推就能算出来。

先约定编号从 0 开始。设 f[i] 表示 i 个人围成一圈、从 0 号开始报数时，最后幸存者的编号。i=1 时显然 f[1] = 0。

当有 i 个人时，第一轮报到 m 的人会出圈。因为 0 号先报 1，所以出圈的是第 m 个人，它的编号是 (m-1) % i，我们记这个编号为 k。出圈之后，剩下的 i-1 个人从 k+1 开始重新报数。如果我们把 k+1 映射成 0、k+2 映射成 1、……，那么这 i-1 个人就完全等价于一个全新的 i-1 人约瑟夫问题，它的幸存者编号就是 f[i-1]。

最后把这个幸存者从“新编号”映射回“老编号”，只需要加上 k+1 再对 i 取模：

f[i] = (f[i-1] + k + 1) % i = (f[i-1] + m) % i

这里解释一下为什么括号里是 m：因为 k+1 = (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; }

测试一下 n=5、m=3：s=0；i=2 时 s=(0+3)%2=1；i=3 时 s=(1+3)%3=1；i=4 时 s=(1+3)%4=0；i=5 时 s=(0+3)%5=3；最终输出 s+1=4。对应前面手推的结果，最后剩下的是4号，完全正确。

5.3 这道题为什么不能直接套递推

看到这里你可能有个疑问：洛谷 P1996 要求输出完整的出圈顺序，不是一个幸存者编号，那这个递推还有什么用？

直接拿这个递推没法输出完整顺序，但有两个重要的应用场景。第一，当题目改成“只问最后剩下谁”时，O(n) 解法是碾压所有模拟法的。比如 n=10^7、m=10^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 取模。这里我建议你拿 n=5、m=3 手动走一遍，体会 pos 的变化过程，比听我讲十遍都管用。

这种写法在 n 达到 10^5、10^6，m 也很大时依然能跑，是竞赛里处理大规模约瑟夫问题的常用手段。如果 n 再往上走，树状数组的空间也可能吃紧，届时要考虑更专门的数学优化，不过那就超出 P1996 的讨论范围了。

6. 常见问题与调试实录

6.1 懵圈率最高的三个坑

第一个坑：把已出圈的人算进报数。数组版里最常见，报数循环没有判断 out[cur]，导致明明已经出圈的人还在“报数”，出圈顺序全乱。解决办法就是计数前先判断是否在场。

第二个坑：回卷时机不对。用 0-indexed 时，cur = (cur + 1) % n写一次就够了，问题往往出在“出圈后还要再往前走一步”这个动作上。很多人会在循环里外各写一次 cur+1，结果第二轮直接跳过了人。我建议把“找第 m 个人”和“确定下一轮起点”看成两件事，前者在 while 循环里完成，后者在出圈后用一句cur = (cur + 1) % n单独完成。

第三个坑：m=1 这类边界。很多人测试的时候只测 m>1 的情况，导致 m=1 时数组版输出错，链表版反而对。m=1 时应该从1号开始一个接一个出圈，即输出 1 2 3 ... n。队列版里 m=1 时内层循环一次不转，直接弹出队首，天然正确。

6.2 调试与对拍方法

对于这种模拟题，最推荐的调试方法就是“小数据手工推演 + 代码逐步对照”。把 n=5、m=3 的手推出圈顺序写在注释里，然后在代码里加一行输出当前 cur 或队列状态的调试信息，跑一遍看看和手推过程是否一致。

更工程化的方法是写对拍。用一份你觉得绝对正确的暴力代码（比如队列版）当“标准答案”，随机生成 n 和 m，跑 1000 组数据，比较输出是否一致。对拍脚本很简单：生成随机数据、分别跑两个程序、diff 结果，一旦不一致，就把那组数据拿出来单步调试。这个方法我从入门用到现在，几乎所有逻辑题的小 bug 都是这么抓出来的。

6.3 特殊数据自测清单

我整理了一份小小的自测清单，每次写完约瑟夫相关代码都会跑一遍：

最后一行我手推验证过：初始1到7，m=4，第一轮数到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)。我之前遇到过一道加强版题目，n=10^6、m=10^9，队列模拟直接跑到怀疑人生，换成树状数组后几百毫秒出结果。这也是为什么我不建议只会一种写法的原因——模板题虽然简单，但它后面缀着的“加强版”往往就是区分选手的分水岭。

7.3 编程竞赛里的“一题串讲”

站在学习角度，P1996 是一道非常适合“一题多解”的题。数组是入门，链表是理解删除，队列是锻炼抽象思维，递推是数学建模，树状数组是数据结构进阶。一道题把数据结构课里最基础的内容几乎串了个遍，这也是我为什么愿意花这么长篇幅写它。如果你正处在学习算法的初级阶段，我强烈建议你把这几种做法都写一遍，跑同样的测试数据，感受一下不同解法的代码量差距和思路差异。

最后分享一点我自己的习惯。每次做约瑟夫问题，我不管数据范围多大，都会先在草稿纸上把 n=5、m=3 整个流程手推一遍，再把这份手推结果当作“测试用例”去验证代码。这看起来机械，但恰恰是这类模拟题最稳的提防手段——很多 bug 不是逻辑没想到，而是手指比脑子快。至于解法选择，我的原则很简单：n 小就用队列模拟，代码短又不容易错；n 大只想求幸存者就用递推；n 大还要完整顺序就用树状数组。把这套组合拳打熟，约瑟夫问题再怎么出变体，你心里都有底。