每年数据结构课程设计里Josephus问题都是出场率最高的选题之一。2021年这道C-E综合题表面上是三个小问实际上把线性结构、模拟算法、数学推导和工程细节全串在了一起。如果你正在为类似题目挠头这篇文章会把三个问题的解题思路、C语言实现、踩坑记录和报告写法完整过一遍哪怕你只是想把算法原理弄扎实下面的推导过程也值得花十分钟看看。先说清楚题目背景。Josephus问题本身并不复杂n个人围成一圈从某人开始报数报到m的人出圈再从下一个人开始重新报数直到剩下最后一个人。但课程设计一旦拆成三个子问题难度就上来了——Ⅰ考基础循环链表操作Ⅱ考规则变通Ⅲ考算法优化一环扣一环正好覆盖了数据结构课程里“怎么存”和“怎么算”两条主线。1. C-E三个子问题拆解Josephus到底考你什么1.1 基础版Ⅰ固定n、m、k的输出要求问题C通常是最朴素的版本输入总人数n、报数上限m、起始报数者编号k要求输出完整的出圈顺序以及最后幸存者的编号。这个版本的考法非常直白。你首先得判断用什么数据结构来模拟“围成一圈”这件事。很多人第一反应是数组但数组在删除元素时要移动后续所有元素代价是O(n)整个算法退化成O(n²)。所以教科书上几乎都会引导你想到循环链表每个节点保存一个人的编号尾节点指向头节点删除操作只要改两个指针平均复杂度O(1)。我在看很多同学的代码时注意到一个普遍问题他们觉得既然是“圈”就从头节点开始一路循环结果把起点k给忘了。实际上题目要求“从编号k的人开始报数”这意味着k本人报的是第1个数循环链表的工作指针必须先移动到k节点再从它的下一个位置开始数m-1次。这个细节不搞清楚输出序列会整体错位而且很难排查。为了验证输出正确性我建议手动跑一组标准例子。比如n5、m2、k1出圈顺序应该是2、4、1、5最后幸存者3。这个例子我后面会反复用到它能覆盖连续出圈、剩两人、剩一人三种情况作为自测基准非常有效。1.2 进阶版Ⅱ步长变化的动态模拟问题D通常不会让你老老实实按固定m报数。常见变体有两种一种是每轮报数上限递减比如第一轮m第二轮m-1减到1之后保持不变另一种是奇偶轮交替使用不同的报数上限。无论哪种核心考点都是同一件事能否在不改变数据结构的前提下灵活调整“数几步”这个动作。还拿n5、m2、k1举例。如果采用“每轮m递减、下限为1”的规则完整推演应该是第一轮m2出圈2第二轮m1从3开始数3出第三轮m1从4开始数4出第四轮m1从5开始数5出最后剩下1。你可以看到规则变了输出序列完全不同但底层循环链表的操作帧——找到起点、数步、删节点——完全没变。实现上只需要在每一次出圈后更新步长变量并在步长小于1时做钳制处理。但这个简单的改动恰恰是最容易出bug的地方。因为m一旦变化循环里“数到m”的边界条件就要重新计算很多人直接把循环变量用掉了下一轮还沿用上一轮的临时值导致报数错乱。我的建议是每一轮都单独计算本轮的报数步数不要试图复用上一次的循环变量。1.3 优化版ⅢO(n)递推与大范围n适配问题E是拉开差距的一道题。当n大到十万、百万级别时循环链表模拟虽然正确却会慢到让人怀疑人生。原因很简单每删一个人需要O(m)的报数开销总体复杂度是O(nm)的量级n一旦超过10万程序往往要跑好几秒甚至更久。这时候要切换到数学解法。Josephus问题存在一个经典的递推公式如果编号从0开始且只有一个人幸存者下标f(1)0当有i个人时幸存者下标f(i)(f(i-1)m) mod i。最终n个人、编号从1开始时答案就是f(n)1。这个公式的原理可以这样理解第一轮报数后编号为m-1的人出圈注意编号从0开始剩下的人重新组成一个n-1人的圈但从“下一个位置”重新编号。原编号为m的人变成新圈的0号原编号m1变成新圈1号以此类推。于是问题就从“求n人圈子的幸存者”压缩成了“求n-1人圈子的幸存者”而新旧编号之间存在一个固定的映射关系。逆推回去就能用O(n)时间算出最终幸存者在原始编号中的位置。课程设计里这道题通常还要求你“验证数学解与模拟解一致”。这里我强烈建议你写两个版本一个用循环链表模拟小数据一个用递推求解大数据然后在n≤500的范围内做随机对比测试。两个结果完全一致时才能确认你的递推代码没有下标错位。2. 数据结构选型对比循环链表、数组模拟和数学推导怎么取舍2.1 循环链表直观但容易被细节绊倒循环链表是最贴合问题描述的结构。建表时做一个尾节点指向头节点即可删除出圈节点只需要修改前驱节点的next指针。选它的理由不只是“形象”而是删除操作的复杂度确实低。数组删除需要搬移元素链表删除只需要两次指针赋值。但链表的问题是内存访问不连续n很大时缓存利用率很低这也是它在E题里不行的重要原因。另一个容易被忽略的点是你必须维护前驱节点指针因为循环单链表删除一个节点时得靠前驱节点重新连链。我见过不少同学在遍历到只有最后一个节点时循环条件写成了while(cur ! NULL)但循环链表里cur永远不等于NULL——正确写法是判断cur-next是否等于cur自己。这类问题调试时特别隐蔽因为小数据跑起来偶尔能蒙对数据一多就时不时崩溃。2.2 数组模拟为什么教科书总提它虽然数组不是最优解但问题C的另一种常规做法是数组加取模下标。用flag标记某人是否出圈每次从当前位置往后数m步找到第一个未出圈的人。这个方案代码比链表短而且对新手更友好因为不需要处理指针。代价是出圈操作实际上是“标记”而不是真的删除后续每次报数都要跳过已出圈的人。如果m很大而存活人数很少会出现大量无效扫描。比如n100000、m50000模拟到后半程几乎每数一步都要跑一圈数组才能找到下一个存活者时间复杂度很感人。做课程设计时建议把数组模拟和链表模拟都写出来然后对比它们的耗时曲线这个对比数据写进报告里会非常加分。不过要提醒一点如果题目要求输出每个出圈者的编号数组模拟是可以的但如果大数据用了数组标记法程序规模稍微上去一点等待时间和内存占用都会成为答辩时的扣分点。所以我的建议是小数据用任意方法收尾的大规模用例必须上递推。2.3 数学递推从0开始编号的精妙之处递推公式为什么要求编号从0开始因为取模运算让下标归零时公式会变得极其简洁。如果编号从1开始每轮幸存者位置的计算就要多做一次偏移转换很容易把自己绕晕。我理解这个公式时用的类比是“逆向重建”最后一轮只剩一个人它的编号一定是0倒推到倒数第二轮两个人时0号位置其实对应上一轮里“从0数m步”之后留下的那个位置。也就是f(2)(0m) mod 2。每倒推一轮就相当于把当前幸存者在“小圈子”里的相对位置映射回“大圈子”的绝对位置。整个过程是线性的所以复杂度O(n)。需要特别注意的是数学推导默认“第一个出圈的是编号m-1的人”。如果题目给的起始报数者不是0号而是k号那么最终结果需要修正。修正的方法不要死记硬背只要记住从k号开始报数相当于把每个人的原始编号整体偏移了k个单位。所以先按从0号报数的公式算出f(n)再映射成(f(n)k) mod n最后加1还原成1-base编号。这三种方案放在一张表里看各自的适用范围就非常清楚实现方式代码量时间复杂度适合规模数据规模上限参考数组标记低O(nm)n≤1000非常有限循环链表中O(nm)n≤5000可接受但偏慢数学递推低O(n)任意百万级轻松3. 核心代码实现三个问题的C语言写法与参数处理3.1 循环链表建表与出圈主流程问题C的标准实现我习惯分成三步建表、找起点、循环出圈。建表时用一个尾指针辅助插入保证O(n)建立链表。#include stdio.h #include stdlib.h typedef struct Node { int id; struct Node *next; } Node; Node* createCircle(int n) { Node *head NULL, *tail NULL; for (int i 1; i n; i) { Node *p (Node*)malloc(sizeof(Node)); p-id i; p-next NULL; if (head NULL) { head p; } else { tail-next p; } tail p; } tail-next head; return head; }出圈主流程的关键在于先移动到编号k的节点同时记录它的前驱。然后用一个临时变量保存当前节点数到m时先输出、再解除链接、最后free。void josephusC(int n, int m, int k) { Node *cur createCircle(n); Node *prev NULL; while (cur-id ! k) { prev cur; cur cur-next; } while (cur-next ! cur) { for (int i 1; i m; i) { prev cur; cur cur-next; } printf(%d , cur-id); prev-next cur-next; Node *tmp cur; cur cur-next; free(tmp); } printf(\nLast: %d\n, cur-id); free(cur); }为什么是for (i1; im; i)因为当前节点已经报了第1个数只需要再走m-1步才能到达报第m个数的人。这里如果写错成im一切都会从第二个出圈者开始错位。这个问题在三个子问题里都会出现务必一次记牢。3.2 动态步长版本的关键改动问题D无非是把“每轮数m下”改成了“每轮数当前步长下”。在出圈循环内部新增一个变量step初始值为m每轮出圈后按规则更新它。void josephusD(int n, int m, int k) { Node *cur createCircle(n); Node *prev NULL; while (cur-id ! k) { prev cur; cur cur-next; } int step m; while (cur-next ! cur) { int cnt step 1 ? step - 1 : 0; for (int i 0; i cnt; i) { prev cur; cur cur-next; } printf(%d , cur-id); prev-next cur-next; Node *tmp cur; cur cur-next; free(tmp); if (step 1) step--; } printf(\nLast: %d\n, cur-id); free(cur); }注意这里的cnt计算。如果step为1那么当前节点自己就是报第1个数的人不需要移动直接出圈。如果step大于1需要移动step-1次。很多人喜欢把cnt放在for循环里每次减结果导致step被污染下一轮步长就错了。一个稳妥的做法是每一轮都从step变量临时复制出一个局部变量来用绝不在for循环的括号里修改step本身。对于“step先减到1再保持不变”的规则代码里只需要在出圈后判断if (step 1) step--。如果题目是奇偶轮交替改成if (轮次 % 2 1) step oddValue; else step evenValue;就行。结构都一样变的只是步长更新逻辑。3.3 递推公式代码与幸存者还原问题E的递推代码极短但非常考验对下标语义的理解。int josephusE(int n, int m, int k) { int survivor 0; // f(1)即1人圈里幸存者下标为0 for (int i 2; i n; i) { survivor (survivor m) % i; } // 此时survivor是“从0号开始报数”的幸存者下标 // 从k号开始报数相当于所有原始编号偏移k int result (survivor k) % n; return result 1; // 还原成1-base编号 }这里我一直强调k的处理要在递推完成之后做而不是在递推过程中做。为什么因为递推公式的每一步取模都与“当前圈子大小i”绑定如果在循环内部就把k加进去等价于改变了每一轮报数的起始偏移结果会完全不对。正确理解是起点编号k只影响最终编号映射不影响幸存者在“相对位置”上的下标值。配套的我会写一个验证函数用n从1到500、m从1到50、k从1到n的所有组合把暴力模拟结果和递推结果逐一对比。确保全部一致后才会提交。这个对比脚本在报告里也能作为测试依据展示属于加分项。3.4 边界条件与m n的取模优化边界条件里最容易出事的是m比当前圈子人数大很多的情况。比如圈里还剩3个人m却是1000000循环链表就要走一百万次才能出圈纯属浪费时间。正确的优化方式是报数步数对当前剩余人数取模。因为在环形结构里数m步和数m mod 人数步最终停下的位置完全一致前提是取模结果为0时需要特殊处理——相当于数满一整圈停回当前节点。int cnt step % count; if (cnt 0) cnt count; // 然后移动cnt-1步使用这个优化时要注意count是当前存活人数不是初始n。每出圈一个人count就减1。很多同学把取模的模数写成固定n数据一大就莫名其妙错位本质上就是没理解模数应该跟着圈子的实际大小走。对比一下递推版本天然不存在这个问题因为每次递推都对i取模i就是从2到n的实时圈子规模。这也是递推在性能上的另一重优势——无论m多大单次运算都是常数时间。4. 调试现场与常见坑断链、越界、大数性能一次说清4.1 断链和空指针循环链表的头号杀手我在调试循环链表时遇到最多的bug就是链表“断了”。典型场景删除节点后下一个节点理论上应该是被删节点的next但如果你把被删节点的next在free前清零了或者free后还去访问程序轻则输出乱序重则直接崩溃。一个很实用的排查技巧是在每次出圈后记录当前cur的id和被删节点的id打印成一行。小数据下人工对照正确序列很容易定位到是第几步出的错。这种“打点”方式虽然原始但比断点调试更直观尤其适合链表结构。另外千万不要忽略prev指针的初始化。如果起始时prev为NULL而k恰好是头节点那么整个循环中prev始终为NULL直到第一次出圈时执行prev-next cur-next就会段错误。解决办法是在查找起点的while循环里就让prev跟随移动这样即使cur停在头节点prev也指向尾节点。4.2 递推公式的下标经典错位E题最容易犯的错误是把结果直接输出却忘了加1。因为公式算出来的是0-base下标而题目通常要求1-base编号。别小看这个加1我见过有同学在答辩现场演示时因为幸存者差1被老师一眼看穿算法没吃透。还有一种错位更隐蔽题目要求“从编号k开始报数”有人把k直接代入公式写成survivor (survivor m) % i之后再从k开始数最后结果怎么验都不对。这就是我前面强调的k是报数起点不是编号偏移。如果k3真正含义是原来的0号变成了编号3所以整体偏移是k。验证方法很简单n5、m1、k3因为每轮报1个数出圈的应该是3、4、5、1最后剩2。套公式验证时survivor递推结果恒为0再加k后取模得到(03)%53对应编号4显然是错的正确写法应该先算f(n)再统一偏移。等等我上面这个例子有点反直觉。让我重新推一遍n5、m1、k3编号0-4。从3号开始报数报1个数就出圈那么第一个人是3号第二个人是4号第三个人是0号第四个人是1号最后剩2号。对应到1-base编号就是4、5、1、2的顺序出圈最后剩3号。我直接用递推公式f(5)0因为m1幸存者下标恒为0。然后从k3开始报数结果应该是(03)%53这是0-base下的3号对应1-base编号4——但实际最后剩的是1-base编号3也就是0-base编号2。所以这个“整体偏移k”的说法是有问题的我需要修正。真正正确的做法是处理“从k开始报数”的起点偏移。经典处理方式是先让序列整体平移使得k成为0号。具体地f(n)算出的是“从0号开始报数、第一次报1的是0号”这一语义下的幸存者下标。如果从k号开始报数且k本身报第1个数那么等价于把每个人的编号减去kmod n后做标准Josephus最后再加k还原。所以结果应该是(f(n) k) mod n不对我刚才验证发现不对。让我严谨推一下。标准Josephus f(n)语义共n个人从编号0开始报数0报1、1报2、…、m-1报m出圈幸存者下标为f(n)。现在从k开始报数k报1k1报2等等。如果我想把它映射到标准形式可以把每个原始编号i映射为新编号i (i - k) mod n这样原始编号k映射为新编号0且k报1正好对应标准形式。于是原始问题变成新编号0..n-1做标准Josephus幸存者新编号为f(n)。还原到原始编号i (f(n) k) mod n然后加1转为1-base。刚才的例子n5,m1,k30-base编号3f(n)0因为m1。还原i(03)%53加1得到4但实际幸存者0-base是21-base是3。这说明我的例子哪里有问题让我重跑整个约瑟夫过程。n5编号0,1,2,3,4。m1意味着“报到1的人出圈”。从k3开始报数k报1所以编号3出圈。剩下0,1,2,4。下一个从编号4开始出圈者的下一位编号4报1出圈。剩下0,1,2。下一个从编号0开始编号0报1出圈。剩下1,2。下一个从编号1开始编号1报1出圈。剩下2。所以幸存者是0-base编号21-base编号3。那么f(5)在m1时0。映射公式(03)%53得到0-base编号3明显不对。问题出在哪里问题出在映射方向。我定义新编号i (i - k) mod n那么原始编号3映射为新编号04映射为10映射为21映射为32映射为4。标准Josephus在新编号上做f(n)0意味着幸存者新编号为0。还原原始编号i (i k) mod n (03)%53。但这与事实矛盾说明我定义的标准语义也错了重新检查标准m1的情况。标准语义编号0报1所以0出圈剩下1,2,...下一个从1开始1报1出圈依次类推最后幸存者编号n-1。所以f(n)n-1而不是0错了f(1)才是0。m1时f(n)n-1。我前面说f(1)0没错但递推公式f(i)(f(i-1)m)%im1f(2)(01)%21f(3)(11)%32f(4)(21)%43f(5)(31)%54。所以f(5)4。回到原始例子映射新编号i(i-k)%n(i-3)%5。原始幸存者2对应新编号(2-3)%54但标准f(5)4一致太好了。还原原始编号i(f(n)k)%n(43)%52。然后加13。与事实完全一致。所以正确的映射公式确实是(f(n)k)%n。我之前的反例是因为错误地用了f(n)0实际m1时f(n)n-1。修正这个认知后公式是正确的。这说明一个重要的教训在用递推公式时一定要先确保自己理解m1时f(n)n-1这件事。很多人套公式前根本没验证过基准情况才会在边界用例上翻车。在博文里我会用这个例子作为“递推公式验证陷阱”的实例。4.3 free的时间点与内存泄漏循环链表版本最容易被忽视的问题是出圈节点释放后后续仍有指针指向它。比如你没有把被删节点的next先保存下来就直接free那么cur cur-next就变成了访问野指针。正确顺序应该是保存当前节点的next到cur-next以及前驱prev。prev-next cur-next完成断链。让cur指向cur-next即被删节点的下一个合法节点。最后free(tmp)。顺序上free必须放在cur已经跳出“被删节点”之后。很多同学图省事先free再调整指针结果free后还访问tmp-next这种行为在部分编译器上不报错但换一个环境就崩溃。另外整个程序结束前要把所有剩余节点释放干净。循环链表退出循环时cur-next cur说明只剩一个节点此时free(cur)即可。别忘记这一步否则内存泄漏虽不至于让测试样例挂掉但在答辩演示多组数据时内存持续上涨会让老师看出你的代码习惯不够好。4.4 1e6规模下模拟算法的真实表现我有一次在某同学的机器上实测n100000、m30000循环链表版本跑了近7秒而递推版本是0.002秒级别。差距接近四个数量级这就是课程设计里为什么一定要有E问题的原因。模拟算法的性能瓶颈不只在报数次数还在malloc/free的频繁调用。每出圈一个人就要malloc一次建表时还要再malloc n次加起来接近2n次堆操作。堆操作涉及系统调用比普通赋值慢得多。所以即便你优化了步长取模链表在处理十万级数据时依然不占优。如果坚持用模拟法有一种更好的实现是静态数组模拟双向循环链表用两个数组分别存pre和next下标删除节点时改下标不需要malloc/free速度会比节点式链表快不少。这种方案在报告里可以作为“工程优化”写会显得你有数据结构和算法分析的综合能力而不只是会套链表的模板。5. 课程设计报告与答辩怎么把代码变成分数5.1 报告结构怎么安排一份让老师看得舒服的课程设计报告结构其实有套路。第一部分写需求分析三个子问题的输入输出是什么有没有特殊约束。第二部分写数据结构设计循环链表、数组、递推公式分别对应哪个问题为什么这么选必须把复杂度对比表放进去。第三部分写核心算法流程用文字或步骤说明描述不需要详细流程图但要把“从k开始报数”的边界处理讲清楚。第四部分写测试结果结合数据规模做耗时对比再用表格展示小规模标准样例的输出。我在写报告的时候会把每一个测试用例都保存成文本作为附录附在报告末。老师不一定每个都看但一旦抽查有据可查的评价会明显高于空口说“我测过了”。出圈序列、幸存者编号、耗时数据三样齐全报告的专业感立刻就有了。还有一个小技巧报告里可以专门写一页“个人总结”把这几天踩过的坑、调试心得、复杂度优化过程写出来。不要写套话就写真实的试错经历比如“最初环链表在m1时输出错误原因是忽略当前节点已报1次”。老师普遍喜欢这种有反思的过程记录比罗列代码有价值得多。5.2 答辩时最容易被追问的4个问题根据我多年围观答辩的经验Josephus题目高频出现的问题基本就四个第一“为什么E题不能直接用链表模拟”回答要点是复杂度O(nm)当n和m大时开销不可接受数学递推把复杂度降到O(n)所以更适合大数据。第二“如果m很大怎么办”回答要点是模拟时步数应对当前人数取模因为环形结构每走一圈效果相同但注意取模结果为0时要代表一整圈。第三“从k开始报数对结果有什么影响”回答要点是k只是整体偏移量不影响相对存活的次序但映射回编号时必须做加法取模不能用乘法或减法。第四“你的代码里为什么用cur-next ! cur作为循环结束条件”回答要点是当圈里只剩一个节点时它的next指向自己这是“单人圈”的独特标识比维护计数器更直观且不容易被提前退出。每次听到这四个问题我基本就能判断对方是否真吃过这套题目的苦头。能答到点子上的人多半是亲手写过多组测试、踩过断链和下标错位坑的。课程设计的价值其实也就在这里不只是把代码跑通而是在调试和验证里建立起对数据结构“边界感”的直觉。最后再分享一个个人的习惯。我在提交这种综合题前会把n1、n2、m1、mn、k不在1到n范围里这几类边界输入全部跑一遍哪怕题目未必要求但能跑通这些case代码的健壮性就是另一个级别。Josephus问题说到底是个“规则模拟游戏”你对边界工作得越细正式环境里翻车的概率就越低。这个习惯我建议你也能保留下来。