我在刷菜鸟教程C经典100例的时候练习43给我的印象特别深。题目很短读起来像小时候玩的“丢手绢”有n个人围成一圈顺序排号从第一个人开始报数报到3的人退出圈子问最后留下的是原来第几号。可就是这么个看似简单的问题我第一次提交的代码跑出结果后用手算验证却是错的后来才发现自己在“出圈后下一个人重新从1报数”这个细节上栽了跟头。这道题在C语言经典100例里排在第43位背后其实是一个著名的数学模型——约瑟夫环问题。如果你正在学C语言、刷题库或者准备机试这道题值得你认真啃一遍。今天我就把自己从数组法、链表法到数学递推法的完整思考过程、调试心得和踩坑记录全部摊开来说。1. 练习43到底在考什么约瑟夫环问题的核心痛点1.1 题目原貌与场景还原练习43的原题描述大致是这样有n个人围成一圈顺序排号。从第一个人开始报数从1报到3凡报到3的人退出圈子问最后留下的是原来第几号的那位。输入一个正整数n输出最后留下的人的原始编号。这里有几个关键约束读题的时候必须抠清楚编号从1开始不是从0开始。报数从编号为1的人开始且第一个人报的是“1”。每报到“3”的人立刻退出圈子退出后由他下一位的人重新从“1”开始报数。整个圈子越来越小但报数方向始终不变都是顺时针。问的是“最后留下的那个人”不是“第几个被淘汰的人”。题目没有给出示例输入输出但按照约定如果n5手动画一圈1、2、3、4、5第一轮报到3的是第3号出圈接着4报15报21报3第1号出圈然后2报14报25报3第5号出圈再然后2报14报22报3第2号出圈最后剩4号。所以n5时答案应该是4。这个手动推演非常有用写代码前先在纸上过一遍能避免很多逻辑错误。1.2 为什么这道题值得反复咀嚼很多人觉得这道题只是“模拟一下循环数数”没必要大动干戈。但从C语言学习的角度看它其实把好几个硬骨头一次性集中到了一个小题目里。第一是状态维护。一个“人”在圈内还是圈外需要用变量或标志位表达这考验的是对内存和变量生命周期的理解。第二是循环与取模。圈子是环形的下标走到底之后要绕回开头取模运算在这里不是技巧而是刚需。第三是动态删除。数组里删除一个元素要移动数据链表里删除节点要改指针不同数据结构带来的实现代价完全不同。第四是数学建模。当n变成十万、一百万时模拟法很可能超时这时需要用递推公式直接算出结果这是从“码农”思维向“算法思维”转变的关键一步。所以这道题既是数组和链表的练习题也是递推和数学归纳的入门题。把它吃透比盲目闷头写十道简单的循环题更有价值。2. 三种主流解法从数组到链表再到数学公式2.1 数组模拟法最直观的入门思路数组模拟法的核心思想是“用一个人为的状态数组来标记每个人是否还在圈内”。我通常用一个int数组下标从0到n-1数组元素为1表示在圈内0表示已出圈。然后维护三个变量pos当前遍历到的下标count已经出圈的人数num当前这个人报的数从1开始数。遍历时如果state[pos]为1说明这个人还活着num加1当num等于3时把这个位置标记为0count加1同时num归0然后pos加上1并对n取模实现“绕圈”。循环一直进行直到count等于n-1此时数组中剩下的那个值为1的元素的下标加1就是答案。这个思路和日常排队报数的场景几乎一模一样非常适合刚学完数组和循环的人。它的优点是代码简单、容易调试缺点是时间复杂度是O(n*m)这里m是每次数到出圈所需的步长。当n比较大的时候比如n10000k3虽然勉强能跑但已经能感觉到明显的循环次数如果n到100万基本就跑不动了。所以数组法更适合作为理解和验证的第一版而不是最终优化方案。核心代码片段如下// n个人从1到n编号每次报到3的人出圈返回最后留下的人的编号从1开始 int josephus_array(int n, int k) { int state[1000] {0}; for (int i 0; i n; i) state[i] 1; int pos 0, count 0, num 0; while (count n - 1) { if (state[pos]) { num; if (num k) { state[pos] 0; count; num 0; } } pos (pos 1) % n; } for (int i 0; i n; i) { if (state[i]) return i 1; } return -1; }注意这里k是步长在练习43里k3。把k抽象成参数是为了后续举一反三。2.2 循环链表法更贴近真实游戏逻辑链表法的思路是把n个人串成一个单向循环链表每个节点保存一个编号。报数就是沿着链表走指针每走两步即数到3就删除当前节点然后从下一个节点继续报数。当链表中只剩下一个节点时输出它的编号。和数组法相比链表法最大的优势是“出圈”操作不需要移动数据只需要改两个指针时间复杂度是O(n*k)和数组法在一个量级但空间上要为每个节点分配额外内存。表面上看链表法没有快多少但它把“删除”这个动作变成了指针操作能够帮你建立“链式存储”的直觉这是学C语言指针阶段非常重要的一次实战。链表法实现起来比数组法更容易出bug主要坑在“当前节点被删除后指针如何安全后移”。很多人写着写着当前节点的next已经被free了程序直接崩溃。这个我在第3部分会详细拆解。核心思路代码片段如下typedef struct node { int id; struct node *next; } Node; Node* createList(int n) { Node *head (Node*)malloc(sizeof(Node)); head-id 1; Node *prev head; for (int i 2; i n; i) { Node *p (Node*)malloc(sizeof(Node)); p-id i; prev-next p; prev p; } prev-next head; // 成环 return head; }删除过程中注意要找到当前节点的前驱否则没法把前驱的next接到当前节点的next上。这正是单向链表的“痛点”。2.3 数学递推法O(n)的终极优化真正让这道题升华的是数学解法。约瑟夫环问题有一个经典递推公式。为了方便推导先把编号转换成从0开始记为f(n)表示“n个人围成一圈、顺时针编号0到n-1、从0号开始报数每次报到k的人出圈”时最后留下的人的编号。已知f(1) 0因为只有一个人时他直接就是幸存者。对于n1第一轮淘汰的是编号为(k-1) mod n的人因为从0开始数报到k的是第k个人编号k-1。淘汰之后圈子里剩n-1个人此时从编号为k的位置开始重新报数这就相当于把问题规模缩小到了n-1个人但原来编号到新编号的映射发生了变化。如果我们已经知道n-1规模下的幸存者编号是f(n-1)那么把它映射回n个人的编号就是f(n) (f(n-1) k) mod n这个递推式是从小到大递推的。练习43里k3那么f(1) 0f(2) (0 3) % 2 1f(3) (1 3) % 3 1f(4) (1 3) % 4 0f(5) (0 3) % 5 3最后结果加1所以n5时答案是4和手算一致。这个解法的时间复杂度只有O(n)而且不需要额外数组或链表几行代码就搞定。真正遇到大数据量比如n10^7只有这个法子能扛得住。它告诉我们算法优化的尽头往往不是“更快的模拟”而是“找出规律放弃模拟”。int josephus_math(int n, int k) { int survivor 0; // f(1) for (int i 2; i n; i) { survivor (survivor k) % i; } return survivor 1; // 转回1-based编号 }3. 实操过程与核心环节实现我带着调试一步步写3.1 数组模拟法的完整代码与内存技巧如果你刚开始练我建议先把数组模拟法完整写出来编译通过跑几个测试样例。下面是一份可以直接复制到IDE里运行的完整代码我把注释写得很细。#include stdio.h // 约瑟夫环数组模拟法 // n总人数k报数到k出圈 // 返回值最后幸存者的编号1~n int JosephusArray(int n, int k) { int state[1000] {0}; // 假设 n 1000 for (int i 0; i n; i) { state[i] 1; // 1表示在圈内 } int pos 0; // 当前遍历到的下标 int count 0; // 已出圈人数 int num 0; // 当前报到的数字 while (count n - 1) { if (state[pos] 1) { num; if (num k) { state[pos] 0; // 出圈 count; num 0; // 下一个人重新从1开始报 } } pos (pos 1) % n; // 环形移动 } for (int i 0; i n; i) { if (state[i] 1) { return i 1; } } return -1; // 理论不会到这 } int main() { int n; printf(请输入人数n); scanf(%d, n); printf(最后留下的是%d\n, JosephusArray(n, 3)); return 0; }用这个代码测试n5输出是4和手算一致测试n1state[0]1while循环条件count 0不成立直接返回1合理。这里有个内存技巧要提醒上面代码里state数组是定长1000如果n超过1000就会越界。在实际题目里如果n不确定最好用动态内存分配int *state (int*)malloc(n * sizeof(int));用完之后free掉。C语言里数组传参和动态分配是完全不同的审查点别在这个小地方丢分。另外这个模拟过程里“pos (pos 1) % n”是环形访问的关键。很多新手会写成“if (pos n) pos 0;”效果一样但取模写法更简洁也更容易推广到k是动态值的情况。3.2 循环链表实现时的指针陷阱链表法的完整代码要比数组法长但每一步都是对指针的锻炼。我经常跟朋友说指针这东西光看书没用自己写一版循环链表删除节点比看十遍“指针是地址”的讲义都管用。先看完整代码#include stdio.h #include stdlib.h typedef struct Node { int id; struct Node *next; } Node; // 创建包含n个节点的循环链表编号1~n Node* CreateList(int n) { Node *head (Node*)malloc(sizeof(Node)); head-id 1; Node *prev head; for (int i 2; i n; i) { Node *cur (Node*)malloc(sizeof(Node)); cur-id i; prev-next cur; prev cur; } prev-next head; return head; } int JosephusList(Node *head, int k) { Node *p head; // p 指向当前报数的人 // 当链表中还有多于一个节点时继续 while (p-next ! p) { // 数到k-1使得p停在删除节点的前驱 for (int i 0; i k - 1; i) { p p-next; } // p-next 就是要出圈的人 Node *tmp p-next; p-next tmp-next; if (tmp head) { head head-next; // 如果删的是头节点更新头 } free(tmp); // p已经从被删节点的前驱变成了被删节点后一个节点的前驱 // 仔细分析删除后p的next指向了tmp的后继p仍留在原位置 // 但下一次报数应该从tmp的后继开始所以p需要再后移一步 p p-next; } int survivor p-id; free(p); return survivor; } int main() { int n; printf(请输入人数n); scanf(%d, n); Node *head CreateList(n); printf(最后留下的是%d\n, JosephusList(head, 3)); return 0; }这段代码有几个特别容易翻车的地方我一个个说。第一个坑循环终止条件。很多人写while (p ! NULL)但循环链表里没有NULLp永远不会是NULL。正确条件应该是p-next ! p表示链表中只剩一个节点。这个节点就是幸存者。第二个坑删除后的指针移动。上面代码中p是“待删除节点的前驱”找到它后待删除节点是p-next。删除后p-next已经指向了tmp的下一个节点。此时下一次报数的起点应该是tmp的下一个节点也就是新的p-next。所以代码最后p p-next让p指向下次报数起点这是关键。如果你忘了这步下一次数数就会从错误的位置开始结果差一位。第三个坑头指针更新。如果待删除节点恰好是头节点删除后链表的头要发生变化。我在代码里加了判断if (tmp head) head head-next。其实因为最后只返回幸存者编号这个头更新对结果影响不大但如果不更新后续删除用head-id或遍历时会出现逻辑错误尤其是n1的情况直接返回head-id即可。第四个坑内存释放。循环链表的节点全部通过malloc分配最后要逐个释放。但循环链表成环释放时容易死循环。一种简单办法是在删除过程中每次出圈就free掉tmp这样到最后只剩一个节点时再free当前节点。我上面的代码就是这么做的。不要试图在程序结束时遍历整个链表释放因为你此时已经丢失了完整链表的入口。养成“谁分配谁释放删一个free一个”的习惯内存问题会少很多。3.3 数学递推法的证明与边界情况数学递推法代码虽然短但如果不理解证明过程面对变体题还是容易懵。我们从头推导一下这里我尽量说得像讲课一样清楚。假设有n个人编号从0到n-1从0号开始报数报数到k的人出圈。第一轮出圈的人是谁报到k的人编号是(k-1) mod n。因为编号从0开始0号报11号报2等到第k个报数的人编号为k-1。出圈后圈子里剩下n-1个人重新组成的“新圈子”从原来编号为k的人开始报数。我们把新圈子里的顺序重新编号为0、1、2、……、n-2那么新编号0对应旧编号k mod n新编号1对应旧编号(k1) mod n以此类推。设这n-1个人的问题里最终幸存者的新编号是f(n-1)。我们要把它转换回旧编号。因为映射关系是新编号x - 旧编号 (x k) mod n所以旧编号就是(f(n-1) k) mod n。这就是递推公式f(n) (f(n-1) k) mod n。边界情况很简单n1时只有一个0号幸存者是0所以f(1)0。如果n0含义是“没有人”在题目里没有意义直接返回0或报错。k可以大于n取模运算自动处理比如n5, k8第一轮出圈的是(8-1)%52号也就是编号2的人没问题。我初学这个公式的时候总觉得“模n”的n搞不清楚为什么不是模n-1因为我们要把n-1规模的结果映射回n规模的编号体系新编号的取值范围是0到n-2加k后可能超过n-1所以要对n取模而不是n-1。这个细节一定要想通。4. 常见问题与排查技巧实录4.1 报数起点和步长混淆这是最最常见的错误。题目说“从第一个人开始报数报到3的人退出”。很多人下意识地把第一个人对应下标0然后让下标0报“0”这就错了。正确对应是第一个人报“1”下标0对应报数1第二个人报“2”下标1对应报数2第三个人报“3”下标2对应报数3。所以第一轮出圈的是下标2而不是下标3。如果你发现n5输出是2而不是4十有八九是报数起点搞错了。我建议调试时打印每一轮的状态。比如// 假设用数组法每出圈一个人打印当前剩余状态 printf(出圈编号%d\n, pos 1);这样就能看到第一轮出圈的编号是不是3如果不是马上回头检查num的初始值。4.2 数组删除元素后索引越界有的同学为了避免状态数组直接把出圈的人从数组中“删除”也就是把后面的元素往前挪。这种做法逻辑上没错但要注意删除元素之后当前报数位置和剩余人数都变了。还是用状态数组取模最稳妥。如果真的要用“删除元素”的思路那么每删一次n要减1pos要保持在删除位置本身因为后一个元素已经补上来了报数计数也要重新归零。这里稍微一个不小心就会越界或者漏人。我之前帮学弟调过程序他把删除写成for (int j pos; j n - 1; j) { arr[j] arr[j 1]; } n--;结果发现下一轮跳过了一个人。原因就是pos指向的人被删掉后arr[pos]已经是原来的arr[pos1]但pos没有回退导致下一次报数从pos1开始跳过了补上来的人。正确做法是删除后不要移动pos或者把pos回退一格再统一for循环里加。这个问题非常经典值得记在小本本上。4.3 链表内存泄漏与空指针链表法的内存问题主要分两种。一种是忘记释放被删除节点的内存导致内存泄漏。在考试或OJ里程序运行时间短可能看不出问题但如果是长时间运行的服务程序内存会越涨越高。另一种是访问了已经被freed的节点即野指针。比如Node *tmp p-next; p-next tmp-next; free(tmp); p tmp-next; // 错误tmp已经释放tmp-next是野指针这里必须先保存后继再释放再用p-next访问后继。我写了个安全口诀“先接链再释放后移动。”也就是先让p-next指向正确节点然后free(tmp)最后移动p到p-next。代码顺序不能错。还有一个容易被忽略的问题当只有一个节点时执行删除p-next p此时for循环里如果k-1大于0p会一直绕圈永远停不下来。所以while循环条件要先判断p-next ! p只有节点数大于1才进入删除流程。4.4 大数据下性能崩溃如果题目明确说n 1000数组模拟和链表模拟都能过。但如果n到10^5数组法的循环次数大概是n*k30万次还行到10^6就是300万次也能跑但到10^7就是3000万次C语言勉强能过时间可能已经到秒级。而数学递推法O(n)只需要一千万次取模运算几乎瞬间完成。我曾经在公司内部的一次技术分享里用这个例子说明算法优化的价值一个看起来只能“硬模拟”的问题通过数学归纳能缩短几个数量级。很多人觉得这是竞赛技巧其实工作中的调度系统、随机抽样、淘汰策略都会遇到类似结构的问题。5. 从练习43延伸出去的实战思维5.1 现实场景中的约瑟夫环模型约瑟夫环不只是练习题里的数学模型它在很多场景中都有影子。比如操作系统里的进程调度多个进程循环占用CPU时间片如果有人被淘汰下一个进程继续获得时间片这和报数出圈极其相似。再比如分布式系统里的“选举”算法一轮一轮过滤节点最终留下一个协调者思路上也脱胎于这类循环淘汰模型。还有游戏里的“击鼓传花”、活动抽奖里的“每隔几个人排除一个”实际上都能抽象成约瑟夫环。我在公司实习时参与过一个内部工具的开发需要从一组测试节点中选一个“幸运节点”接受特定任务。需求是节点排成一个环每隔三个节点剔除一个最终选中的节点承担任务。当时同事准备写个while循环硬模拟我提了一句“这不就是约瑟夫环吗”然后直接用数学递推法写了十几行代码把原来的百行模拟替换掉了。领导还挺惊讶。这件事后来被我们当段子讲说“学习C语言经典100例还是有用的”。5.2 变体题目的举一反三练习43考察的是固定步长k3而且只问最后一个人。实际变体很多步长变成任意k比如报到7的人出圈那只要把代码里的3改成k即可数学公式也一样模k改成模k。从第m个人开始报数不是第1个人。此时可以先把编号平移也就是把m映射为0号或者先调用一次“旋转”再套用公式。问最后两个人是谁而不是一个人。那就不能只用一个递推变量需要同时保存倒数第二轮、倒数第三轮的结果。问第x个出圈的人是谁。这需要反过来推或者用线段树等数据结构维护。遇到变体题第一件事是把已知问题向标准约瑟夫环靠拢。比如“从第m个人开始”其实等价于“所有人编号减去m-1后再按标准问题计算最后把结果加回来”。这类平移思想在算法题里特别重要学会之后能触类旁通。5.3 我的一些个人心得练习43是我在刷C经典100例过程中“顿悟”感最强的一题。我开始只会数组模拟后来为了锻炼指针写了链表版再后来看到数学递推法整个人像被打开了一扇门。现在我给你一个很实在的建议不要只满足于跑通一种解法。拿到这道题至少写三个版本数组版、链表版、数学版互相验证结果。这个过程会让你同时复习数组、指针、循环链表、动态内存、函数封装性价比极高。调试的时候一定要准备小规模样例比如n1、n2、n5。n1是边界n2能验证你的删除逻辑n5能用手算全流程。我每次写约瑟夫环相关代码都会先用这三个样例跑一遍再上大数据。这个习惯帮我避免了很多不必要的调试时间。最后再分享一个实用小技巧如果你手头没有IDE只用一个在线C编译器建议在代码里加一个“调试模式”宏用来控制是否打印每一轮的状态。例如#define DEBUG 1 #if DEBUG printf(当前剩余); // 打印state数组 #endif开启动态打印你能清楚地看到每一步出圈编号和手算结果比对调试完把DEBUG改成0一份干净的提交版本就出来了。这个方法适合所有模拟类题目不止练习43。希望这道题能成为你C语言路上的一个坚实台阶。
C语言经典100例约瑟夫环问题：数组、链表与数学递推详解
我在刷菜鸟教程C经典100例的时候练习43给我的印象特别深。题目很短读起来像小时候玩的“丢手绢”有n个人围成一圈顺序排号从第一个人开始报数报到3的人退出圈子问最后留下的是原来第几号。可就是这么个看似简单的问题我第一次提交的代码跑出结果后用手算验证却是错的后来才发现自己在“出圈后下一个人重新从1报数”这个细节上栽了跟头。这道题在C语言经典100例里排在第43位背后其实是一个著名的数学模型——约瑟夫环问题。如果你正在学C语言、刷题库或者准备机试这道题值得你认真啃一遍。今天我就把自己从数组法、链表法到数学递推法的完整思考过程、调试心得和踩坑记录全部摊开来说。1. 练习43到底在考什么约瑟夫环问题的核心痛点1.1 题目原貌与场景还原练习43的原题描述大致是这样有n个人围成一圈顺序排号。从第一个人开始报数从1报到3凡报到3的人退出圈子问最后留下的是原来第几号的那位。输入一个正整数n输出最后留下的人的原始编号。这里有几个关键约束读题的时候必须抠清楚编号从1开始不是从0开始。报数从编号为1的人开始且第一个人报的是“1”。每报到“3”的人立刻退出圈子退出后由他下一位的人重新从“1”开始报数。整个圈子越来越小但报数方向始终不变都是顺时针。问的是“最后留下的那个人”不是“第几个被淘汰的人”。题目没有给出示例输入输出但按照约定如果n5手动画一圈1、2、3、4、5第一轮报到3的是第3号出圈接着4报15报21报3第1号出圈然后2报14报25报3第5号出圈再然后2报14报22报3第2号出圈最后剩4号。所以n5时答案应该是4。这个手动推演非常有用写代码前先在纸上过一遍能避免很多逻辑错误。1.2 为什么这道题值得反复咀嚼很多人觉得这道题只是“模拟一下循环数数”没必要大动干戈。但从C语言学习的角度看它其实把好几个硬骨头一次性集中到了一个小题目里。第一是状态维护。一个“人”在圈内还是圈外需要用变量或标志位表达这考验的是对内存和变量生命周期的理解。第二是循环与取模。圈子是环形的下标走到底之后要绕回开头取模运算在这里不是技巧而是刚需。第三是动态删除。数组里删除一个元素要移动数据链表里删除节点要改指针不同数据结构带来的实现代价完全不同。第四是数学建模。当n变成十万、一百万时模拟法很可能超时这时需要用递推公式直接算出结果这是从“码农”思维向“算法思维”转变的关键一步。所以这道题既是数组和链表的练习题也是递推和数学归纳的入门题。把它吃透比盲目闷头写十道简单的循环题更有价值。2. 三种主流解法从数组到链表再到数学公式2.1 数组模拟法最直观的入门思路数组模拟法的核心思想是“用一个人为的状态数组来标记每个人是否还在圈内”。我通常用一个int数组下标从0到n-1数组元素为1表示在圈内0表示已出圈。然后维护三个变量pos当前遍历到的下标count已经出圈的人数num当前这个人报的数从1开始数。遍历时如果state[pos]为1说明这个人还活着num加1当num等于3时把这个位置标记为0count加1同时num归0然后pos加上1并对n取模实现“绕圈”。循环一直进行直到count等于n-1此时数组中剩下的那个值为1的元素的下标加1就是答案。这个思路和日常排队报数的场景几乎一模一样非常适合刚学完数组和循环的人。它的优点是代码简单、容易调试缺点是时间复杂度是O(n*m)这里m是每次数到出圈所需的步长。当n比较大的时候比如n10000k3虽然勉强能跑但已经能感觉到明显的循环次数如果n到100万基本就跑不动了。所以数组法更适合作为理解和验证的第一版而不是最终优化方案。核心代码片段如下// n个人从1到n编号每次报到3的人出圈返回最后留下的人的编号从1开始 int josephus_array(int n, int k) { int state[1000] {0}; for (int i 0; i n; i) state[i] 1; int pos 0, count 0, num 0; while (count n - 1) { if (state[pos]) { num; if (num k) { state[pos] 0; count; num 0; } } pos (pos 1) % n; } for (int i 0; i n; i) { if (state[i]) return i 1; } return -1; }注意这里k是步长在练习43里k3。把k抽象成参数是为了后续举一反三。2.2 循环链表法更贴近真实游戏逻辑链表法的思路是把n个人串成一个单向循环链表每个节点保存一个编号。报数就是沿着链表走指针每走两步即数到3就删除当前节点然后从下一个节点继续报数。当链表中只剩下一个节点时输出它的编号。和数组法相比链表法最大的优势是“出圈”操作不需要移动数据只需要改两个指针时间复杂度是O(n*k)和数组法在一个量级但空间上要为每个节点分配额外内存。表面上看链表法没有快多少但它把“删除”这个动作变成了指针操作能够帮你建立“链式存储”的直觉这是学C语言指针阶段非常重要的一次实战。链表法实现起来比数组法更容易出bug主要坑在“当前节点被删除后指针如何安全后移”。很多人写着写着当前节点的next已经被free了程序直接崩溃。这个我在第3部分会详细拆解。核心思路代码片段如下typedef struct node { int id; struct node *next; } Node; Node* createList(int n) { Node *head (Node*)malloc(sizeof(Node)); head-id 1; Node *prev head; for (int i 2; i n; i) { Node *p (Node*)malloc(sizeof(Node)); p-id i; prev-next p; prev p; } prev-next head; // 成环 return head; }删除过程中注意要找到当前节点的前驱否则没法把前驱的next接到当前节点的next上。这正是单向链表的“痛点”。2.3 数学递推法O(n)的终极优化真正让这道题升华的是数学解法。约瑟夫环问题有一个经典递推公式。为了方便推导先把编号转换成从0开始记为f(n)表示“n个人围成一圈、顺时针编号0到n-1、从0号开始报数每次报到k的人出圈”时最后留下的人的编号。已知f(1) 0因为只有一个人时他直接就是幸存者。对于n1第一轮淘汰的是编号为(k-1) mod n的人因为从0开始数报到k的是第k个人编号k-1。淘汰之后圈子里剩n-1个人此时从编号为k的位置开始重新报数这就相当于把问题规模缩小到了n-1个人但原来编号到新编号的映射发生了变化。如果我们已经知道n-1规模下的幸存者编号是f(n-1)那么把它映射回n个人的编号就是f(n) (f(n-1) k) mod n这个递推式是从小到大递推的。练习43里k3那么f(1) 0f(2) (0 3) % 2 1f(3) (1 3) % 3 1f(4) (1 3) % 4 0f(5) (0 3) % 5 3最后结果加1所以n5时答案是4和手算一致。这个解法的时间复杂度只有O(n)而且不需要额外数组或链表几行代码就搞定。真正遇到大数据量比如n10^7只有这个法子能扛得住。它告诉我们算法优化的尽头往往不是“更快的模拟”而是“找出规律放弃模拟”。int josephus_math(int n, int k) { int survivor 0; // f(1) for (int i 2; i n; i) { survivor (survivor k) % i; } return survivor 1; // 转回1-based编号 }3. 实操过程与核心环节实现我带着调试一步步写3.1 数组模拟法的完整代码与内存技巧如果你刚开始练我建议先把数组模拟法完整写出来编译通过跑几个测试样例。下面是一份可以直接复制到IDE里运行的完整代码我把注释写得很细。#include stdio.h // 约瑟夫环数组模拟法 // n总人数k报数到k出圈 // 返回值最后幸存者的编号1~n int JosephusArray(int n, int k) { int state[1000] {0}; // 假设 n 1000 for (int i 0; i n; i) { state[i] 1; // 1表示在圈内 } int pos 0; // 当前遍历到的下标 int count 0; // 已出圈人数 int num 0; // 当前报到的数字 while (count n - 1) { if (state[pos] 1) { num; if (num k) { state[pos] 0; // 出圈 count; num 0; // 下一个人重新从1开始报 } } pos (pos 1) % n; // 环形移动 } for (int i 0; i n; i) { if (state[i] 1) { return i 1; } } return -1; // 理论不会到这 } int main() { int n; printf(请输入人数n); scanf(%d, n); printf(最后留下的是%d\n, JosephusArray(n, 3)); return 0; }用这个代码测试n5输出是4和手算一致测试n1state[0]1while循环条件count 0不成立直接返回1合理。这里有个内存技巧要提醒上面代码里state数组是定长1000如果n超过1000就会越界。在实际题目里如果n不确定最好用动态内存分配int *state (int*)malloc(n * sizeof(int));用完之后free掉。C语言里数组传参和动态分配是完全不同的审查点别在这个小地方丢分。另外这个模拟过程里“pos (pos 1) % n”是环形访问的关键。很多新手会写成“if (pos n) pos 0;”效果一样但取模写法更简洁也更容易推广到k是动态值的情况。3.2 循环链表实现时的指针陷阱链表法的完整代码要比数组法长但每一步都是对指针的锻炼。我经常跟朋友说指针这东西光看书没用自己写一版循环链表删除节点比看十遍“指针是地址”的讲义都管用。先看完整代码#include stdio.h #include stdlib.h typedef struct Node { int id; struct Node *next; } Node; // 创建包含n个节点的循环链表编号1~n Node* CreateList(int n) { Node *head (Node*)malloc(sizeof(Node)); head-id 1; Node *prev head; for (int i 2; i n; i) { Node *cur (Node*)malloc(sizeof(Node)); cur-id i; prev-next cur; prev cur; } prev-next head; return head; } int JosephusList(Node *head, int k) { Node *p head; // p 指向当前报数的人 // 当链表中还有多于一个节点时继续 while (p-next ! p) { // 数到k-1使得p停在删除节点的前驱 for (int i 0; i k - 1; i) { p p-next; } // p-next 就是要出圈的人 Node *tmp p-next; p-next tmp-next; if (tmp head) { head head-next; // 如果删的是头节点更新头 } free(tmp); // p已经从被删节点的前驱变成了被删节点后一个节点的前驱 // 仔细分析删除后p的next指向了tmp的后继p仍留在原位置 // 但下一次报数应该从tmp的后继开始所以p需要再后移一步 p p-next; } int survivor p-id; free(p); return survivor; } int main() { int n; printf(请输入人数n); scanf(%d, n); Node *head CreateList(n); printf(最后留下的是%d\n, JosephusList(head, 3)); return 0; }这段代码有几个特别容易翻车的地方我一个个说。第一个坑循环终止条件。很多人写while (p ! NULL)但循环链表里没有NULLp永远不会是NULL。正确条件应该是p-next ! p表示链表中只剩一个节点。这个节点就是幸存者。第二个坑删除后的指针移动。上面代码中p是“待删除节点的前驱”找到它后待删除节点是p-next。删除后p-next已经指向了tmp的下一个节点。此时下一次报数的起点应该是tmp的下一个节点也就是新的p-next。所以代码最后p p-next让p指向下次报数起点这是关键。如果你忘了这步下一次数数就会从错误的位置开始结果差一位。第三个坑头指针更新。如果待删除节点恰好是头节点删除后链表的头要发生变化。我在代码里加了判断if (tmp head) head head-next。其实因为最后只返回幸存者编号这个头更新对结果影响不大但如果不更新后续删除用head-id或遍历时会出现逻辑错误尤其是n1的情况直接返回head-id即可。第四个坑内存释放。循环链表的节点全部通过malloc分配最后要逐个释放。但循环链表成环释放时容易死循环。一种简单办法是在删除过程中每次出圈就free掉tmp这样到最后只剩一个节点时再free当前节点。我上面的代码就是这么做的。不要试图在程序结束时遍历整个链表释放因为你此时已经丢失了完整链表的入口。养成“谁分配谁释放删一个free一个”的习惯内存问题会少很多。3.3 数学递推法的证明与边界情况数学递推法代码虽然短但如果不理解证明过程面对变体题还是容易懵。我们从头推导一下这里我尽量说得像讲课一样清楚。假设有n个人编号从0到n-1从0号开始报数报数到k的人出圈。第一轮出圈的人是谁报到k的人编号是(k-1) mod n。因为编号从0开始0号报11号报2等到第k个报数的人编号为k-1。出圈后圈子里剩下n-1个人重新组成的“新圈子”从原来编号为k的人开始报数。我们把新圈子里的顺序重新编号为0、1、2、……、n-2那么新编号0对应旧编号k mod n新编号1对应旧编号(k1) mod n以此类推。设这n-1个人的问题里最终幸存者的新编号是f(n-1)。我们要把它转换回旧编号。因为映射关系是新编号x - 旧编号 (x k) mod n所以旧编号就是(f(n-1) k) mod n。这就是递推公式f(n) (f(n-1) k) mod n。边界情况很简单n1时只有一个0号幸存者是0所以f(1)0。如果n0含义是“没有人”在题目里没有意义直接返回0或报错。k可以大于n取模运算自动处理比如n5, k8第一轮出圈的是(8-1)%52号也就是编号2的人没问题。我初学这个公式的时候总觉得“模n”的n搞不清楚为什么不是模n-1因为我们要把n-1规模的结果映射回n规模的编号体系新编号的取值范围是0到n-2加k后可能超过n-1所以要对n取模而不是n-1。这个细节一定要想通。4. 常见问题与排查技巧实录4.1 报数起点和步长混淆这是最最常见的错误。题目说“从第一个人开始报数报到3的人退出”。很多人下意识地把第一个人对应下标0然后让下标0报“0”这就错了。正确对应是第一个人报“1”下标0对应报数1第二个人报“2”下标1对应报数2第三个人报“3”下标2对应报数3。所以第一轮出圈的是下标2而不是下标3。如果你发现n5输出是2而不是4十有八九是报数起点搞错了。我建议调试时打印每一轮的状态。比如// 假设用数组法每出圈一个人打印当前剩余状态 printf(出圈编号%d\n, pos 1);这样就能看到第一轮出圈的编号是不是3如果不是马上回头检查num的初始值。4.2 数组删除元素后索引越界有的同学为了避免状态数组直接把出圈的人从数组中“删除”也就是把后面的元素往前挪。这种做法逻辑上没错但要注意删除元素之后当前报数位置和剩余人数都变了。还是用状态数组取模最稳妥。如果真的要用“删除元素”的思路那么每删一次n要减1pos要保持在删除位置本身因为后一个元素已经补上来了报数计数也要重新归零。这里稍微一个不小心就会越界或者漏人。我之前帮学弟调过程序他把删除写成for (int j pos; j n - 1; j) { arr[j] arr[j 1]; } n--;结果发现下一轮跳过了一个人。原因就是pos指向的人被删掉后arr[pos]已经是原来的arr[pos1]但pos没有回退导致下一次报数从pos1开始跳过了补上来的人。正确做法是删除后不要移动pos或者把pos回退一格再统一for循环里加。这个问题非常经典值得记在小本本上。4.3 链表内存泄漏与空指针链表法的内存问题主要分两种。一种是忘记释放被删除节点的内存导致内存泄漏。在考试或OJ里程序运行时间短可能看不出问题但如果是长时间运行的服务程序内存会越涨越高。另一种是访问了已经被freed的节点即野指针。比如Node *tmp p-next; p-next tmp-next; free(tmp); p tmp-next; // 错误tmp已经释放tmp-next是野指针这里必须先保存后继再释放再用p-next访问后继。我写了个安全口诀“先接链再释放后移动。”也就是先让p-next指向正确节点然后free(tmp)最后移动p到p-next。代码顺序不能错。还有一个容易被忽略的问题当只有一个节点时执行删除p-next p此时for循环里如果k-1大于0p会一直绕圈永远停不下来。所以while循环条件要先判断p-next ! p只有节点数大于1才进入删除流程。4.4 大数据下性能崩溃如果题目明确说n 1000数组模拟和链表模拟都能过。但如果n到10^5数组法的循环次数大概是n*k30万次还行到10^6就是300万次也能跑但到10^7就是3000万次C语言勉强能过时间可能已经到秒级。而数学递推法O(n)只需要一千万次取模运算几乎瞬间完成。我曾经在公司内部的一次技术分享里用这个例子说明算法优化的价值一个看起来只能“硬模拟”的问题通过数学归纳能缩短几个数量级。很多人觉得这是竞赛技巧其实工作中的调度系统、随机抽样、淘汰策略都会遇到类似结构的问题。5. 从练习43延伸出去的实战思维5.1 现实场景中的约瑟夫环模型约瑟夫环不只是练习题里的数学模型它在很多场景中都有影子。比如操作系统里的进程调度多个进程循环占用CPU时间片如果有人被淘汰下一个进程继续获得时间片这和报数出圈极其相似。再比如分布式系统里的“选举”算法一轮一轮过滤节点最终留下一个协调者思路上也脱胎于这类循环淘汰模型。还有游戏里的“击鼓传花”、活动抽奖里的“每隔几个人排除一个”实际上都能抽象成约瑟夫环。我在公司实习时参与过一个内部工具的开发需要从一组测试节点中选一个“幸运节点”接受特定任务。需求是节点排成一个环每隔三个节点剔除一个最终选中的节点承担任务。当时同事准备写个while循环硬模拟我提了一句“这不就是约瑟夫环吗”然后直接用数学递推法写了十几行代码把原来的百行模拟替换掉了。领导还挺惊讶。这件事后来被我们当段子讲说“学习C语言经典100例还是有用的”。5.2 变体题目的举一反三练习43考察的是固定步长k3而且只问最后一个人。实际变体很多步长变成任意k比如报到7的人出圈那只要把代码里的3改成k即可数学公式也一样模k改成模k。从第m个人开始报数不是第1个人。此时可以先把编号平移也就是把m映射为0号或者先调用一次“旋转”再套用公式。问最后两个人是谁而不是一个人。那就不能只用一个递推变量需要同时保存倒数第二轮、倒数第三轮的结果。问第x个出圈的人是谁。这需要反过来推或者用线段树等数据结构维护。遇到变体题第一件事是把已知问题向标准约瑟夫环靠拢。比如“从第m个人开始”其实等价于“所有人编号减去m-1后再按标准问题计算最后把结果加回来”。这类平移思想在算法题里特别重要学会之后能触类旁通。5.3 我的一些个人心得练习43是我在刷C经典100例过程中“顿悟”感最强的一题。我开始只会数组模拟后来为了锻炼指针写了链表版再后来看到数学递推法整个人像被打开了一扇门。现在我给你一个很实在的建议不要只满足于跑通一种解法。拿到这道题至少写三个版本数组版、链表版、数学版互相验证结果。这个过程会让你同时复习数组、指针、循环链表、动态内存、函数封装性价比极高。调试的时候一定要准备小规模样例比如n1、n2、n5。n1是边界n2能验证你的删除逻辑n5能用手算全流程。我每次写约瑟夫环相关代码都会先用这三个样例跑一遍再上大数据。这个习惯帮我避免了很多不必要的调试时间。最后再分享一个实用小技巧如果你手头没有IDE只用一个在线C编译器建议在代码里加一个“调试模式”宏用来控制是否打印每一轮的状态。例如#define DEBUG 1 #if DEBUG printf(当前剩余); // 打印state数组 #endif开启动态打印你能清楚地看到每一步出圈编号和手算结果比对调试完把DEBUG改成0一份干净的提交版本就出来了。这个方法适合所有模拟类题目不止练习43。希望这道题能成为你C语言路上的一个坚实台阶。
