★ FEATURED ARTICLE 最近后台私信里被问得比较多的就是某高校SSE练习平台上的“C语言编程练习”系列题尤其是练到第24题的时候不少同学在“答案错误”和“运行超时”之间反复横跳心态直接崩了。其实这道题本身并不复杂真正把人拦住的地方是两处一是对在线评测系统的读写规则不敏感二是对题目背后涉及的经典算法模型没有吃透。这篇文章就把第24题的完整拆解过程、三种主流实现方案、以及我当年踩过的坑一起整理出来给正在刷题或者准备补考的同学做个参考。这套练习题的读者画像很清晰正在学C语言的大一新生、刚开始接触在线判题系统的同学以及想从“把代码写出来”进阶到“把代码写对、写稳”的初学者。如果你已经能熟练写循环和数组那这篇文章能帮你少走很多弯路如果你还在被“为什么本地跑没问题、一提交就零分”折磨那更建议从头到尾读一遍。1. 拿到题目先别急着敲代码——先搞清楚在线评测系统怎么“打分”1.1 平台给你打分靠的是“输出比对”不是人眼很多同学第一次接触在线评测OJ系统时容易把它想象成“有老师盯着你的代码看觉得你写得不错就给分”。但实际上这类平台的全部判分逻辑只有一个用你的程序读入一批测试数据运行后产生输出再拿输出和标准答案进行逐字符比对。比对完全一致得分任何多一个空格、少一个换行、多打印一个提示语句都会直接判为“答案错误”。这意味着什么意味着你的程序不仅要在逻辑上正确还必须在输入输出的格式上分毫不差。比如题目要求“每组输出占一行行末无多余空格”你如果随意加上一句printf(结果是%d\n, ans);哪怕算对了平台也会毫不留情地给你一个零分。这道练习24我见过不少同学就是死在“自己加中文提示”上的。1.2 练习24到底考的是哪类题我们这次拿到的练习24是一道经典的“约瑟夫环”问题只不过平台把题干包装成了类似这样的描述有n个人围成一圈按顺序从1到n编号。从第1个人开始报数报到m的人出圈然后下一个人重新从1开始报数直到圈内只剩一个人为止。请输出最后剩下的那个人的编号。输入通常是两个整数n和m例如5 2要求输出最后留在圈内的人的编号。有的题目版本会要求输出完整的出圈顺序这个要看具体题干但核心模型是一样的。这道题考察的东西其实很集中数组状态标记、循环遍历、取模运算、边界条件处理以及多组数据输入的处理习惯。它不涉及高深的语法但非常考验你对“循环程序在边界情况下的表现”是否有直觉。一旦n和m给到很大或者输入数据有多组写法不够稳的人就很容易翻车。1.3 为什么这题容易被“成绩卡住”我总结了一下卡住大家的主要是三个点。第一个点是没有处理多组输入。很多同学默认程序只跑一次写一个scanf拿完数据就直接算结果平台用三组数据测试你的程序只处理完第一组就结束了判分自然崩。正确的框架是while (scanf(%d %d, n, m) ! EOF)。第二个点是数组下标混乱。题目里的人编号从1开始而C语言数组下标从0开始这两者在你反复写pos (pos 1) % n的时候特别容易缠在一起。一旦某个地方少加1或者多加1输出的答案就会整体偏移。第三个点是没有想清楚退出条件和边界情况比如n1的时候程序该怎么走、m1的时候是不是应该直接输出n、n0和m0的组合是不是题目约定的终止输入。这些零碎的小问题叠加在一起就变成了“本地测了好多次都对一提交就WA答案错误”的经典现场。2. 解法一数组模拟循环队列——最容易理解和实现2.1 核心思路与代码框架先给出一版最直白的写法用数组当“座位表”0表示人还在圈内1表示已经出圈。我们用一个指针pos在数组里循环移动边移动边报数报到m的人就置为出圈状态直到出圈人数达到n-1。#include stdio.h #define MAXN 1005 int main() { int n, m; while (scanf(%d %d, n, m) ! EOF) { // 平台通常约定 n0 且 m0 时结束输入 if (n 0 m 0) { break; } int state[MAXN] {0}; // 0 表示还在圈内1 表示已出圈 int outCount 0; // 已经出圈的人数 int curNumber 0; // 当前报到的数字 int pos 0; // 当前遍历到的下标0-based // 当圈内只剩一个人时结束 while (outCount n - 1) { if (state[pos] 0) { curNumber; if (curNumber m) { state[pos] 1; // 出圈 outCount; curNumber 0; // 下一个人重新从1开始报数 } } pos (pos 1) % n; // 循环移动 } // 找到唯一一个 state 仍为 0 的人 for (int i 0; i n; i) { if (state[i] 0) { printf(%d\n, i 1); // 下标转编号 break; } } } return 0; }这段代码读起来非常直观一个while大循环控制总体出圈进度内部用if (state[pos] 0)跳过已经出圈的人再用curNumber完成报数动作。整个流程就和一个班级围成圈报数一模一样。2.2 细节讲解为什么用取模、状态数组怎么维护新手最容易看不明白的是pos (pos 1) % n这行。它做的事情很简单当pos走到数组末尾时让它重新回到下标0从而形成“环形”效果。因为人围成一圈物理上不存在终点逻辑上就必须靠取模在数组的两端之间循环跳转。举个例子假设n5数组下标是0、1、2、3、4。当pos4时(20141)%5等于0这一下就把“第5个人报完数后下一个轮到第1个人”的语义体现出来了。如果没有取模程序会在下一轮访问下标5导致数组越界轻则读到垃圾数据重则直接段错误。状态数组的维护也很关键。state[pos] 1标记出圈之后循环里就不会再对它报数。但这里有一个很容易被忽略的点pos向前移动时并不关心当前位置的人是否已经出圈因为if (state[pos] 0)会负责跳过。也就是说这个循环是“机械地转圈”遇到空位就空转一次。对于n在几百、几千以内的数据这种做法完全没问题代码性能足够支撑。2.3 这个方法的弱点和优化空间数组模拟最大的优点是写起来快、思路清晰、不容易错特别适合考试和面试初期当保底方案。但它也有两个明显的弱点。第一个是时间复杂度偏高。每一次“有人出圈”都要从当前点位继续遍历而报数过程会反复扫过大量已经出圈的人。如果n很大、m也很大总操作次数可能达到O(n×m)在n达到几万、m达到几万时就会明显变慢平台给出的时间上限往往撑不住。第二个是空间取决于你预设的数组大小。上面代码用了MAXN 1005如果题目把n的范围扩大到10万这个数组就不够用了需要按题目要求动态调整。更稳妥的做法是使用malloc动态分配或者直接看题目数据范围来定数组大小。如果只是想把这题提交通过数组模拟通常已经够了。但如果后面还有进阶题目比如n范围达到百万级别或者m不是一个固定数而是一个数组那就得考虑接下来要讲的链表法和数学递推法了。3. 解法二链表与数学递推——两种更高阶的实现3.1 循环链表法删除节点最直观数组模拟是“原地占座”而链表法则更贴近人的直觉把所有人串成一个环报到m的人直接从这个环上摘掉。这样剩下的节点天然只在圈内没有“空转”的浪费。#include stdio.h #include stdlib.h typedef struct Node { int id; struct Node *next; } Node; int main() { int n, m; while (scanf(%d %d, n, m) ! EOF) { if (n 0 m 0) { break; } Node *head NULL, *tail NULL; // 创建循环链表 for (int i 1; i n; i) { Node *p (Node *)malloc(sizeof(Node)); p-id i; if (head NULL) { head p; } else { tail-next p; } tail p; } tail-next head; // 首尾相连成环 Node *cur head; Node *prev tail; // prev 始终指向 cur 的前一个节点 // 当链表中只剩一个节点时cur-next cur while (cur-next ! cur) { for (int i 1; i m; i) { prev cur; cur cur-next; } // 删除 cur 节点 prev-next cur-next; free(cur); cur prev-next; } printf(%d\n, cur-id); free(cur); } return 0; }这段代码里需要特别留意的是prev的维护。一开始让prev指向尾节点是因为在单链表里删除当前节点必须知道它的前驱。当cur移动到要删除的节点时prev自然就是它的前驱。删除后cur要立即跳到删掉节点的后继也就是prev-next从而保证“从下一个人开始报数”的语义。链表法的优势是语义清晰每个节点只代表一个活人没有状态数组里的“尸体占位”问题。劣势也同样明显你需要手写节点结构、动态内存申请和释放任何一个地方漏掉free就会出现内存泄漏如果n很大频繁malloc和free的开销也会拖慢程序。而且链表本身的指针操作对于刚学C语言一两个月的同学来说理解成本比数组高不少。3.2 数学递推法O(n)秒出结果的“作弊答案”如果你只是想快速通过这道题其实还有一个“不讲武德”的数学方法——约瑟夫环递推公式。它不需要模拟任何人出圈的过程直接通过一个递推算出最后幸存者的位置。递推公式长这样f(1) 0f(i) (f(i-1) m) % i这里的f(i)表示“i个人围成一圈从第0个位置开始计数时最后幸存者的下标”。注意这个下标是0-based。最终输出的时候要记得加1转成人的编号。#include stdio.h int main() { int n, m; while (scanf(%d %d, n, m) ! EOF) { if (n 0 m 0) { break; } int ans 0; // 当只有1个人时幸存者下标是0 for (int i 2; i n; i) { ans (ans m) % i; } printf(%d\n, ans 1); // 下标转编号 } return 0; }为什么这个公式成立它的核心思想是反向推导当只有1个人时幸存者当然是编号0当人数从i-1变成i时相当于在原来的答案上往后数m个人再对i取模。这是一个非常漂亮的递推理解之后你甚至会怀疑“为什么前面那些模拟方案那么绕”。这个解法的优势是时间和空间都达到极致时间复杂度O(n)空间复杂度O(1)n再大都不怕。缺点是需要先理解递推原理背下来的话遇到变种题容易出错。比如题目如果要求输出完整出圈顺序递推公式就需要改造这时回头用数组模拟反而更直接。3.3 三种解法对比与适用场景解法时间复杂度空间复杂度编写难度适用场景数组模拟O(n×m)O(n)低n、m较小考试保底方案循环链表O(n×m)O(n)中需要模拟完整删除过程数学递推O(n)O(1)低有推导门槛n很大只求最后幸存者在练习24这道题里如果平台给的n范围不超过1000数组模拟完全够用。如果你的目标是尽快写出不出错的代码优先选数组模拟如果你打算冲一冲平台的时间排名或者后面还要做约瑟夫环的变种题那递推法是必须掌握的。4. 提交前的自查从编译错误到正确输出的完整检查清单4.1 多组输入处理while(scanf(...) ! EOF)为什么这么重要SSE这类在线练习平台有个习惯一个题目往往包含多组测试数据而不是只跑一组。有的题目会在输入格式里写明“输入包含多组测试数据每组占一行”有的题目干脆不说只丢一个“测试用例超过一组”的隐藏规则。如果你不处理多组输入后果就是平台测第二组时你的程序已经退出输出只有第一组的结果最后判分直接“答案错误”。多组输入的写法基本是固定套路while (scanf(%d %d, n, m) ! EOF) { // 处理一组数据 }这里scanf的返回值是成功读入的变量个数当读到文件末尾时返回EOF循环结束。比较坑的是有些题目要求n0且m0时结束程序你要在循环体内部先判断这个条件再决定是否break而不是把n0 m0直接写进while条件里。4.2 边界条件与特殊数据n1、m1、n0 m0边界条件是一个看起来不起眼、却能直接决定生死的地方。我整理了一个自测清单建议你在提交之前无论如何先跑一遍这组数据输入1 1只有一个幸存者他的编号就是1。如果你用数组模拟可以验证outCount n - 1是否成立如果你用递推可以验证循环是否一次都不进入。输入5 1m1意味着从第一个人开始报数报到的第一个人也就是编号1直接出圈最终剩下编号5。这是检验你是否把“报数”和“跳过”逻辑搞混的好用例。输入0 0平台通常约定这表示输入结束你的程序应该正常退出而不是把n0带入计算导致除以0或下标越界。输入10 3答案是多少可以先自己算一遍再对程序输出。约瑟夫环n10、m3的经典答案我建议你用笔推理一遍这样脑子里对整个过程会有一个清晰印象。1 1 - 1 5 1 - 5 5 2 - 3 10 3 - 4最后一组10 3算出来的答案是4这也是网上流传的经典组合。如果你跑出来的结果不一样基本可以断定是对下标或报数节奏的理解出了问题。4.3 常见报错与排查对照表在线评测系统返回的报错缩写新手看了容易一头雾水。这里直接整理成一个对照表你提交后看到哪个就按对应思路去查。报错缩写含义常见原因排查方向CE编译错误语法错误、缺少头文件、变量重名看平台给出的编译器输出逐行修复WA答案错误逻辑不对或输出格式不对先跑自测用例再检查空格换行TLE运行超时算法太慢或死循环检查是否有循环无法退出考虑换算法RE运行时错误数组越界、空指针、除以零检查下标访问和边界用例MLE内存超限数组开得过大或无限创建节点缩小数组或检查链表是否有节点泄漏拿到WA时我自己的习惯是先不急着改代码而是把题目样例重新读一遍再对照输出格式逐字节比较。很多时候问题根本不在算法而在那最后一行的换行符。如果题目要求“每组输出占一行”你写成两个换行平台也会判WA。4.4 推荐的一组自测用例模板很多同学从来不在本地做测试写完直接提交这其实是刷题最大的误区。尤其对于OJ题本地自测相当于给你一次免费的纠错机会。把下面这几组数据保存成一个文本文件或者直接在控制台里手动输入逐组对比输出5 2 6 3 10 3 1 1 7 5 0 0对应期望输出为3 1 4 1 3第6组0 0结束输入。如果你的程序每一组都能对上再去提交命中的概率会高很多。如果中途某一组不对就用调试器在这组数据上打断点一步步看pos和curNumber的变化很快就能定位问题。5. 我踩过的几个坑以及一点个人建议5.1 数组越界和死循环的调试技巧这题里最容易出现的运行时错误就是数组越界。我自己当年写数组模拟版本时忘了对pos做取模结果在n5的情况下跑到下标5程序直接崩溃。平台返回RE我还一脸懵后来用调试器才发现是取模丢了。排查这类问题有个非常朴素但有效的方法在循环体里加一条临时打印比如printf(pos%d, curNumber%d, outCount%d\n, pos, curNumber, outCount);盯着这一行看它有没有变得不合理。如果pos突然超过n-1那就是取模写错了。如果outCount一直不变那就是报数逻辑里某个if分支永远没进去。还有一个隐藏很深的坑当m很大时数组模拟的循环次数会爆炸。比如n1000、m50000程序会空转几千万次平台直接报TLE。这不是你程序写错了而是算法选定错了。遇到这类数据直接换递推公式。5.2 更进一步的扩展玩法练习24过了之后你可以自己做几个小的变体训练帮助自己真正吃透约瑟夫环第一变体让m不是固定值而是一个随出圈次数变化的数组m[1]、m[2]……这时候数组模拟和链表法依然能打递推公式就需要重新推导难度立刻上一个台阶。第二变体要求输出完整的出圈顺序而不仅仅是最后幸存者。这时数组模拟反而最方便因为每次出圈的人可以直接打印递推法在这个需求下几乎没有优势。第三变体n的范围扩大到10^7。递推法仍然可以在O(n)内解决但对循环的写法要求更精细数组模拟基本上不可能通过内存限制。这才是真正检验你“有没有从模拟思维升到数学思维”的时刻。做完这些变体之后你会发现约瑟夫环背后其实是“环形结构上按规律删除元素”的一类问题而这类思想在后来的链表操作、循环队列实现、数据流淘汰算法里会反复出现。算法能力就是这么一点点练出来的练习24只是路上一个小站。5.3 一点经验体会刷这套练习最让我有感触的不是某道题多么难而是在线评测系统教会了我写代码时“一次写对”的习惯。本地编译器对格式宽容而OJ平台对格式零容忍本地跑一次能过不代表思路真的对只有把边界数据都考虑进来程序才算真正稳。每次看到自己从WA改到AC那种找回一个“隐藏小坑”的成就感其实比单纯通过考核更让人上瘾。如果你现在也被这道练习题折磨得头疼不妨先停下来把题目样例重新读三遍再用我上面给的自测用例跑一遍理清n、m、下标、输出这几条线再动手改代码。祝你这道题一发入魂也顺便把C语言的“手感”练出来后面那几道压轴的指针题还在等着你呢。
阅读完成 · 觉得有帮助？
