1. 约瑟夫环到底在考什么先读懂 Counting Out约瑟夫环Josephus problem是算法竞赛里最经典的“知道结论很简单不知道结论死活写不对”的题型。OJ 上的 HDU1457 Counting Out 就是这类题的代表。它描述的场景很直白n 个人围成一圈编号从 1 到 n从某个人开始报数报到 m 的人出圈下一个人接着从 1 报数直到只剩最后一个人让你输出这个人的编号有时候还要求输出完整出圈顺序。看起来就是按规则一步步模拟但数据一大纯模拟就扛不住了。这道题适合正在刷 OJ 的新手也适合准备面试想快速复习基础算法的求职者更适合那些背过约瑟夫递推公式但一直没搞懂“公式怎么来的”的同学。我的看法是公式背下来不难真正值钱的是推导过程。因为算法题里的约瑟夫环经常换皮换起点、换报数规则、换淘汰节奏你死记的公式会立刻失效只有理解了原理才能每次都在几分钟内写出正确的代码。1.1 这类题目的常见输入形态从我刷题的实际情况看HDU1457 这类题的输入通常不止一组数据。常见写法有两种一种是每行给两个整数 n 和 m读到 0 0 结束另一种是用 EOF 作为结束标记也就是一直读直到文件末尾。这两种写法在代码上的处理不一样用 0 0 结束要在循环里先判断读进来的值用 EOF 结束则要看 scanf 的返回值是不是 2。还有一个特别容易忽略的点编号到底是从 0 到 n-1还是从 1 到 n。很多教科书和网上的题解推导公式时都默认用 0-based编号 0 到 n-1提交前忘了把结果加 1就会卡在 Wrong Answer 上找不到原因。我拿到一道约瑟夫题第一件事就是把这几个要素写在草稿纸上编号从几开始、报数从谁开始、结束标记是什么、n 的范围有多大。别看都是小事每一条都直接影响代码怎么写。1.2 动手前先想清楚三个问题第一个问题n 的上限是多少。如果 n 只有几千用数组模拟轻轻松松如果 n 到了十万甚至百万模拟法基本必超时必须走 O(n) 的递推。第二个问题题目要的是“最后一个幸存者”还是“完整出圈顺序”。只要幸存者O(n) 递推一行搞定要完整出圈顺序就得用链表或者树状数组复杂度完全不是一个量级。第三个问题这一轮的报数值 m 是固定的还是每一轮都会变。变步长的版本我后面单独讲它的递推公式只是把常数 m 换成一个序列。这三个问题想清楚整个解题方向就定了。下面我先把最主流的两种解法摆出来对比一下。2. 两种解法选型模拟法 vs 递推法2.1 模拟法写起来爽跑起来慢最直观的思路就是老老实实模拟开一个标记数组记录每个人是否还活着或者干脆建一个循环链表每一轮走 m 步淘汰一个人。这种方式最贴近生活经验写的时候不容易理解错题意但代价是时间复杂度大约是 O(n*m)。n100、m1000 的时候无所谓一旦 n 上到十万m 再大一点循环次数就是十亿量级多半会超时。不过模拟法并不是一无是处。我在写递推公式之前一定先用模拟代码跑几组小数据把答案记下来当“标准答案”。公式写出后再用小数据对拍这样能快速发现自己是不是漏掉了边界条件。对拍时你会发现很多细节比如淘汰掉第 m 个人之后下一个人应该是谁这个“指针移动”的顺序一旦搞错结果就会差很远。2.2 递推法把问题缩小到 n-1递推法的核心观察是第一轮淘汰了一个人之后剩下的 n-1 个人仍然围成一圈继续报数。这个 n-1 人问题和原来的 n 人问题“结构完全相同”只是每个人的编号整体发生了平移。于是只要知道 n-1 人时的幸存者编号就能把它映射回 n 人时的编号。这样从 1 个人一直推到 n 个人总复杂度只有 O(n)空间 O(1)。很多人不理解为什么递推公式里有个取模其实取模就是在做“围成一圈”这件事。编号加完 m 之后可能超过当前人数 n超过的部分要从头再数取模就是模拟这个回绕过程。2.3 复杂度对照表解法时间复杂度空间复杂度适合场景数组标记模拟O(n*m)O(n)n 很小或想验证答案循环链表模拟O(n*m)O(n)输出完整出圈顺序n 不大一维递推O(n)O(1)只要幸存者编号n 较大树状数组/线段树O(n log n)O(n)输出完整出圈顺序n 较大实际做题时我的选型原则很简单只要题问的是“最后剩下谁”一律用递推只要题问的是“完整出圈顺序”先看 nn 小用链表n 大上树状数组。下面把最关键的递推公式推导过程完整讲一遍。3. 递推公式推导为什么是 (f(n-1)m)%n3.1 从 0-based 编号开始推导先把 n 个人编号为 0 到 n-1并假设从编号 0 的人开始报数报到 m 的人出圈。设 f(n) 表示这种情况下最后幸存者的编号。显然只有 1 个人的时候幸存者就是他本身所以 f(1)0。现在看 n 个人的情况。第一轮第一个出圈的人是编号 (m-1) mod n 的人。他出圈之后下一个人开始报数这个人的编号是 m mod n。剩下 n-1 个人如果把他们重新编号为 0 到 n-2就变成了一个规模为 n-1 的约瑟夫环。在这个新环里幸存者的“新编号”就是 f(n-1)。要把这个新编号映射回原来的编号只需要加上 m 再对 n 取模因为整个环形结构相当于整体平移了 m 个位置。所以递推式就是f(1) 0f(n) (f(n-1) m) % n注意这里的 m 不用先对 n 取余因为外面还有一个 % n最终结果一定是合法的。但写代码时要注意 m 和 n 相乘、相加过程中可能溢出该用 long long 就大胆用。3.2 用手算验证公式拿 n5、m3 来验证。按游戏规则走一遍1 到 5 围成一圈从 1 开始报数报到 3 的人出圈。第一轮出圈的是 3剩下 4、5、1、2从 4 开始报到 3出圈的是 1剩下 2、4、5从 2 开始出圈的是 5剩下 2、4从 2 开始报到 3 时又数回 2于是出圈的是 2最后幸存者是 4。再用递推公式算一遍f(1)0f(2)(03)%21f(3)(13)%31f(4)(13)%40f(5)(03)%53。0-based 答案是 3转成 1-based 就是 4和模拟结果完全一致。这个例子说明只要编号规则对应得上公式可以直接在手算时用来做校验。3.3 三个容易翻车的边界第一个边界是 m1。每轮淘汰的都是当前开始报数的那个人最后一定剩下编号最大的那个人1-based 答案就是 n。公式推起来也没问题但单独特判会省一点时间也避免你多想。第二个边界是 n1。直接返回 00-based即可别让循环进去又退出来容易出错。第三个边界是报数起点偏移。如果题目说的是“从编号 k 的人开始报数”就不能直接套公式的答案。假设 f(n) 是从编号 0 开始报数的结果那么从 1-based 的 k 开始报数时0-based 幸存在原编号中是 (f(n)k-1) % n再转成 1-based 就是 ((f(n)k-1)%n) 1。这个偏移处理我在做变体题时经常用到。4. 代码实现与提交排坑4.1 固定 m 的标准 C 解法递推公式的代码简洁到让人怀疑是不是少写了好多东西但它确实就是这几行#include stdio.h int main() { int n, m; while (scanf(%d%d, n, m) 2 (n || m)) { int s 0; // f(1) 00-based for (int i 2; i n; i) { s (s m) % i; } printf(%d\n, s 1); // 转成 1-based } return 0; }循环里 i 从 2 增长到 n每一步 s 都变成 i 人时的答案。这个写法有两个关键细节一是 s 的初值对应 f(1)所以循环从 2 开始二是输出前加 1。很多 WA 就是因为这两点没想明白。如果题目的结束标记不是 0 0而是直接多组读到 EOF就把 while 条件改成while (scanf(%d%d, n, m) 2)。如果 m 可能很大建议把 n、m、s 都声明成 long long防止中间步骤溢出。有人觉得 n 的范围看着不大就不加 long long结果 m 给到 1e9sm 直接爆掉 int这种翻车我见过太多次了。4.2 多组输入与输出格式的坑老题对输出格式要求很严格常见的坑有两个。一个是“Case”前缀有的题要求每组输出前带Case 1:不对齐就是 Presentation Error。另一个是每组输出之间有没有空行这个要盯着题目样例看不能拍脑袋。读入方面如果用 0 0 作为结束标记注意在循环开头就把两个值读进来再判断不要在循环里又 scanf 一次。我见过有人写成先读 n判断 n 为 0 break再读 m结果 n0 m5 这种非法组合直接导致后续数据错位。正确做法是while (scanf(%d%d, n, m) 2 (n || m))一口气处理完。4.3 报数 m 每轮变化的变体HDU1457 有些版本会给出一个报数序列第 i 轮用第 i 个报数值。这种情况递推公式依然成立只要把常数 m 换成对应的序列值。假设当圈里还剩 i 个人时这一轮使用的报数值存在数组 a[i] 里代码就是long long s 0; for (int i 2; i n; i) { s (s a[i]) % i; } printf(%lld\n, s 1);需要注意的是a[i] 的下标含义要和“剩下 i 个人”对应上。有的题从剩余 n 个人开始给第一个报数值有的题给的是从 1 到 n 的一整串数读入后要确认清楚。我在写这种版本时习惯先用 n5 手算一组再拿代码跑一遍比对比直接提交探雷靠谱得多。5. 进阶变体出圈顺序、超大 n、变步长报数5.1 要求输出完整出圈顺序时怎么办只求幸存者递推是最好的。但有的题目会问完整出圈顺序这时递推就无能为力了。n 比较小的时候我直接用 C 的 list 写循环链表模拟代码短、思路清晰#include bits/stdc.h using namespace std; int main() { int n, m; while (cin n m (n || m)) { listint L; for (int i 1; i n; i) L.push_back(i); auto it L.begin(); while (!L.empty()) { int step (m - 1) % (int)L.size(); for (int i 0; i step; i) { it; if (it L.end()) it L.begin(); } cout *it; it L.erase(it); if (it L.end()) it L.begin(); cout (!L.empty() ? : \n); } } return 0; }这里的 step 先对 L.size() 取余是为了避免 m 大于当前人数时白转好几圈。erase 返回的是被删元素的下一个元素的迭代器这个特性能让代码很干净。如果 n 很大链表模拟会超时那就得换树状数组维护“还剩多少人”配合二分查找第 k 个存活者做到 O(n log n)。5.2 n 超大而 m 很小时的批量跳步优化有一种极端情况n 高达 1e9 甚至 1e18m 却很小比如 m2 或 m3。这时候 O(n) 的递推也太慢需要批量跳步。原理是当 s m 小于当前人数 i 时取模不会生效s 只是简单地加上 m这个“线性增长”阶段可以连续跳过很多轮。long long josephus_large(long long n, long long m) { if (m 1) return n - 1; long long s 0; long long i 2; while (i n) { if (s m i) { // 连续跳 step 轮期间不需要取模 long long step (i - 1 - s m - 2) / (m - 1) - 1; long long remain n - i 1; if (step remain) step remain; s step * m; i step; } else { s (s m) % i; i; } } return s; }这个优化建议配合小数据对拍吃透否则公式里的除法边界容易写错。我自己验证过 n100、m2 时它给出的答案是 720-based和经典结论一致。但这类优化题在 HDU1457 里大概率用不上当作扩展知识了解即可。5.3 把递推推广到变步长报数变步长报数的思路和固定 m 一样只是公式里的 m 变成序列。假如题目给了长度为 n 的数组第 i 个元素表示当圈里剩余 i 个人时从 1 数到这个数淘汰那么答案就是s (s a[i]) % i从 i2 推到 n。这里有个容易混的点数组顺序是从剩余人数多到少还是从少到多要按“剩余 i 个人”来组织才会和递推方向一致。这种变体在面试题里偶尔出现核心还是考察你有没有真正理解递推公式的推导过程。能讲清楚“为什么偏移量是 m”而不是背下来这类题就都难不住你。6. 常见问题与排查速查表6.1 高频踩坑点我自己这些年刷题、写题解发现约瑟夫环的 WA 几乎都集中在下面这些地方症状可能原因处理方法答案总是比样例大 1 或小 1编号 1-based 与 0-based 转换出错输出前确认要不要 1多组数据只出了第一组结束标记没判断好用 scanf 返回值结合 sentinel大数据超时用了 O(n*m) 的模拟换成 O(n) 递推m 很大时结果异常int 溢出全部换 long long出圈顺序错乱删掉元素后指针没有正确指向下一个用 erase 返回值注意迭代器回绕从指定编号开始报数算错没有处理起点偏移结果加上起点偏移再取模6.2 对拍与调试技巧我强烈建议在正式提交前写一个暴力模拟版本随机生成小数据把模拟答案和递推答案逐组对比。这个方法看起来笨但排查边界条件特别快。比如 n1、m100 这种组合模拟代码可能根本没写到递推公式也可能因为 m 和 n 的关系出问题对拍一两次就能抓出来。另一种实用调试法是手算小数据。n5、m3 的结果是 4n7、m2 的结果是 7这几个固定组合可以作为“记忆测试点”。如果代码在这几组上全对正确率就很有保障了。7. 刷题之外的一点心得约瑟夫环这类题给我的最大体会是算法的价值不在于你背了多少模板而在于你能不能把一个动态过程抽象成一个递推关系。第一次学递推公式时我也觉得“这怎么可能一步到位”直到自己从 n5 一步步推到 n6才真正理解取模的意义。后来遇到变步长、变起点、输出完整顺序都能顺着这个思路快速写出来。最后分享一个小技巧不管题目给的编号是 1 还是 0我在草稿上一律先用 0-based 推推完再统一转换。这样可以避免在推导过程中反复纠结号思路会清晰很多。你可以试试看几次之后你会发现所有约瑟夫环变体题本质上都是同一个公式在换皮。
