上周帮学弟调试上机实践的作业清单里编号2.3.4这道题一眼看去就是经典的约瑟夫环n个人围成一圈从第一个人开始报数报到m的人出圈剩下的人继续从1报数直到最后一人出圈要求输出完整的出圈顺序。学弟卡了很久本地样例能过放在在线评测平台上要么超时要么直接段错误。我把这道题完整拆了一遍从最直观的循环链表、数组标记到最后的数学递推顺便把调试过程中遇到的几个典型问题也记录下来。这篇文章就当作一次上机实践复盘给正在刷这类题的人一个参考。题目编号虽然叫2.3.4但它背后的知识密度远比看着大。一个人能不能写好这道题基本能看出他对数据结构和边界条件的掌握程度。下面我会按实际做题的顺序来讲先拆题再给三种解法和完整代码最后是调试实录和上机习惯。1. 拿到题目2.3.4先别急着敲代码1.1 题目到底在问什么上机实践题最容易犯的错误就是读题太快。2.3.4这道题表面描述很常见一堆人围成圈报数报到指定数字的人出圈循环往复直到所有人出列。但这里有个关键分叉题目到底要你输出什么是每一轮出圈的完整顺序还是最后剩下的那个人我让学弟把原题截图发过来才发现题面里写的是输出出圈顺序空格分隔。这直接决定了下面用什么算法。如果只问最后幸存者数学递推一行就能算出答案如果要输出完整的出圈顺序那模拟过程基本躲不掉只能考虑模拟的常数和数据结构优化。很多人一看到围成一圈就条件反射写循环链表结果题目可能只想考递推也有些人没注意到要输出全序列直接用递推公式交上去样例自然就错了。所以拿到上机题第一步不是打开IDE而是把题目里的输入输出要求圈出来。你需要确认三件事第一输入是两个整数n和m还是有多组测试数据第二编号是从1开始还是从0开始第三输出是每行一个出圈编号还是空格分隔且行尾没有多余空格。这三个细节第一个影响程序结构第二个影响公式和取模第三个影响提交后是AC还是Presentation Error。1.2 输入输出边界比算法本身更致命上机实践题和平时写练习代码最大的区别在于评测系统只认输出不认过程。你逻辑再漂亮格式错一个字符就是零分。我整理了一下这道题常见的边界场景建议写代码之前先想清楚n等于1时程序能不能直接输出这个人的编号不进入删除循环。m等于1时出圈顺序就是1到n但链表删除时会涉及前驱节点指针处理不当就段错误。m远大于n时比如n等于5、m等于100报数会绕很多圈模拟代码如果直接数到100效率在数据量大时会变差需要取模优化。多组输入时链表创建的节点要释放干净避免内存泄漏。这些边界不提前列出来在本地测试时很难发现因为人手工测试通常只会输入正常的n和m。可评测系统不一样它会在后台塞一大堆极端数据。我自己做上机题的习惯是读完题先写一版测试用例清单至少包含最小规模、最大规模、单组数据、多组数据、m等于1、m大于n、m和n相等。有了这个清单代码写完直接按清单跑一遍大部分低级错误在提交之前就能拦住。1.3 从题目描述抽象出数据结构约瑟夫环的抽象过程其实很有意思。人围成一圈本质是一个循环序列出圈操作本质是从序列里删除一个元素然后从下一个位置继续计数。这里有两个数据结构选择方向如果删除是核心操作链表在理论上是最高效的因为删除节点只需要改指针时间复杂度O(1)。但实际代码里数组的连续内存访问对CPU缓存更友好在n比较小的时候数组实现的常数往往比链表还小。所以不要一上来就围成一圈等于循环链表。你需要先评估n的取值范围。如果n不超过1万数组模拟完全够用如果n到10万、100万级别链表模拟的时间会明显上升如果题目只是问最后幸存者那直接走数学路线。数据结构选型永远跟着数据规模走而不是跟着题目描述走。我见过太多人在链表和数组之间反复横跳最后代码还没写对。上机的原则很简单先在草稿纸上把数据规模、算法复杂度、代码难度这三者比较一遍再动手。2. 循环链表模拟最贴合直觉但指针坑最多2.1 为什么教科书都选循环链表在数据结构的教材里约瑟夫环几乎必配循环链表。原因是这个数据结构跟题目描述是直译的几个人围成一圈链表尾节点指向头节点出圈就是删除节点从下一个继续就是从删除节点的后继继续。对学生来说理解起来几乎没有门槛。但直译不代表好写。循环链表最烦的地方在于删除一个节点必须知道它的前驱节点而单链表找前驱需要从头遍历。网上很多版本是用双指针同时在链表上移动一个指向当前节点一个指向前驱这本身没问题可一旦遇到m等于1这种特殊情况pre指针还没初始化就直接解引用程序就炸了。我调试学弟代码的时候第一个崩溃点就出现在这里。2.2 完整实现与删除逻辑下面这份代码是我调试后整理的版本思路是创建循环链表后用一个tail指针指向尾节点让pre初始指向tailcur初始指向head。这样pre天然就是cur的前驱不管m等于几都不会出现前驱为空的情况。#include stdio.h #include stdlib.h typedef struct Node { int data; 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-data i; p-next NULL; if (head NULL) { head p; } else { tail-next p; } tail p; } tail-next head; return head; } void josephusList(int n, int m) { Node *head createCircle(n); Node *pre head; while (pre-next ! head) { pre pre-next; // 让 pre 指向尾节点 } Node *cur head; while (cur-next ! cur) { for (int i 1; i m; i) { pre cur; cur cur-next; } printf(%d , cur-data); pre-next cur-next; Node *tmp cur; cur cur-next; free(tmp); } printf(%d\n, cur-data); free(cur); } int main() { int n, m; while (scanf(%d%d, n, m) ! EOF) { josephusList(n, m); } return 0; }这段代码的关键细节有两个。第一个是pre的初始化不能是NULL必须指向cur的前驱也就是链表尾节点。第二个是删除时的顺序先把pre-next指向cur-next把cur从链表里摘掉然后让cur指向下一个节点最后再free(tmp)这样cur在逻辑上已经移动到出圈节点的下一个位置符合从下一个人重新报数的规则。2.3 实测结果和时间复杂度账用n5、m3测试输出是3 1 5 2 4和手算结果一致再用n10、m3测试输出3 6 9 2 7 1 8 5 10 4也没问题。看起来挺美但时间复杂度其实不低。每次删除一个节点都要在循环链表里走m步总共要删除n-1个节点所以整体复杂度是O(n*m)。如果n是1万、m是1万就需要执行1亿次指针移动在OJ上很可能超时。这个问题在学弟第一次提交时立刻暴露了。他用的数据范围是n不超过10万、m不超过10万链表版跑了大概几秒钟评测系统直接判TLE。这不是代码写错是算法选型错了。遇到这种数据规模用链表模拟本质是拿一个O(n*m)的算法去挑战大数据时间必然扛不住。3. 数组标记法上机时更快写完的方案3.1 用状态数组模拟报数过程链表会超时一个自然的改进是用数组。数组版不需要动态分配内存也不需要维护指针关系只需要一个int数组标记每个人是否已经出圈。0表示在圈内1表示已经出圈然后用一个pos变量记录当前报数位置。上机写这种题数组版比链表版快得多因为它的思维模型更贴近报数这个动作人还在圈内计数器就加一计数器到达m时当前位置的人出圈改成标记1然后pos从下一个人继续走遇到已经是1的跳过。#include stdio.h #include string.h int main() { int n, m; scanf(%d%d, n, m); int a[100005] {0}; // 0 表示在圈内1 表示已出圈 int count n; int pos 0; // 数组下标代表编号 pos1 while (count 0) { int step 0; while (step m) { if (a[pos] 0) { step; if (step m) break; } pos (pos 1) % n; } a[pos] 1; printf(%d , pos 1); count--; if (count 0) { while (a[pos] 1) { pos (pos 1) % n; } } } printf(\n); return 0; }这个版本逻辑上最接近人的思考过程。注意pos从0开始输出编号时加1。出圈一个人之后count减1然后pos要移动到下一个仍在圈内的位置确保下一轮报数从正确的人开始。3.2 链表与数组上机时到底选哪个我整理了一张对比表直接列一下两种模拟方案在实践中的差异对比维度循环链表数组标记代码长度较长需要建链表和释放节点较短逻辑集中在报数循环里删除操作改指针O(1)标记数组元素O(1)找下一个位置指针天然指向后继需要取模跳过已出圈位置调试难度指针漂移、段错误频发主要注意下标越界和取模数据规模小时代码复杂度高于收益简单直接推荐数据规模很大时若只求幸存者仍低效模拟依然是O(n*m)不解决问题从我的经验看上机实践题只要n在10万以内、m也不大数组版是最稳的选择。它在足够多的测试数据下能顺利通过且写起来快万一出问题也容易定位。但如果你已经预估到n和m都是百万级别那无论链表还是数组O(n*m)的复杂度都兜不住这时候必须换数学方案。3.3 数组版的一个隐蔽效率问题数组版虽然代码简单但有个细节容易被忽略当大量人已经出圈后pos每走一步都要判断当前位置是否已经出圈如果出圈人数多这一步可能连续跳过很多位置。极端情况下比如最后只剩一个人而这个人前面全是出圈标记程序就要绕一整圈才能找到他。这个额外开销累加起来最坏情况下仍然接近O(n*m)。所以数组版并不是银弹。它适合的是数据规模中等、需要完整输出出圈顺序的题目不能指望它通吃所有测试点。我在第5节调试实录里会专门提到一个因为取模和跳过逻辑写错导致的死循环就是数组版这个跳过已出圈位置环节出的问题。4. 递推公式只求幸存者的O(n)解法4.1 为什么要把模拟扔掉有些约瑟夫环的题只问一个东西最后剩下的人是谁。比如求幸存者的编号输入n和m输出最后留下的人。遇到这种变体模拟就完全是一种浪费了因为模拟过程中输出了大量中间状态而这些状态题目根本不需要。这道2.3.4题目虽然要求输出完整出圈顺序但很多上机题是从它改编的改法就是去掉输出顺序这一步。我建议把递推解法也彻底吃透因为同样的知识点换个问法就变一道新题。数学解法的核心是递推关系。把问题看成n个人从0到n-1编号m为报数上限。定义一个函数f(n, m)表示n个人时最后幸存者的编号0-based关键就是找到f(n, m)和f(n-1, m)之间的关系。4.2 递推关系的完整推导先看第一轮。n个人编号0到n-1从0开始报数报到m-1的人出圈也就是编号为(m-1) % n的人被删除。这个编号为什么取模因为m可能比n大报数过程中会绕圈第一轮出圈的编号就是m-1对n取余。删除这个人之后剩下n-1个人他们重新从出圈者的下一个人开始报数。现在做一次重新编号把出圈者后面的那个人记为新的0号那么新旧编号之间有一个固定映射关系旧编号 新编号 m % n这个映射可以从一个简单例子里验证。假设n5、m3第一轮出圈的是编号2。出圈后剩下的4个人按顺序是3、4、0、1重新编号成0、1、2、3。旧编号3对应新编号0而(03)%53旧编号0对应新编号2而(23)%50。恰好吻合。所以n个人时的幸存者就是n-1个人时的幸存者先映射回原编号。递推式写出来就是f(1, m) 0f(i, m) (f(i-1, m) m) % i这里的i从2循环到n变量名写小写i更容易理解因为取模的模数也在变化当人数是i时编号范围是0到i-1所以取模i。4.3 迭代实现与编号陷阱有了递推式代码只需要几行#include stdio.h int main() { long long n, m; scanf(%lld%lld, n, m); long long ans 0; // 1个人时的幸存者0-based for (long long i 2; i n; i) { ans (ans m) % i; } printf(%lld\n, ans 1); // 转回1-based return 0; }有人会问为什么用long long因为题目如果给到n和m都是10的9次方这个量级ans加上m之后可能超过int的2的31次方范围虽然取模之后会变小但中间加法的瞬间会溢出。这种边界题折磨人的地方就在这你明明知道公式是对的就是因为一个int溢出答案全错。输出的时候要特别小心公式推导用的是0-based编号但题目输入输出通常用1-based编号。所以最后输出ans1。这个1是上机题的高频失分点测试样例可能恰好不暴露问题但一旦n和m的取值不同少了这1位就会导致整个结果偏移。4.4 为什么递推公式不能直接输出完整出圈顺序这道题目要求输出完整顺序递推公式不能直接做到。原因很简单递推过程中我们只保留了幸存者编号这个信息每一轮删了谁、删的顺序是什么被压缩掉了。如果想用数学方案输出完整顺序需要用树状数组或线段树维护当前圈内第k个未出圈的人这样的信息每次找第m个人然后从数据结构里删除复杂度是O(n log n)。这个方案代码量比数组模拟大不少上机考试时不建议冒险。所以完整的问题解决方案应该是分层的n很小m很小直接用数组模拟代码短容易调。n很大m也大但只问幸存者用递推公式O(n)。n很大且要求完整出圈顺序数组模拟会超时需要线段树或树状数组。先把题目要求搞清楚再决定用哪一层这才是上机实践的真正意义。5. 完整调试实录四个让我卡住的bug5.1 指针漂移导致死循环学弟第一次用链表写本地跑n5、m3是对的但跑n10、m3的时候就卡死。我帮他把循环体里加了两行printf打印pre-data和cur-data发现删除完第三个节点后pre和cur的关系突然变得错乱cur-next又指回了一个已经被free的节点。原因出在删除语句的顺序上。他原本的代码是cur cur-next; pre-next cur-next;这两句顺序一颠倒pre-next指向的已经不是原来的cur-next而是cur移动后的next等于跳过了下一个有效节点。更危险的是如果此时cur刚好是pre的后继free之后pre还保留着指向已释放内存的悬空指针下一次访问就直接段错误。修复方式就是我在第2节写的顺序先摘节点再移动cur最后释放。改成pre-next cur-next; Node *tmp cur; cur cur-next; free(tmp);这个bug的教训是链表删除操作不要凭感觉写一定要先理清谁还被需要、谁已经可以被释放。5.2 m等于1时的段错误第二个bug隐藏得更深。m等于1时每次都是当前的人直接出圈不需要走任何step。我最初看到的链表代码里pre初始化为NULL然后让pre跟着cur走m-1步。m等于1时循环一次都不执行pre还是NULL删cur的时候写pre-next cur-next就相当于往NULL地址写数据程序当场崩溃。修复的思路是永远不要让pre处于未知状态。我在最终版本里让pre初始指向尾节点也就是head的前驱这样就保证了不管m等于几pre都一定存在且是cur的前驱。这个bug也提醒我上机测试用例里一定要包含m等于1这种极端输入。它不是刁难而是考察你有没有真的理解数据结构的前驱后继关系。5.3 数组版跳过逻辑引发的死循环写完数组版后我在n10、m3的时候跑得好好的但自己加了一个n5、m100的用例程序直接卡死。排查后发现问题在跳过已出圈位置的while循环while (a[pos] 1) { pos (pos 1) % n; }这个循环如果没有终止条件理论上会在所有位置都是1的时候无限循环。正常情况下count0保证了至少有一个位置是0但如果count等于0之后再进入这个循环就会死循环。我的代码里用if(count0)做了保护但学弟版本里没做他在count减到0后仍然执行了这段跳过逻辑程序就卡死了。修复方式有两个一是在外层while循环里先判断count是否大于0二是保证出圈时如果这是最后一个人直接结束不再执行任何跳过逻辑。这也是一个典型的边界条件问题你设计的跳过逻辑要依赖圈里还有人而圈里还有人这个条件在最后一个人出圈后会变成假。5.4 行末空格引发的Presentation Error这个bug跟算法无关纯粹是输出格式。题目要求输出空格分隔的序列行末不能有多余空格。我的第一个版本在每次printf编号后都带了一个空格提交后判了Presentation Error所有输出都对但格式就是不给过。修复很简单把输出结果存到数组里最后统一输出判断当前是不是最后一个元素或者每次输出前判断计数器如果是第一个输出的编号就不打空格之后每个编号前打一个空格。后者更省内存if (first) { printf(%d, pos 1); first 0; } else { printf( %d, pos 1); }上机实战里Presentation Error看起来是小事但它会浪费你宝贵的提交机会。我后来养成一个习惯写完代码先检查所有printf凡是涉及循环输出的都问自己一句行尾到底允不允许多一个空格。6. 做完这道题我改掉了三个上机习惯这道2.3.4做完之后我自己上机的操作顺序变了不少。以前我拿到题的第一反应是这个数据结构我熟开写现在我会先做三件事。第一件事把题目的数据范围抄到草稿纸上。数据范围不是给数学题准备的是给算法选型用的。看到n不超过1000那就大胆用数组模拟看到n是10的7次方直接考虑递推或更高级的数据结构。范围稍微一变整个方案就要跟着变这是最需要提前判断的。第二件事写代码之前先列边界测试用例。我不是列给自己看的是列给代码看的。n等于1、m等于1、m大于n、n等于m这些用例在代码写完之后一分钟不到就能全部跑完但能拦住一半以上的低级错误。每次上机题卡住我都先回去看边界用例跑没跑而不是盯着主逻辑改来改去。第三件事调试的时候多用printf输出关键变量。很多同学怕printf污染代码其实上机环境里它就是最趁手的调试工具。链表指针不确定打印pre和cur的data数组下标不确定打印pos和step递推结果不对打印每一轮的ans。打印一遍问题基本就现身了。最后说一个和算法无关但很重要的心得上机实践题不像竞赛题那样追求一上来就写出最优解它更看重你解决问题的完整度。先用最直白的方式写一个能跑通小数据的版本再分析复杂度瓶颈再针对瓶颈优化这个流程比第一次就憋大招稳妥得多。2.3.4这道题从链表到数组再到递推恰好就是一条完整的上机优化路径。踩过这些坑之后我反而觉得它是那道最值得做的入门题。