
《算法笔记》2.4节的问题D题面名字叫连续自然数求和。看到这个名字很多人的第一反应是这有什么好写的但我可以负责任地告诉你这道题在OJ上的提交记录里WA和PE的比例远高于你的想象。原因很统一不是不会求和是没搞明白“多组输入”和“输出格式”这两个隐藏关卡。这篇文章以最常见的OJ版本为例——一行一个正整数读到0结束每组输出1加到n的和——把我的完整思路、三种写法的取舍以及实际提交中遇到的翻车现场从头到尾过一遍。如果你正在刷循环结构这块或者打算帮朋友讲题这篇应该能省你不少时间。1. 先把题目“翻译”成人话它到底要你做什么1.1 题面信息与常见OJ版本这个题目编号是“问题D”对应书上的“例题5-1-4 连续自然数求和”。核心描述其实就一句话输入一个正整数n输出123...n的值。但实际刷题时题面几乎都会加上“多组输入”的限制。以我这边的练习记录为例常见版本是这样的输入 5 3 0 输出 15 6也就是说每行给一个正整数n对每一行都求一遍1到n的累加和当读到一个0时整个程序结束。注意这里的0只是哨兵它不参与求和也不该输出任何结果。如果你在别的平台上看到的终止条件是读到文件尾EOF或者先给一个组数T处理逻辑其实也差不太多把外层循环的入口条件换一下就行。后文我会单独写这几种输入模式的对应写法这里先记住一个原则做题第一步永远是确认输入格式而不是急着敲代码。1.2 为什么这一节非要让你用循环连续自然数求和有一个现成公式n*(n1)/2。既然公式摆在那里为什么题目还要你写循环因为这一节的核心是循环结构这道题就是用来练“重复做加法直到满足条件”这个思维的。放在2.4这个位置它的真正价值有三层你要会用循环做固定次数的累加你要能处理多组数据也就是外层再套一个循环你要搞清楚循环变量、累加器各自的“生命周期”。换句话说一道看似无脑的求和题同时训练了循环嵌套、变量作用域和输入终止判断三大基本功。有了这个认识你就不会觉得它“太简单不值得写”了。2. 基线解法用循环老老实实累加2.1 一个能AC的标准写法先给出我当时的最终版本以C语言为例#include stdio.h int main() { int n; while (scanf(%d, n) 1 n ! 0) { long long sum 0; for (int i 1; i n; i) { sum i; } printf(%lld\n, sum); } return 0; }这段代码不长但每一行都有讲究。while (scanf(%d, n) 1 n ! 0)这一句做了两件事先尝试从标准输入读一个整数成功读到了返回值是1才继续判断这个整数是不是0。因为有短路特性只有当scanf成功时才会去碰n的值所以不会出现“没读到东西却拿垃圾值判断”的情况。long long sum 0;这一行是重中之重它写在while里面意味着每一组输入进来时sum都会被重新清零。如果把它移到while外面你会发现第二组数据的答案莫名其妙变大了。for (int i 1; i n; i)是从1加到n注意这里的等于号。我见过不少新手写成i n结果每一组输出都比正确答案少一个n。C版本其实长得差不多用scanf/printf还是cin/cout都行但OJ环境下我更推荐前者因为格式化输出可控性更好不容易出现\n被缓冲导致顺序错乱的问题#include cstdio int main() { int n; while (scanf(%d, n) 1 n ! 0) { long long sum 0; for (int i 1; i n; i) { sum i; } printf(%lld\n, sum); } return 0; }如果你用的编译器还停留在老标准不支持在for里声明变量把int i提到函数开头定义即可逻辑不变。2.2 累加器为什么必须重置把它想成水杯很多初学者第一次在这里卡住是因为不理解sum 0为什么不能只写一次。我习惯把累加器比作一个水杯。每一组输入到来就是新的一天开始你要用这个杯子重新接一杯水。如果头一天接的水不倒掉第二天再往杯子里加水杯子当然会溢出来。举个例子第一组输入n 5如果sum写在while外面且第一轮结束时sum 15第二轮输入n 3循环开始前sum还带着上一轮的15累加1 2 3 6后输出变成21而不是期望的6。这类错误在调试时的特征非常明显输出结果一次比一次大而且看起来像是“前面的和加后面的和”。只要看到这种趋势第一反应就应该是检查累加器有没有在每组循环开始前重置。2.3 为什么不建议在这里直接套公式既然有n*(n1)/2这个O(1)的公式用公式不是更“高级”吗理论上没错但放在这道题里我有两个不推荐的理由。第一练习目标没达成。这一节的考点就是循环你用公式AC了但手指并没有形成“重复累加”的肌肉记忆。后面刷质数判断、数字翻转、进制转换时哪儿都躲不开循环现在不练后面迟早要补课。第二公式有溢出隐患。n*(n1)在n稍微大一点的时候就可能超过int的表示范围。如果非要用公式写法必须是这样long long sum 1LL * n * (n 1) / 2;关键在于1LL它把整个乘法提升为long long运算避免中间结果溢出。但即便如此我在这道题上仍然建议你老老实实写循环——等你把循环练熟了公式自然也就是一行代码的事。3. 多组输入与结束判断这题真正的“暗门”3.1 四种常见输入模式对照多组输入是OJ题最常见的套路但套路也分好几种。我整理了一个对照表方便你拿到题先对号入座输入模式典型题面描述外层循环写法注意点固定组数先给T后面跟T行数据for (int t 0; t T; t)T本身不参与业务计算读到EOF不告诉你有几组一直读到文件尾while (scanf(...) ! EOF)混入非数字字符可能死循环哨兵值结束读到某个特定值如0就结束while (scanf(...) 1 n ! 0)哨兵值不计入业务先读组数再读哨兵少见但存在组合前两种注意读取顺序本题属于第三种哨兵值结束。这类题的关键是理解“0只负责叫停不负责参与计算”。3.2 scanf返回值到底是个什么这是新手最容易混淆的点值得单独拿出来讲。scanf的返回值是“成功赋值给变量的输入项个数”而不是“读到的内容本身”。什么意思当你输入0时scanf(%d, n)成功地把0放进了n这个变量它返回的是1代表“成功读取了1个整数”。所以下面这种写法是错的while (scanf(%d, n) ! 0) { // 错误示例 // 你的逻辑 }这个循环的退出条件是什么是scanf返回值等于0也就是“没能成功读取任何数据”。但当你输入0时scanf返回的是1条件1 ! 0成立循环不会结束于是程序继续执行输出一个多余的累加结果然后在等待下一次输入时卡住。正确写法应该是这样while (scanf(%d, n) 1 n ! 0) { // 你的逻辑 }先保证“成功读到了一个整数”再判断“这个整数不是0”。两个条件都满足才进入循环。多说一句为什么更推荐 1而不是! EOF因为如果输入文件里混入了非数字字符scanf会返回0! EOF这个条件依然成立循环会卡在同一个位置反复尝试读取造成死循环。而 1遇到这种情况会直接退出。纯数字输入下两者都能工作但从工程习惯上 1是更稳的写法。3.3 输出格式的空行规则连续自然数求和这道题还有一个让人崩溃的细节空行到底怎么打常见的规则有两种。规则A每组输出后面都跟一个空行包括最后一组。这种最简单直接写printf(%lld\n\n, sum);规则B只有相邻两组输出之间才有空行第一组前面和最后一组后面都不能有多余空行。这种就需要一个标记变量int first 1; while (scanf(%d, n) 1 n ! 0) { // 求和逻辑 if (first) { first 0; } else { printf(\n); } printf(%lld\n, sum); }first的作用很直白第一次进入循环时不输出前导空行后面每一组开始前先补一个空行把上一组隔开。这样首尾都不会多出空行。很多题目算法完全正确就是栽在这一个小小的空行上被OJ判成PE格式错误。千万记得先看示例输出数一数每组输出之间有没有空行最后一组后面到底要不要空行再决定用哪种写法。4. 三个现场翻车案例与排查思路4.1 案例一累加器定义在了循环外面现象输入“5 3 0”程序输出的是“15 21”而不是期望的“15 6”。错误代码长这样int n; long long sum 0; // 错误位置 while (scanf(%d, n) 1 n ! 0) { for (int i 1; i n; i) { sum i; } printf(%lld\n, sum); }根因在上面已经讲过sum没有在每组开始时清零。第二轮执行前sum还保存着第一轮的15于是第二组算出来的不是3而是15621。排查方法在printf之前加一行临时输出把每次循环开始时的sum打印出来一眼就能看到它是不是从0起步。修完之后记得把调试输出删掉。4.2 案例二把scanf返回值当成了读到的值现象输入最后一行的0之后程序不但没有结束反而多输出了一行东西然后才卡住。错误代码长这样while (scanf(%d, n) ! 0) { // 错误判断 long long sum 0; for (int i 1; i n; i) { sum i; } printf(%lld\n, sum); }前面已经在3.2详细解释过原因这里再说一个更隐蔽的连锁反应当程序读到0因为循环条件判断错误它会把这组0也当成有效数据进入循环体求了一个“1加到0”的和也就是0然后输出一个多余的0行。很多时候不是循环没退出而是退出之前先多输出了一行看起来就像输出错乱。修复方法就是把外层条件改成scanf(%d, n) 1 n ! 0或者保留EOF判断但在循环体里单独检查if (n 0) break;。4.3 案例三输出格式的空行陷阱现象在本地跑得好好的提交上去就是PE。我遇到过一个很典型的场景题目要求“每组输出之间空一行”我理解成了“每组输出后面空一行”于是每组之后都打了空行。第一组前面没有空行所以问题是最后一组后面多了一个空行。这个错误在示例输出里其实能看出来但我当时图快直接写了printf(%lld\n\n, sum)结果在严格模式的OJ上被判定为格式错误。从此我养成了一个习惯空行处理一律用first标记模板哪怕题目要求每组后面都空行我也会先明确写出“最后一组要不要空行”再选择对应方案。这类问题最难受的点在于它不是算法错不是逻辑错是纯粹的“输出契约”没对齐。解决办法只有一个——把示例输出当作合同来读空格、空行、换行都要数清楚。4.4 本地验证的“笨办法”很多WA其实不是算法问题而是自己测试数据覆盖不够。对于这道题我建议至少准备下面几组n 1边界最小情况和是1n 2验证累加逻辑和是3n 100验证大一点的数和是5050连续输入5 3 0验证多组处理和哨兵退出空输入文件里什么都没有验证程序不会输出任何东西在本地用输入重定向最接近OJ环境。Linux或macOS终端执行./a.out in.txtWindows下通常是a.exe in.txt把测试数据放进in.txt输出结果直接显示在终端里这样可以快速看到空行和换行是否符合预期。如果不想手算结果也可以写一个用公式法的“标准答案程序”生成随机n拿两个程序的输出逐行对比这就是最朴素的对拍。不过对这道题来说手动算几个样例就足够了。5. 从这道题延伸出去连续自然数求和的三个变体5.1 变体一求m到n的区间和连续自然数求和最常见的变体是不求和[1, n]而是求和[m, n]。核心写法是long long sum 0; for (int i m; i n; i) { sum i; }这里最容易错的是边界区间含不含两端。如果题目表达是“从m到n之间的所有整数”那两端都算如果写的是“大于m且小于n”那就是i m 1; i n。读题时把这个细节圈出来比写代码更重要。另一种思路是用前缀和先算[1, n]的和再减去[1, m-1]的和。注意是减到m-1不是减到m否则会把m这一项也减掉。这个思路在后面做很多数学题时都会用到值得顺手记下来。5.2 变体二奇数和与偶数和再变一下求1到n之间所有奇数的和或者所有偶数的和。最简单的写法是在循环里加判断long long oddSum 0, evenSum 0; for (int i 1; i n; i) { if (i % 2 1) { oddSum i; } else { evenSum i; } }也可以直接用步长2的写法for (int i 1; i n; i 2) oddSum i; for (int i 2; i n; i 2) evenSum i;这两种写法在本题都能AC但步长法能帮你建立“循环控制变量不一定要每次加1”的意识。后面写埃氏筛、跳跃数组时这种步长控制的思路特别常用。5.3 用break提前退出时注意跳出的是哪层循环最后一个变体如果题目要求累加过程中一旦超过某个阈值就提前停止并且输出当时加到了哪个数你可能会用到break。示例代码long long sum 0; for (int i 1; i n; i) { sum i; if (sum 10000) { printf(累加到%d时超过10000\n, i); break; } }这里有个很多人踩过的坑break只会跳出它所在的那一层循环不会跳出外层。如果程序是“多组输入每组求和”内层for里的break只是让这一组提前结束外层的while还会继续读取下一组数据。如果你希望整个程序直接结束应该用return 0或者设置一个标志变量而不是依赖break。这些变体表面上看只是换了一个累加条件但对循环控制能力的要求完全不一样。等你能连续做对这几道2.4节这关才算真正过完。最后说点个人体会我后来回看这道题最大的收获不是学会了for循环怎么写而是养成了一个习惯——拿到任何OJ题第一件事不是打开编译器而是先把输入输出格式读懂把终止条件圈出来。这个习惯让我后面刷字符串、数论题时少踩了无数坑。如果你现在正卡在某个WA上别急着怀疑人生按“输入模式 → 循环逻辑 → 输出格式”的顺序排查多半就在这三件事里。