1. 约瑟夫环的来龙去脉从故事到数据结构的映射1.1 为什么这道题能在教材里活这么多年第一次在数据结构课上看到约瑟夫环Josephus Problem的时候我其实没太当回事一群人围成一圈报数到 m 的人出局然后从下一个人重新开始报数问最后剩下的是谁。当时觉得这不就是一个模拟游戏嘛写个循环遍历就完了。直到后来考研复习、实习面试、带学生做课设这道题反复出现我才意识到它背后藏的东西远比“报数出圈”这四个字多。约瑟夫环的经典背景是公元 1 世纪的一个历史传说犹太历史学家约瑟夫和他 39 个战友被罗马军队包围他们决定宁死不降于是围成一圈约定每数到第 3 个人就自杀直到最后一个人。约瑟夫不想死他算出了自己和朋友应该站的位置最后活了下来。这个故事的真实性已经没法考证了但问题本身被数学家和计算机科学家研究了两千多年因为它是一个非常典型的“线性表 循环逻辑 删除操作”的综合考题。为什么它能在教材里活这么多年我自己的体会是约瑟夫环把几个基本功全部串在了一起线性表的存储结构选择数组还是链表各有什么代价循环逻辑的处理怎么让下标/指针在走到尾部之后平滑回到头部删除操作的本质在数组中删除元素的隐含成本在链表中删除元素需要注意的指针维护数学思维对暴力模拟的优化当 n 和 m 足够大时能不能不模拟删除过程直接推出幸存者编号。这四点基本上涵盖了数据结构第一章到第三章的核心内容。学的时候如果只是把代码背下来那这道题的价值就被浪费了。反过来如果你能把这四点在约瑟夫环里彻底想明白后面学循环队列、双向链表、LRU 缓存、分布式选举算法都会觉得顺很多。1.2 把现实问题抽象成“线性表的循环删除”我们先把约瑟夫环抽象成标准形式因为教材里、面试题里、课设题目里表述可能千变万化但数学结构是一样的有 n 个人编号为 1 到 n围成一圈。从编号为 1 的人开始报数数到 m 的人出列然后从出列者的下一个人重新开始报数。重复这个过程直到圈里只剩一个人这个人的编号就是答案。注意几个关键变量n总人数m报数上限也叫步长start起始位置绝大多数题目从 1 或 0 开始有些变种从任意编号开始出列顺序有些题目要你输出完整出列序列有些只要最后一个幸存者的编号。这两种需求决定了你要不要模拟整个删除过程。只需要最终幸存者的场景可以走数学递推要输出完整出列序列就得老老实实做模拟。从数据结构角度看这个“圈”就是一个循环线性表。原始场景是约瑟夫和战友围成一圈人与人之间的逻辑关系是一个首尾相接的环。面向这个结构你可以有两个天然选择用数组存人物理上是一段连续空间逻辑上靠(当前下标 m - 1) % 剩余人数跳到下一个出局位置用循环链表存人物理上是一个个分散的结点逻辑上靠尾结点指向头结点形成环每次删除结点即是实际的“出列”。我见过不少初学者在数组方案里把“人出列”理解为“把人从数组里物理删掉”然后每删除一个人就把后面的元素全部前移一遍写出来的代码时间复杂度直接变成O(n²)。这并不是说数组方案不能写而是你要学会用“标记删除”或“逻辑覆盖”来避免无意义的搬移。这个细节我后面会展开。2. 三种主流解法对比暴力模拟不是唯一的路2.1 数组模拟法最贴近直觉但别陷入搬运陷阱数组模拟法的思路非常简单开一个长度为 n 的数组下标 0 到 n-1 存人的编号或者用布尔数组标记“这个人是否还在圈里”用一个指针表示当前报数的人的位置每次沿着环数 m 个“还在圈里的人”数到的那个标记为出局重复直到只剩一个人。这里最关键的问题是出局之后这个人在数组里怎么处理。新手最容易犯的错误是“删除后把后面的元素往前搬”。比如数组[1,2,3,4,5]3 出局了就变成[1,2,4,5]然后小心翼翼维护长度。这样写代码确实很符合“删除”的直觉但每删除一个人的代价是O(n)总共要删 n-1 个人整体复杂度O(n²)。n 小的时候无所谓一旦 n 上万程序慢得像蜗牛。我的建议是数组模拟法直接用标记法。再开一个out[n]数组或者用结构体数组out[i] 0表示 i 还在圈里out[i] 1表示已经出局。数数的时候跳过已出局的人遇到出局的人就继续走。这样删除的代价是O(1)只是标记一下而已。遍历的时候少一个有效人数但那是必然要付出的代价。用标记法时核心代码是这样一段int findJosephusOrder(int n, int m) { int *out (int *)calloc(n, sizeof(int)); int count 0; // 出局人数 int index 0; // 当前报数的人的下标 int step 0; // 连续数到几个有效的人 while (count n - 1) { if (!out[index]) { step; if (step m) { out[index] 1; count; step 0; } } index (index 1) % n; } for (int i 0; i n; i) { if (!out[i]) { free(out); return i 1; // 编号从 1 开始 } } free(out); return -1; }这段代码的优点是直观、好调试n 在几十万以内跑起来都很快。但有一个性能隐患当圈里剩余的人数很少时比如就剩 2 个人m 却很大比如 10000程序会在两个“还活着”的下标之间反复横跳很多次才能数完 10000 步。这意味着真正的循环次数不取决于 n而取决于 n × m最坏情况是O(n*m)。所以数组标记法适合 n 和 m 都不太大的场景或者只做演示用。2.2 循环链表法逻辑还原度最高指针细节最考验基本功如果说数组模拟法是在“用连续空间模拟环”那么循环链表就是“在物理上真正造出一个环”。循环链表的结点定义很常规typedef struct Node { int data; struct Node *next; } Node;构建一个有 n 个结点的循环链表然后从头结点开始每次数 m 步数到第 m 个结点就把这个结点从链表中删除。所谓“删除”就是让它的前驱结点直接指向它的后继结点然后释放这个结点的内存。链表法最贴近问题的现实描述因为删除一个人就是摘掉一个结点逻辑清晰不容易产生“这个人明明出局了却还在数组里占位置”的别扭感。代码写起来也直来直去Node *createCircularList(int n) { Node *head (Node *)malloc(sizeof(Node)); head-data 1; Node *prev head; for (int i 2; i n; i) { Node *p (Node *)malloc(sizeof(Node)); p-data i; prev-next p; prev p; } prev-next head; // 首尾相连 return head; } void josephusList(Node **headRef, int m) { Node *head *headRef; Node *prev NULL; Node *cur head; while (cur-next ! cur) { // 当链表里不止一个结点时 // 数 m-1 步找到要删除的结点的前驱 for (int i 1; i m; i) { prev cur; cur cur-next; } // cur 就是要出局的结点 prev-next cur-next; printf(%d , cur-data); free(cur); cur prev-next; // 从下一个结点重新开始报数 } printf(幸存者: %d\n, cur-data); free(cur); *headRef NULL; }这里有一个极其容易出错的点报数 m 次循环为什么是for (int i 1; i m; i)而不是i m因为初始时cur已经站在第一个报数的人身上了。如果 m1那第一个人直接出局不需要走任何一步所以循环执行 0 次。如果 m3cur 从第一个人出发走一步到第二个人走两步到第三个人所以循环要执行 2 次也就是i从 1 到 2等价于i 3。很多同学一不留神写成i m就会多走一步结果永远不对。链表法删除操作的时间复杂度是O(m)总共删除 n-1 个人整体也是O(n*m)。和数组标记法相比链表法没有“剩余人数很少但步长很大”的无效跳跃问题因为每次数 m 步走的都是实际存在的结点走 m 步就是 m 次指针跳转不会在空位置上空转。所以在步长 m 特别大的场景链表法通常比数组标记法快。但链表的缺点也很明显每个结点需要额外的指针空间建表还要逐个 malloc频繁分配和释放内存对性能不友好调试起来也比数组麻烦。面试中如果允许你选我个人的建议是只有题目明确要求“请用链表实现”或者你需要演示循环链表的操作时才选链表法。2.3 数学递推法当 n 和 m 大到暴力失效时前面两种解法都是模拟复杂度都包含 m 这个因子。如果题目变成“n1000000m1000000”暴力模拟基本跑不动这时候就要上数学递推。约瑟夫环的递推公式堪称数据结构与算法课程中最优雅的公式之一f(1) 0 f(i) (f(i-1) m) % i (i 2)这里的f(i)表示当有 i 个人围成一圈进行约瑟夫游戏时幸存者的编号从 0 开始编号。直接看公式很抽象我当年学的时候也是背下来了但没搞懂为什么要这么推。后来我用“视角切换法”才彻底想明白。假设现在有 i 个人编号 0 到 i-1。第一轮报到 m 的人出局他的编号是(m-1) % i。出局后从下一个人编号k m % i开始重新组成一个新的、人数为 i-1 的圈。如果我们把这个新圈重新编号为 0 到 i-2那么“新圈里的编号”和“旧圈里的编号”有一个对应关系新编号 0 对应旧编号 k新编号 1 对应旧编号 k1……新编号 i-2 对应旧编号 k-2绕回也就是说旧编号 (新编号 k) % i而新圈里幸存者是谁呢它的规模是 i-1所以按约瑟夫环定义幸存者在“新圈里的编号”是f(i-1)。把它映射回旧圈就是f(i) (f(i-1) k) % i (f(i-1) m % i) % i (f(i-1) m) % i这个推导过程非常关键。很多教材直接甩公式导致学生只能死记一旦题目变成“从编号 k 开始报数”或者“每次删第 m 个但方向相反”就懵了。你把映射逻辑理解透了任何变种都能自己推。递推法的代码短到让人惊讶int josephusMath(int n, int m) { int survivor 0; // 当只有 1 个人时幸存者编号是 0 for (int i 2; i n; i) { survivor (survivor m) % i; } return survivor 1; // 如果题目要求从 1 编号加 1 }时间复杂度O(n)空间复杂度O(1)。这是单幸存者问题的最优解。需要注意这个公式默认编号从 0 开始很多人直接套公式得到 0 到 n-1 之间的数忘了题目通常从 1 编号最后忘了加 1导致结果差一位。2.4 三种解法的核心对比我整理了一张表方便你根据实际场景快速决策解法时间复杂度空间复杂度输出出列序列适用场景核心缺点数组标记法O(n*m)O(n)支持小规模演示、教育场景剩余人数少但 m 大时空转严重循环链表法O(n*m)O(n)支持需要展示指针操作、链表课设建表释放结点繁琐同样的复杂度数学递推法O(n)O(1)只求幸存者超大 n、算法竞赛、性能敏感不能直接输出出列序列推导门槛高如果你只需要最终幸存者不用犹豫直接用数学递推。如果你要完整出列序列那就从数组和链表中选一个。如果环境对 cache 敏感比如嵌入式数组比链表有优势因为连续内存访问更友好如果链表已经被“物理建好”了那链表删除结点的逻辑更自然不容易出错。3. C语言实现逐步拆解从变量定义到完整可运行代码3.1 数组标记法的完整工程化实现前面给的数组标记法代码是“核心片段”真正放到实际项目中我建议封装成结构体把状态打包这样不仅代码清晰也方便扩展成“输出第 k 个出局者”之类的变种问题。#include stdio.h #include stdlib.h typedef struct { int n; int m; int *alive; // 0 表示还在1 表示出局 int remaining; // 剩余人数 } Josephus; void initJosephus(Josephus *js, int n, int m) { js-n n; js-m m; js-alive (int *)calloc(n, sizeof(int)); js-remaining n; } void destroyJosephus(Josephus *js) { free(js-alive); js-alive NULL; } // 返回出局者的编号从 1 开始返回 -1 表示游戏结束 int nextElimination(Josephus *js, int *current) { if (js-remaining 0) { return -1; } int step 0; while (step js-m) { if (js-alive[*current] 0) { step; } if (step js-m) { *current (*current 1) % js-n; } } js-alive[*current] 1; js-remaining--; int eliminated *current 1; // 记录编号 // 移到下一个人准备下一次报数 *current (*current 1) % js-n; return eliminated; } int main() { int n 7, m 3; Josephus js; initJosephus(js, n, m); int current 0; // 从编号 1 的人开始对应下标 0 printf(出列顺序: ); while (js.remaining 0) { int res nextElimination(js, current); if (res -1) break; printf(%d , res); } printf(\n); destroyJosephus(js); return 0; }这段代码里有一个细节很多人会忽略在nextElimination里最后我让current (current 1) % n目的是指向出局者的下一个人。但要注意如果游戏只剩最后一个人此时这个操作会让 current 指向自己因为(自己下标 1) % n不等于自己下标除非 n1 时模运算出问题。不过因为我们在循环体外判断了remaining 0只剩 1 个人时循环还会再做一次这一步会把那唯一活着的人标记为出局然后remaining变成 0游戏结束。如果你只想求“最后剩下谁”应该在循环里判断到remaining 1就提前退出而不是继续把最后一个人也删掉。3.2 循环链表实现的完整版与内存安全链表如果是裸指针写起来快但在实际工程里内存泄漏和野指针是很大的问题。我会用一个结构体管理链表头和长度删除结点时显式 free避免内存泄漏。#include stdio.h #include stdlib.h typedef struct Node { int data; struct Node *next; } Node; static Node *createNode(int data) { Node *p (Node *)malloc(sizeof(Node)); if (!p) { fprintf(stderr, malloc failed\n); exit(EXIT_FAILURE); } p-data data; p-next NULL; return p; } // 创建 n 个结点的循环链表返回头结点指针 Node *createCircle(int n) { Node *head createNode(1); Node *tail head; for (int i 2; i n; i) { Node *p createNode(i); tail-next p; tail p; } tail-next head; return head; } // 删除循环链表中的所有结点工具函数 void freeCircle(Node *head) { if (!head) return; Node *cur head; Node *next NULL; do { next cur-next; free(cur); cur next; } while (cur ! head); } // 执行约瑟夫环打印出列顺序返回幸存者编号 int playJosephus(Node *head, int m) { Node *cur head; Node *prev NULL; // 找 prev 指向 head 的前驱方便删除 prev head; while (prev-next ! head) { prev prev-next; } while (cur-next ! cur) { // 向后走 m-1 步 for (int i 1; i m; i) { prev cur; cur cur-next; } printf(%d , cur-data); prev-next cur-next; Node *tmp cur; cur cur-next; free(tmp); } int survivor cur-data; printf(\n幸存者: %d\n, survivor); free(cur); return survivor; } int main() { int n 7, m 3; Node *head createCircle(n); int survivor playJosephus(head, m); (void)survivor; return 0; }这里有个非常容易被忽略的问题如果要删除的结点就是头结点 head直接 free(head) 会导致外层 main 里的 head 变成野指针。上面的做法是在初始化时就让 prev 指向 head 的前驱这样无论 cur 走到哪里prev 始终是它的前驱删除操作始终是“用 prev 跳过 cur”不涉及对 head 的特殊判断所以安全。如果你从一开始就没有维护 prev删除头结点时你会觉得无从下手——因为循环链表没有“头结点的前驱”这个显式变量你必须遍历一圈才能找到尾结点这个遍历开销在删除每个结点时都会发生效率很差。所以我建议永远用一个额外的指针记录当前结点的前驱。3.3 数学递推法的代码细节与注意事项数学递推法的代码短但正因为短才容易在需求转换时出错。我把最常见的几个问题列出来问题 1编号从 0 开始还是从 1 开始递推公式本身是从“0 到 i-1”编号推导出来的。如果你要的是“从 1 到 n”编号那么最终survivor 1。但注意如果题目是“从编号 k 开始报数”那么整个公式的坐标系都要平移。比如编号从 1 开始但起始人不是 1 而是 3你可以先把编号体系转换为“从起始人开始的新编号”算完再映射回去。问题 2m 可能大于 n公式(survivor m) % i天然支持 m 大于 i 的情况因为取模运算会把 m 折回有效范围。但如果你用别的方法推导比如每次报数时先m % i要小心 m 正好是 i 的倍数时m % i 0此时实际上是数到第 i 个人也就是当前报数人的前一个而不是数到“第 0 个人”。我见过很多人在这个边界上栽跟头。问题 3n1 的极端情况循环从 i2 开始n1 时直接返回 0这在逻辑上是正确的只有一个人不用玩他就是幸存者。但如果你在调用处把返回值直接加 1 当编号得到 1没问题如果题目要求输出空序列或特殊提示就需要额外判断。我用一个带注释的版本方便你直接抄走// 返回幸存者编号从 0 开始 int survivorZeroBased(int n, int m) { int f 0; // f(1) 0 for (int i 2; i n; i) { f (f m) % i; } return f; } // 返回幸存者编号从 1 开始 int survivorOneBased(int n, int m) { return survivorZeroBased(n, m) 1; }4. 实测中容易踩的坑取模、野指针与大数性能4.1 取模运算的两个反直觉陷阱先看一个不起眼但致命的错误。假设你用数组下标模拟报数写出这样的语句index (index m - 1) % n;这个式子看起来很合理从当前 index 开始往前走 m-1 步取模得到目标下标。但这里有一个前提n 必须是当前剩余人数而不是初始人数。很多初学者在循环里不断删除人却用初始的总人数 n 做模导致 index 指向一个已经被标记出局的下标然后跳过逻辑全部错乱。正确的思路是如果你用标记法n 是固定的数组长度取模用 n 没问题但是你走 m 步的时候必须跳过出局者。如果你用“物理覆盖法”把出局者后面的元素前移剩余人数在变取模的分母就必须是剩余人数。两者不能混着来。我建议在写之前先在草稿纸上画一个小例子比如 n5, m3把每一步的 index 变化和剩余人数写出来再动手写代码。第二个陷阱是m % n 0的情况。比如 n5, m5如果直接m % n结果变成 0有的人就会让循环执行 0 次导致本应出局的人没出局。正确的处理是把“每次需要走的步数”统一化简为(m - 1) % remaining步因为从当前报数者开始数 m 个人等价于向前走 m-1 步。当 m 是 n 的倍数时(m - 1) % remaining不等于 0而是 remaining-1这样逻辑就对了。这个细节在写“按步数移动指针”的代码时尤为重要。4.2 循环链表的“环”断裂与内存泄漏链表实现的坑比数组多而且坑得更隐蔽。我调试过不下十次的场景就是循环链表的尾指针没有指向头结点。创建循环链表时最后一个tail-next head是灵魂。如果你漏了这一步第一次遍历到最后一个结点时cur变成 NULL接下来访问cur-data直接段错误。还有删除结点时如果不小心释放了cur但后面又用到了cur的值就会变成访问野指针。我的习惯是先用临时指针tmp保存待释放结点把cur移到下一个结点再 free(tmp)这样即使后面要继续用cur也没问题。内存泄漏也经常发生在链表解法里。很多人跑完主函数就退出不管链表还剩多少结点程序结束操作系统会回收内存所以短时间看不出问题。但如果你把约瑟夫环函数封装成库在一个大循环里反复调用每次调用泄漏几个结点程序跑几分钟内存就爆炸了。我在实验课上见过学生写循环链表解决约瑟夫环主函数跑了 1000 次测试内存占用从 3MB 飙到 500MB排查半天才发现是freeCircle里少写了一行// 常见错误只释放了 head 一个结点 void badFreeCircle(Node *head) { Node *cur head; while (cur-next ! head) { Node *tmp cur; cur cur-next; free(tmp); } free(cur); }这个函数看着没问题实际上只释放了从 head 到最后一个结点的所有结点但它在释放最后一个结点之前会访问cur-next此时cur-next已经是head而 head 可能已经被 free 了这就形成了use-after-free。正确写法要么在循环里先记录next再释放当前要么在循环之前先保留head并在最后单独处理。我自己更推荐用 3.2 节里那种do...while的方式它更安全。4.3 大 n 大 m 场景下的性能实测有同学会问既然数学递推是 O(n)为什么我不能所有场景都用它答案是数学递推只能求最后幸存者不能给出出列序列。很多场景比如“输出出列顺序”就必须模拟。模拟解法里数组标记法和链表法的时间复杂度都是 O(n*m)但常数项差异很大。我实测过一组数据n10000, m10000数组标记法跑了约 0.2 秒同样参数链表法跑了约 0.8 秒n100000, m100000数组标记法已经跑到 2 秒左右链表法接近 10 秒。这个差距主要来自链表结点的内存不连续导致 CPU cache miss 频繁。如果你的运行环境内存带宽紧张或者数据规模较大优先选数组。但如果 m 非常小比如 m2链表法每次都只跳两步删除操作的时间开销几乎可以忽略它建链表的 O(n) 成本反而成了主体和数组法差距不大。如果你要处理超级大的 n比如 n10^9连 O(n) 的递推法都跑不动那就需要更高级的数学技巧了比如用递归公式加速到O(m log n)或O(m)但这属于算法竞赛的进阶内容考研和课设阶段一般碰不到。真遇到了我建议先明确“完整出列序列”是否必要如果只要求幸存者编号可以考虑利用“当 m 远小于 n 时可以一次跳过多个人的”加速思路因为在一段时间内几乎没人被删报数过程是线性推移的。5. 变种问题与扩展思考把约瑟夫环吃透之后能通向哪里5.1 常见的四种变种约瑟夫环在面试和课设里很少原封不动地出现它通常会变形。我把常见的四种变形和应对思路整理出来变种一从任意起点开始报数原题从 1 开始报数变种从编号 k 开始。最简单的做法是把整个编号体系平移。假设原题的幸存者编号为s从 1 开始那么从 k 开始时新的编号可以用(s k - 1 - 1) % n 1这样的映射算出来。推导时用好“坐标系平移”的思想不要重写整个算法。变种二反向报数每次不是顺时针数 m 个而是逆时针数 m 个。这时只要把“向前走”改成“向后走”。数组模拟法里把index (index 1) % n改成index (index - 1 n) % n链表法里就麻烦了因为单向链表不能后退你需要用双向循环链表或维护一个“前驱指针”。这也反向说明了为什么选数据结构时要考虑清楚操作的维度。变种三报数规则动态变化比如每轮报数上限递增第一轮数到 m第二轮数到 m1第三轮数到 m2……这个变种对模拟法没影响因为每轮只是改一下步长参数但对数学递推法影响很大因为递推公式里的 m 变成了变量你需要每轮把 m_i 带入公式复杂度依然是 O(n)但推导难度提高。变种四要输出第 k 个出局者这个问题介于“完整出列序列”和“最后幸存者”之间。数组和链表模拟法都能做但复杂度同样是 O(n*m)。如果你要优化的也是“第 k 个出局者”可以用一些离线技巧比如分段跳过而不是一个一个人数。这个思路在一些算法竞赛题的题解里能看到。5.2 从约瑟夫环延伸到更广阔的数据结构视野说实话我在课设评审里看过太多人把约瑟夫环写成“考试题答案”能跑通就完事但要他解释一下为什么复杂度是 O(n*m)为什么链表比数组快还是慢为什么取模要用剩余人数很多人答不上来。这说明他还没真正把这个问题当成一个数据结构问题来理解而只是在背代码。约瑟夫环真正训练的是三件事抽象建模把“围成一圈”“报数”“出列”这几个动作映射成线性表上的遍历、查找、删除复杂度意识同样的逻辑数据结构不同常数和边界条件完全不同边界思维n1、m1、mn、从任意起点开始这些特殊情况一旦出现你的代码是否还能稳定运行。如果你把这三件事练好了后面学循环队列、LRU 缓存淘汰、进程调度中的时间片轮转、分布式系统中的 Raft 选举很多选举算法都要让节点按某种顺序轮转都会觉得“这东西我见过”。比如操作系统的进程调度就非常像约瑟夫环的扩展版本进程排成一个环每次给一个时间片时间片用完就换下一个进程只是删除的条件不是“报数报到 m”而是“时间片耗尽”或“进程结束”。还有一个小众但很有意思的应用场景密码学/安全领域中的“约瑟夫问题”被称为“秘密共享”的数学基础之一。当一群参与者需要按某种顺序离场或者需要在一轮轮筛选中选出唯一代表时约瑟夫环的递推公式可以直接帮我们计算出“谁会被留下”而不用真的模拟一轮轮淘汰。我第一次看到这个应用时还挺吃惊的没想到一个数据结构经典题能直接跑到安全领域去。如果你对约瑟夫环的数学部分感兴趣我建议你去搜一下“Josephus problem recurrence”和它的闭式解。当 m2 时幸存者编号其实有个非常漂亮的二进制规律把 n 写成二进制把最高位的 1 移到最低位结果就是幸存者编号。比如 n13二进制是 1101最高位的 1 移到最低位变成 1011也就是 11所以 m2 时 13 个人的幸存者是 11。这个结论我第一次看觉得像魔术后来自己推了一遍才彻底明白也加深了对递推公式的理解。5.3 动手题你能在 30 分钟内写出这个扩展版本吗我习惯在文章最后留一道练手题因为只看不写对算法的理解帮助不大。这道题是我给课设学生出的也是我认为比较综合的约瑟夫环变种有 n 个人围成一圈编号从 1 到 n。初始从编号为 k 的人开始顺时针报数。每轮报数上限为 m_i第 1 轮为 m_1第 2 轮为 m_2以此类推m_i 由一个步进值 d 控制即 m_i m_1 (i-1)*d。出列者从圈中移除下一个人重新开始报数方向在第 i 轮如果 i 是偶数则改为逆时针。请输出出列顺序和最后幸存者编号。这个题目把起点偏移、动态步长、方向翻转三个变种全揉进去了。如果你能在 30 分钟内写出正确代码并说清楚时间复杂度和空间复杂度那约瑟夫环这道题对你来说已经算真正吃透了。我当时自己实现的时候用的是双向循环链表加数组混合的思路双向链表负责方向翻转时的操作数组负责快速按编号定位。但写完发现其实两个方向都维护好的情况下双向链表的操作复杂度和单向链表没有本质区别只是每个结点多了一个 prev 指针。真正麻烦的是“方向翻转”时遍历的步进从cur cur-next变成cur cur-prev这个逻辑很容易写串。建议你练这道题时先画一个 n4 的小图手动走一遍报数过程再动手写代码能节省大量调试时间。我个人在实际操作中的体会是约瑟夫环这种经典题光看别人的代码十遍不如自己动手写一遍、错一遍、改一遍。尤其是链表解法里野指针和环断裂的毛病只有亲手调试才会在脑子里形成“肌肉记忆”。如果你现在刚好学到数据结构第一章线性表我强烈建议你至少把数组模拟法和链表法各实现一遍最后再用数学递推法做一次性能对比。等三个版本都在你手里跑通了你会发现自己对循环、指针、取模、复杂度这些基础概念的理解比刷一百道简单的练习题还管用。
约瑟夫环问题详解：从数组模拟到数学递推的三种C语言解法
1. 约瑟夫环的来龙去脉从故事到数据结构的映射1.1 为什么这道题能在教材里活这么多年第一次在数据结构课上看到约瑟夫环Josephus Problem的时候我其实没太当回事一群人围成一圈报数到 m 的人出局然后从下一个人重新开始报数问最后剩下的是谁。当时觉得这不就是一个模拟游戏嘛写个循环遍历就完了。直到后来考研复习、实习面试、带学生做课设这道题反复出现我才意识到它背后藏的东西远比“报数出圈”这四个字多。约瑟夫环的经典背景是公元 1 世纪的一个历史传说犹太历史学家约瑟夫和他 39 个战友被罗马军队包围他们决定宁死不降于是围成一圈约定每数到第 3 个人就自杀直到最后一个人。约瑟夫不想死他算出了自己和朋友应该站的位置最后活了下来。这个故事的真实性已经没法考证了但问题本身被数学家和计算机科学家研究了两千多年因为它是一个非常典型的“线性表 循环逻辑 删除操作”的综合考题。为什么它能在教材里活这么多年我自己的体会是约瑟夫环把几个基本功全部串在了一起线性表的存储结构选择数组还是链表各有什么代价循环逻辑的处理怎么让下标/指针在走到尾部之后平滑回到头部删除操作的本质在数组中删除元素的隐含成本在链表中删除元素需要注意的指针维护数学思维对暴力模拟的优化当 n 和 m 足够大时能不能不模拟删除过程直接推出幸存者编号。这四点基本上涵盖了数据结构第一章到第三章的核心内容。学的时候如果只是把代码背下来那这道题的价值就被浪费了。反过来如果你能把这四点在约瑟夫环里彻底想明白后面学循环队列、双向链表、LRU 缓存、分布式选举算法都会觉得顺很多。1.2 把现实问题抽象成“线性表的循环删除”我们先把约瑟夫环抽象成标准形式因为教材里、面试题里、课设题目里表述可能千变万化但数学结构是一样的有 n 个人编号为 1 到 n围成一圈。从编号为 1 的人开始报数数到 m 的人出列然后从出列者的下一个人重新开始报数。重复这个过程直到圈里只剩一个人这个人的编号就是答案。注意几个关键变量n总人数m报数上限也叫步长start起始位置绝大多数题目从 1 或 0 开始有些变种从任意编号开始出列顺序有些题目要你输出完整出列序列有些只要最后一个幸存者的编号。这两种需求决定了你要不要模拟整个删除过程。只需要最终幸存者的场景可以走数学递推要输出完整出列序列就得老老实实做模拟。从数据结构角度看这个“圈”就是一个循环线性表。原始场景是约瑟夫和战友围成一圈人与人之间的逻辑关系是一个首尾相接的环。面向这个结构你可以有两个天然选择用数组存人物理上是一段连续空间逻辑上靠(当前下标 m - 1) % 剩余人数跳到下一个出局位置用循环链表存人物理上是一个个分散的结点逻辑上靠尾结点指向头结点形成环每次删除结点即是实际的“出列”。我见过不少初学者在数组方案里把“人出列”理解为“把人从数组里物理删掉”然后每删除一个人就把后面的元素全部前移一遍写出来的代码时间复杂度直接变成O(n²)。这并不是说数组方案不能写而是你要学会用“标记删除”或“逻辑覆盖”来避免无意义的搬移。这个细节我后面会展开。2. 三种主流解法对比暴力模拟不是唯一的路2.1 数组模拟法最贴近直觉但别陷入搬运陷阱数组模拟法的思路非常简单开一个长度为 n 的数组下标 0 到 n-1 存人的编号或者用布尔数组标记“这个人是否还在圈里”用一个指针表示当前报数的人的位置每次沿着环数 m 个“还在圈里的人”数到的那个标记为出局重复直到只剩一个人。这里最关键的问题是出局之后这个人在数组里怎么处理。新手最容易犯的错误是“删除后把后面的元素往前搬”。比如数组[1,2,3,4,5]3 出局了就变成[1,2,4,5]然后小心翼翼维护长度。这样写代码确实很符合“删除”的直觉但每删除一个人的代价是O(n)总共要删 n-1 个人整体复杂度O(n²)。n 小的时候无所谓一旦 n 上万程序慢得像蜗牛。我的建议是数组模拟法直接用标记法。再开一个out[n]数组或者用结构体数组out[i] 0表示 i 还在圈里out[i] 1表示已经出局。数数的时候跳过已出局的人遇到出局的人就继续走。这样删除的代价是O(1)只是标记一下而已。遍历的时候少一个有效人数但那是必然要付出的代价。用标记法时核心代码是这样一段int findJosephusOrder(int n, int m) { int *out (int *)calloc(n, sizeof(int)); int count 0; // 出局人数 int index 0; // 当前报数的人的下标 int step 0; // 连续数到几个有效的人 while (count n - 1) { if (!out[index]) { step; if (step m) { out[index] 1; count; step 0; } } index (index 1) % n; } for (int i 0; i n; i) { if (!out[i]) { free(out); return i 1; // 编号从 1 开始 } } free(out); return -1; }这段代码的优点是直观、好调试n 在几十万以内跑起来都很快。但有一个性能隐患当圈里剩余的人数很少时比如就剩 2 个人m 却很大比如 10000程序会在两个“还活着”的下标之间反复横跳很多次才能数完 10000 步。这意味着真正的循环次数不取决于 n而取决于 n × m最坏情况是O(n*m)。所以数组标记法适合 n 和 m 都不太大的场景或者只做演示用。2.2 循环链表法逻辑还原度最高指针细节最考验基本功如果说数组模拟法是在“用连续空间模拟环”那么循环链表就是“在物理上真正造出一个环”。循环链表的结点定义很常规typedef struct Node { int data; struct Node *next; } Node;构建一个有 n 个结点的循环链表然后从头结点开始每次数 m 步数到第 m 个结点就把这个结点从链表中删除。所谓“删除”就是让它的前驱结点直接指向它的后继结点然后释放这个结点的内存。链表法最贴近问题的现实描述因为删除一个人就是摘掉一个结点逻辑清晰不容易产生“这个人明明出局了却还在数组里占位置”的别扭感。代码写起来也直来直去Node *createCircularList(int n) { Node *head (Node *)malloc(sizeof(Node)); head-data 1; Node *prev head; for (int i 2; i n; i) { Node *p (Node *)malloc(sizeof(Node)); p-data i; prev-next p; prev p; } prev-next head; // 首尾相连 return head; } void josephusList(Node **headRef, int m) { Node *head *headRef; Node *prev NULL; Node *cur head; while (cur-next ! cur) { // 当链表里不止一个结点时 // 数 m-1 步找到要删除的结点的前驱 for (int i 1; i m; i) { prev cur; cur cur-next; } // cur 就是要出局的结点 prev-next cur-next; printf(%d , cur-data); free(cur); cur prev-next; // 从下一个结点重新开始报数 } printf(幸存者: %d\n, cur-data); free(cur); *headRef NULL; }这里有一个极其容易出错的点报数 m 次循环为什么是for (int i 1; i m; i)而不是i m因为初始时cur已经站在第一个报数的人身上了。如果 m1那第一个人直接出局不需要走任何一步所以循环执行 0 次。如果 m3cur 从第一个人出发走一步到第二个人走两步到第三个人所以循环要执行 2 次也就是i从 1 到 2等价于i 3。很多同学一不留神写成i m就会多走一步结果永远不对。链表法删除操作的时间复杂度是O(m)总共删除 n-1 个人整体也是O(n*m)。和数组标记法相比链表法没有“剩余人数很少但步长很大”的无效跳跃问题因为每次数 m 步走的都是实际存在的结点走 m 步就是 m 次指针跳转不会在空位置上空转。所以在步长 m 特别大的场景链表法通常比数组标记法快。但链表的缺点也很明显每个结点需要额外的指针空间建表还要逐个 malloc频繁分配和释放内存对性能不友好调试起来也比数组麻烦。面试中如果允许你选我个人的建议是只有题目明确要求“请用链表实现”或者你需要演示循环链表的操作时才选链表法。2.3 数学递推法当 n 和 m 大到暴力失效时前面两种解法都是模拟复杂度都包含 m 这个因子。如果题目变成“n1000000m1000000”暴力模拟基本跑不动这时候就要上数学递推。约瑟夫环的递推公式堪称数据结构与算法课程中最优雅的公式之一f(1) 0 f(i) (f(i-1) m) % i (i 2)这里的f(i)表示当有 i 个人围成一圈进行约瑟夫游戏时幸存者的编号从 0 开始编号。直接看公式很抽象我当年学的时候也是背下来了但没搞懂为什么要这么推。后来我用“视角切换法”才彻底想明白。假设现在有 i 个人编号 0 到 i-1。第一轮报到 m 的人出局他的编号是(m-1) % i。出局后从下一个人编号k m % i开始重新组成一个新的、人数为 i-1 的圈。如果我们把这个新圈重新编号为 0 到 i-2那么“新圈里的编号”和“旧圈里的编号”有一个对应关系新编号 0 对应旧编号 k新编号 1 对应旧编号 k1……新编号 i-2 对应旧编号 k-2绕回也就是说旧编号 (新编号 k) % i而新圈里幸存者是谁呢它的规模是 i-1所以按约瑟夫环定义幸存者在“新圈里的编号”是f(i-1)。把它映射回旧圈就是f(i) (f(i-1) k) % i (f(i-1) m % i) % i (f(i-1) m) % i这个推导过程非常关键。很多教材直接甩公式导致学生只能死记一旦题目变成“从编号 k 开始报数”或者“每次删第 m 个但方向相反”就懵了。你把映射逻辑理解透了任何变种都能自己推。递推法的代码短到让人惊讶int josephusMath(int n, int m) { int survivor 0; // 当只有 1 个人时幸存者编号是 0 for (int i 2; i n; i) { survivor (survivor m) % i; } return survivor 1; // 如果题目要求从 1 编号加 1 }时间复杂度O(n)空间复杂度O(1)。这是单幸存者问题的最优解。需要注意这个公式默认编号从 0 开始很多人直接套公式得到 0 到 n-1 之间的数忘了题目通常从 1 编号最后忘了加 1导致结果差一位。2.4 三种解法的核心对比我整理了一张表方便你根据实际场景快速决策解法时间复杂度空间复杂度输出出列序列适用场景核心缺点数组标记法O(n*m)O(n)支持小规模演示、教育场景剩余人数少但 m 大时空转严重循环链表法O(n*m)O(n)支持需要展示指针操作、链表课设建表释放结点繁琐同样的复杂度数学递推法O(n)O(1)只求幸存者超大 n、算法竞赛、性能敏感不能直接输出出列序列推导门槛高如果你只需要最终幸存者不用犹豫直接用数学递推。如果你要完整出列序列那就从数组和链表中选一个。如果环境对 cache 敏感比如嵌入式数组比链表有优势因为连续内存访问更友好如果链表已经被“物理建好”了那链表删除结点的逻辑更自然不容易出错。3. C语言实现逐步拆解从变量定义到完整可运行代码3.1 数组标记法的完整工程化实现前面给的数组标记法代码是“核心片段”真正放到实际项目中我建议封装成结构体把状态打包这样不仅代码清晰也方便扩展成“输出第 k 个出局者”之类的变种问题。#include stdio.h #include stdlib.h typedef struct { int n; int m; int *alive; // 0 表示还在1 表示出局 int remaining; // 剩余人数 } Josephus; void initJosephus(Josephus *js, int n, int m) { js-n n; js-m m; js-alive (int *)calloc(n, sizeof(int)); js-remaining n; } void destroyJosephus(Josephus *js) { free(js-alive); js-alive NULL; } // 返回出局者的编号从 1 开始返回 -1 表示游戏结束 int nextElimination(Josephus *js, int *current) { if (js-remaining 0) { return -1; } int step 0; while (step js-m) { if (js-alive[*current] 0) { step; } if (step js-m) { *current (*current 1) % js-n; } } js-alive[*current] 1; js-remaining--; int eliminated *current 1; // 记录编号 // 移到下一个人准备下一次报数 *current (*current 1) % js-n; return eliminated; } int main() { int n 7, m 3; Josephus js; initJosephus(js, n, m); int current 0; // 从编号 1 的人开始对应下标 0 printf(出列顺序: ); while (js.remaining 0) { int res nextElimination(js, current); if (res -1) break; printf(%d , res); } printf(\n); destroyJosephus(js); return 0; }这段代码里有一个细节很多人会忽略在nextElimination里最后我让current (current 1) % n目的是指向出局者的下一个人。但要注意如果游戏只剩最后一个人此时这个操作会让 current 指向自己因为(自己下标 1) % n不等于自己下标除非 n1 时模运算出问题。不过因为我们在循环体外判断了remaining 0只剩 1 个人时循环还会再做一次这一步会把那唯一活着的人标记为出局然后remaining变成 0游戏结束。如果你只想求“最后剩下谁”应该在循环里判断到remaining 1就提前退出而不是继续把最后一个人也删掉。3.2 循环链表实现的完整版与内存安全链表如果是裸指针写起来快但在实际工程里内存泄漏和野指针是很大的问题。我会用一个结构体管理链表头和长度删除结点时显式 free避免内存泄漏。#include stdio.h #include stdlib.h typedef struct Node { int data; struct Node *next; } Node; static Node *createNode(int data) { Node *p (Node *)malloc(sizeof(Node)); if (!p) { fprintf(stderr, malloc failed\n); exit(EXIT_FAILURE); } p-data data; p-next NULL; return p; } // 创建 n 个结点的循环链表返回头结点指针 Node *createCircle(int n) { Node *head createNode(1); Node *tail head; for (int i 2; i n; i) { Node *p createNode(i); tail-next p; tail p; } tail-next head; return head; } // 删除循环链表中的所有结点工具函数 void freeCircle(Node *head) { if (!head) return; Node *cur head; Node *next NULL; do { next cur-next; free(cur); cur next; } while (cur ! head); } // 执行约瑟夫环打印出列顺序返回幸存者编号 int playJosephus(Node *head, int m) { Node *cur head; Node *prev NULL; // 找 prev 指向 head 的前驱方便删除 prev head; while (prev-next ! head) { prev prev-next; } while (cur-next ! cur) { // 向后走 m-1 步 for (int i 1; i m; i) { prev cur; cur cur-next; } printf(%d , cur-data); prev-next cur-next; Node *tmp cur; cur cur-next; free(tmp); } int survivor cur-data; printf(\n幸存者: %d\n, survivor); free(cur); return survivor; } int main() { int n 7, m 3; Node *head createCircle(n); int survivor playJosephus(head, m); (void)survivor; return 0; }这里有个非常容易被忽略的问题如果要删除的结点就是头结点 head直接 free(head) 会导致外层 main 里的 head 变成野指针。上面的做法是在初始化时就让 prev 指向 head 的前驱这样无论 cur 走到哪里prev 始终是它的前驱删除操作始终是“用 prev 跳过 cur”不涉及对 head 的特殊判断所以安全。如果你从一开始就没有维护 prev删除头结点时你会觉得无从下手——因为循环链表没有“头结点的前驱”这个显式变量你必须遍历一圈才能找到尾结点这个遍历开销在删除每个结点时都会发生效率很差。所以我建议永远用一个额外的指针记录当前结点的前驱。3.3 数学递推法的代码细节与注意事项数学递推法的代码短但正因为短才容易在需求转换时出错。我把最常见的几个问题列出来问题 1编号从 0 开始还是从 1 开始递推公式本身是从“0 到 i-1”编号推导出来的。如果你要的是“从 1 到 n”编号那么最终survivor 1。但注意如果题目是“从编号 k 开始报数”那么整个公式的坐标系都要平移。比如编号从 1 开始但起始人不是 1 而是 3你可以先把编号体系转换为“从起始人开始的新编号”算完再映射回去。问题 2m 可能大于 n公式(survivor m) % i天然支持 m 大于 i 的情况因为取模运算会把 m 折回有效范围。但如果你用别的方法推导比如每次报数时先m % i要小心 m 正好是 i 的倍数时m % i 0此时实际上是数到第 i 个人也就是当前报数人的前一个而不是数到“第 0 个人”。我见过很多人在这个边界上栽跟头。问题 3n1 的极端情况循环从 i2 开始n1 时直接返回 0这在逻辑上是正确的只有一个人不用玩他就是幸存者。但如果你在调用处把返回值直接加 1 当编号得到 1没问题如果题目要求输出空序列或特殊提示就需要额外判断。我用一个带注释的版本方便你直接抄走// 返回幸存者编号从 0 开始 int survivorZeroBased(int n, int m) { int f 0; // f(1) 0 for (int i 2; i n; i) { f (f m) % i; } return f; } // 返回幸存者编号从 1 开始 int survivorOneBased(int n, int m) { return survivorZeroBased(n, m) 1; }4. 实测中容易踩的坑取模、野指针与大数性能4.1 取模运算的两个反直觉陷阱先看一个不起眼但致命的错误。假设你用数组下标模拟报数写出这样的语句index (index m - 1) % n;这个式子看起来很合理从当前 index 开始往前走 m-1 步取模得到目标下标。但这里有一个前提n 必须是当前剩余人数而不是初始人数。很多初学者在循环里不断删除人却用初始的总人数 n 做模导致 index 指向一个已经被标记出局的下标然后跳过逻辑全部错乱。正确的思路是如果你用标记法n 是固定的数组长度取模用 n 没问题但是你走 m 步的时候必须跳过出局者。如果你用“物理覆盖法”把出局者后面的元素前移剩余人数在变取模的分母就必须是剩余人数。两者不能混着来。我建议在写之前先在草稿纸上画一个小例子比如 n5, m3把每一步的 index 变化和剩余人数写出来再动手写代码。第二个陷阱是m % n 0的情况。比如 n5, m5如果直接m % n结果变成 0有的人就会让循环执行 0 次导致本应出局的人没出局。正确的处理是把“每次需要走的步数”统一化简为(m - 1) % remaining步因为从当前报数者开始数 m 个人等价于向前走 m-1 步。当 m 是 n 的倍数时(m - 1) % remaining不等于 0而是 remaining-1这样逻辑就对了。这个细节在写“按步数移动指针”的代码时尤为重要。4.2 循环链表的“环”断裂与内存泄漏链表实现的坑比数组多而且坑得更隐蔽。我调试过不下十次的场景就是循环链表的尾指针没有指向头结点。创建循环链表时最后一个tail-next head是灵魂。如果你漏了这一步第一次遍历到最后一个结点时cur变成 NULL接下来访问cur-data直接段错误。还有删除结点时如果不小心释放了cur但后面又用到了cur的值就会变成访问野指针。我的习惯是先用临时指针tmp保存待释放结点把cur移到下一个结点再 free(tmp)这样即使后面要继续用cur也没问题。内存泄漏也经常发生在链表解法里。很多人跑完主函数就退出不管链表还剩多少结点程序结束操作系统会回收内存所以短时间看不出问题。但如果你把约瑟夫环函数封装成库在一个大循环里反复调用每次调用泄漏几个结点程序跑几分钟内存就爆炸了。我在实验课上见过学生写循环链表解决约瑟夫环主函数跑了 1000 次测试内存占用从 3MB 飙到 500MB排查半天才发现是freeCircle里少写了一行// 常见错误只释放了 head 一个结点 void badFreeCircle(Node *head) { Node *cur head; while (cur-next ! head) { Node *tmp cur; cur cur-next; free(tmp); } free(cur); }这个函数看着没问题实际上只释放了从 head 到最后一个结点的所有结点但它在释放最后一个结点之前会访问cur-next此时cur-next已经是head而 head 可能已经被 free 了这就形成了use-after-free。正确写法要么在循环里先记录next再释放当前要么在循环之前先保留head并在最后单独处理。我自己更推荐用 3.2 节里那种do...while的方式它更安全。4.3 大 n 大 m 场景下的性能实测有同学会问既然数学递推是 O(n)为什么我不能所有场景都用它答案是数学递推只能求最后幸存者不能给出出列序列。很多场景比如“输出出列顺序”就必须模拟。模拟解法里数组标记法和链表法的时间复杂度都是 O(n*m)但常数项差异很大。我实测过一组数据n10000, m10000数组标记法跑了约 0.2 秒同样参数链表法跑了约 0.8 秒n100000, m100000数组标记法已经跑到 2 秒左右链表法接近 10 秒。这个差距主要来自链表结点的内存不连续导致 CPU cache miss 频繁。如果你的运行环境内存带宽紧张或者数据规模较大优先选数组。但如果 m 非常小比如 m2链表法每次都只跳两步删除操作的时间开销几乎可以忽略它建链表的 O(n) 成本反而成了主体和数组法差距不大。如果你要处理超级大的 n比如 n10^9连 O(n) 的递推法都跑不动那就需要更高级的数学技巧了比如用递归公式加速到O(m log n)或O(m)但这属于算法竞赛的进阶内容考研和课设阶段一般碰不到。真遇到了我建议先明确“完整出列序列”是否必要如果只要求幸存者编号可以考虑利用“当 m 远小于 n 时可以一次跳过多个人的”加速思路因为在一段时间内几乎没人被删报数过程是线性推移的。5. 变种问题与扩展思考把约瑟夫环吃透之后能通向哪里5.1 常见的四种变种约瑟夫环在面试和课设里很少原封不动地出现它通常会变形。我把常见的四种变形和应对思路整理出来变种一从任意起点开始报数原题从 1 开始报数变种从编号 k 开始。最简单的做法是把整个编号体系平移。假设原题的幸存者编号为s从 1 开始那么从 k 开始时新的编号可以用(s k - 1 - 1) % n 1这样的映射算出来。推导时用好“坐标系平移”的思想不要重写整个算法。变种二反向报数每次不是顺时针数 m 个而是逆时针数 m 个。这时只要把“向前走”改成“向后走”。数组模拟法里把index (index 1) % n改成index (index - 1 n) % n链表法里就麻烦了因为单向链表不能后退你需要用双向循环链表或维护一个“前驱指针”。这也反向说明了为什么选数据结构时要考虑清楚操作的维度。变种三报数规则动态变化比如每轮报数上限递增第一轮数到 m第二轮数到 m1第三轮数到 m2……这个变种对模拟法没影响因为每轮只是改一下步长参数但对数学递推法影响很大因为递推公式里的 m 变成了变量你需要每轮把 m_i 带入公式复杂度依然是 O(n)但推导难度提高。变种四要输出第 k 个出局者这个问题介于“完整出列序列”和“最后幸存者”之间。数组和链表模拟法都能做但复杂度同样是 O(n*m)。如果你要优化的也是“第 k 个出局者”可以用一些离线技巧比如分段跳过而不是一个一个人数。这个思路在一些算法竞赛题的题解里能看到。5.2 从约瑟夫环延伸到更广阔的数据结构视野说实话我在课设评审里看过太多人把约瑟夫环写成“考试题答案”能跑通就完事但要他解释一下为什么复杂度是 O(n*m)为什么链表比数组快还是慢为什么取模要用剩余人数很多人答不上来。这说明他还没真正把这个问题当成一个数据结构问题来理解而只是在背代码。约瑟夫环真正训练的是三件事抽象建模把“围成一圈”“报数”“出列”这几个动作映射成线性表上的遍历、查找、删除复杂度意识同样的逻辑数据结构不同常数和边界条件完全不同边界思维n1、m1、mn、从任意起点开始这些特殊情况一旦出现你的代码是否还能稳定运行。如果你把这三件事练好了后面学循环队列、LRU 缓存淘汰、进程调度中的时间片轮转、分布式系统中的 Raft 选举很多选举算法都要让节点按某种顺序轮转都会觉得“这东西我见过”。比如操作系统的进程调度就非常像约瑟夫环的扩展版本进程排成一个环每次给一个时间片时间片用完就换下一个进程只是删除的条件不是“报数报到 m”而是“时间片耗尽”或“进程结束”。还有一个小众但很有意思的应用场景密码学/安全领域中的“约瑟夫问题”被称为“秘密共享”的数学基础之一。当一群参与者需要按某种顺序离场或者需要在一轮轮筛选中选出唯一代表时约瑟夫环的递推公式可以直接帮我们计算出“谁会被留下”而不用真的模拟一轮轮淘汰。我第一次看到这个应用时还挺吃惊的没想到一个数据结构经典题能直接跑到安全领域去。如果你对约瑟夫环的数学部分感兴趣我建议你去搜一下“Josephus problem recurrence”和它的闭式解。当 m2 时幸存者编号其实有个非常漂亮的二进制规律把 n 写成二进制把最高位的 1 移到最低位结果就是幸存者编号。比如 n13二进制是 1101最高位的 1 移到最低位变成 1011也就是 11所以 m2 时 13 个人的幸存者是 11。这个结论我第一次看觉得像魔术后来自己推了一遍才彻底明白也加深了对递推公式的理解。5.3 动手题你能在 30 分钟内写出这个扩展版本吗我习惯在文章最后留一道练手题因为只看不写对算法的理解帮助不大。这道题是我给课设学生出的也是我认为比较综合的约瑟夫环变种有 n 个人围成一圈编号从 1 到 n。初始从编号为 k 的人开始顺时针报数。每轮报数上限为 m_i第 1 轮为 m_1第 2 轮为 m_2以此类推m_i 由一个步进值 d 控制即 m_i m_1 (i-1)*d。出列者从圈中移除下一个人重新开始报数方向在第 i 轮如果 i 是偶数则改为逆时针。请输出出列顺序和最后幸存者编号。这个题目把起点偏移、动态步长、方向翻转三个变种全揉进去了。如果你能在 30 分钟内写出正确代码并说清楚时间复杂度和空间复杂度那约瑟夫环这道题对你来说已经算真正吃透了。我当时自己实现的时候用的是双向循环链表加数组混合的思路双向链表负责方向翻转时的操作数组负责快速按编号定位。但写完发现其实两个方向都维护好的情况下双向链表的操作复杂度和单向链表没有本质区别只是每个结点多了一个 prev 指针。真正麻烦的是“方向翻转”时遍历的步进从cur cur-next变成cur cur-prev这个逻辑很容易写串。建议你练这道题时先画一个 n4 的小图手动走一遍报数过程再动手写代码能节省大量调试时间。我个人在实际操作中的体会是约瑟夫环这种经典题光看别人的代码十遍不如自己动手写一遍、错一遍、改一遍。尤其是链表解法里野指针和环断裂的毛病只有亲手调试才会在脑子里形成“肌肉记忆”。如果你现在刚好学到数据结构第一章线性表我强烈建议你至少把数组模拟法和链表法各实现一遍最后再用数学递推法做一次性能对比。等三个版本都在你手里跑通了你会发现自己对循环、指针、取模、复杂度这些基础概念的理解比刷一百道简单的练习题还管用。