★ FEATURED ARTICLE 1. 题目拆解与第一版思路1.1 这道题到底在考什么先说结论这道题表面上是“求和”实际上是在考三件事——读懂输入输出格式、正确处理多组数据、以及从“能跑”到“跑得稳”的思维升级。标题里写的是“2.4 问题 A: 例题5-1-1 连续自然数求和”我一开始想得很简单不就是从1加到N吗循环累加就完事了。但真正动手做的时候才发现里面有不少细节值得掰开了说。题目的核心要求通常是给定一个正整数N计算1 2 3 ... N的结果并按照指定格式输出。看起来人畜无害但如果你直接写一个for循环去累加题目能过但“为什么这么写”就值得琢磨了。尤其是当N的取值范围变大、输入变成多组数据、输出格式还带换行要求时很多初学者会在这里栽跟头。我当时的第一版代码是这样的#include stdio.h int main() { int N; while (scanf(%d, N) ! EOF) { int sum 0; for (int i 1; i N; i) { sum i; } printf(%d\n, sum); } return 0; }这段代码本身没有语法错误交给系统也确实能拿满分但这里面藏着一个问题我用了int类型。如果N的上限超过一定范围累加结果会溢出那时候你跑本地测试可能没问题但提交到系统就会得到“答案错误”或者非常诡异的输出。有些基础不好的同学遇到这种情况往往会去怀疑编译器、怀疑测评系统而不是怀疑数据类型——这是经典的踩坑现场。1.2 为什么需要仔细看输入输出格式这一节的题目是“例题5-1-1”但这类题目在练习系统里的格式往往高度模板化很容易被忽略。常见的输入描述是“输入一行包含一个正整数N。”输出描述是“输出一行包含1到N的和。”这时你可能会觉得用printf直接输出就完事了。但很多练习系统的隐藏要求是——支持多组输入。也就是说评测程序可能会连续输入多行N你的程序需要逐行处理直到文件结束。如果你只写了一个scanf没有循环那么程序只能处理一行数据后面的输入全被丢弃结果自然不对。我第一次提交的时候就犯了这个问题心里想明明题目说的是“输入一个正整数”为什么要用while (scanf(...) ! EOF)后来才明白“例题”在书上可能只有一组数据但练习系统为了增加区分度往往会把“多组输入”作为默认约定。这不是刁难而是为了让你养成处理流式输入的习惯后面很多题目都会用到这个套路。如果你用的是C语言的scanf记住这个固定写法while (scanf(%d, N) ! EOF) { // 处理N }如果用的是C也可以写成while (cin N) { // 处理N }这里EOF是End of File的缩写意思是读到文件末尾时停止循环。理解了这个逻辑你就能明白为什么很多网上的代码都有这个while了。2. 从循环到公式为什么要换一种思路2.1 循环累加的时间复杂度第一种解法——循环累加——的时间复杂度是O(N)也就是说当N等于100时循环100次当N等于10万时循环10万次。这个复杂度本身不算高但问题在于如果你接受的是一组非常大的N比如10^9那么循环10亿次程序的运行时间会显著增加在严格的练习系统里很可能超时。有同学会说“老师讲过1到N的和等于N*(N1)/2为什么还要用循环”这个质疑非常对。公式法的时间复杂度是O(1)不管N多大只要算一个乘法和一个除法瞬间出结果。而且公式法还能避免循环中反复做整数加法带来的潜在溢出风险前提是选择合适的数据类型。所以这道题给我的第一个教训是拿到题目后不要急着写循环先想想有没有数学上的闭式解。编程不只是把思路翻译成代码更重要的是选择最优的思路去翻译。2.2 公式法的正确性论证等差数列求和公式大家高中都学过和S (首项 末项) × 项数 ÷ 2。对于从1到N的连续自然数首项是1末项是N项数是N所以S (1 N) × N ÷ 2。用字母表示就是S N × (N 1) ÷ 2计算时要注意运算顺序。如果你直接写成N * (N 1) / 2在C语言里是先算乘法再算除法这没问题。但如果N是奇数N 1是偶数乘积一定是偶数所以除以2能整除不会出现小数截断的问题。这一点很关键它保证了整数运算的精度。当然从理论上看公式法的确很香但在实际编程中还需要考虑另一个问题——运算过程中的数值范围。比如N是10万时N × (N 1) 10万 × 10万零1约等于10的10次方这个值已经超出了16位整数的范围但在32位int里还勉强放得下大约21亿。可如果N是10亿乘积就到了10的18次方远超出32位int连64位的long long都危险。这时候就应该考虑高精度或者取模运算了。2.3 溢出问题看起来没问题其实很致命我用一个具体的例子来说明溢出问题有多隐蔽。假设N 10000010万用循环累加最后的结果是5000050000这个数大约是50亿。在C语言的32位int中最大值大约是21.47亿所以如果你用int去存这个和就会发生有符号整数溢出。在大多数编译器和环境下溢出后的结果无法预期可能是负的也可能是一个看起来完全无关的大数但绝对不会等于正确答案。有人会问那为什么题目里给N100时我用int就能得到5050因为100太小了结果远在int范围内。这就造成了一种错觉我的代码是对的。等到评测数据中有大N时就会突然翻车。要解决这个问题有两个方向把累加变量或存储结果的变量改成long long/long long int用64位来承载大数结果。如果N可能更大比如10^18那就需要使用高精度算法或者学会在模意义下求和如果题目要求的是取模。我个人的建议是在练习阶段一律用long long来存储可能超出32位范围的变量不要吝啬那一点点内存。程序不会因为多用8个字节而变慢但会因为你省了这8个字节而输出错误答案。3. 完整实现从稚嫩到可靠的代码演进3.1 第一版能通过部分测试的循环版下面是很多初学者第一次写出来的完整代码我称之为“能跑但不够稳”的版本#include stdio.h int main() { int N; while (scanf(%d, N) ! EOF) { int sum 0; for (int i 1; i N; i) { sum i; } printf(%d\n, sum); } return 0; }这个版本的优点逻辑清晰完全按照定义来。缺点时间复杂度O(N)且int会溢出。当评测数据规模较小时它能拿满分但当N达到10^7级别时运行时间可能来到几百毫秒甚至更多某些严格的系统就会判超时。而对于更大N就会直接算错。所以这个版本并不是理想答案。3.2 第二版公式加速版把循环优化成公式之后代码变成#include stdio.h int main() { long long N; while (scanf(%lld, N) ! EOF) { long long sum N * (N 1) / 2; printf(%lld\n, sum); } return 0; }这个版本的变化主要有三点输入变量N的类型从int换成long long读取格式从%d变成%lld。求和从循环变为公式计算。输出格式从%d变成%lld。仔细看这个代码你会发现N * (N 1) / 2里的N是long long因此N 1也是long long乘积也是long long这样在大多数情况下就不会溢出了。long long能表示的最大有符号整数大约是9.2 × 10^18只要N不超过大约40亿这个公式就是安全的。如果超过问题就变得复杂通常需要高精度或取模处理但那是后话。很多同学看到这个版本会说这也太简单了吧就这么几行对真正考基本功的题目往往答案就藏在最简单的优化里但你要能想到并写对才算是真的掌握了。3.3 输出格式的精确控制这类题目的输出格式往往是“一行一个结果”多加一个空格、少打一个换行都可能导致答案错误。我见过一些同学在输出时写成printf(%lld , sum);在末尾多了一个空格结果评测系统按照严格比对的方式判错非常可惜。所以我的经验是明确题目要求的是“每个结果占一行”还是“每个结果之间用空格分隔”。如果题目没有特殊说明默认每行输出一个结果。不要在输出末尾加多余的空白字符空格、制表符都算。3.4 如果题目要求输出格式更复杂怎么办有些变体题会要求你输出类似于“12...N S”的完整等式而不是仅仅输出S。这时候我的做法是先写一个sum计算再写一个循环打印数字和加号最后单独打印等号与结果。这种题目考查的是字符串输出的细节尤其是“最后一个数后面不要有多余的加号”这种问题处理起来并不难但很考验细心。比如说要求输出“1236”这种形式你可以这样处理#include stdio.h int main() { int N; while (scanf(%d, N) ! EOF) { long long sum (long long)N * (N 1) / 2; for (int i 1; i N; i) { if (i 1) printf(); printf(%d, i); } printf(%lld\n, sum); } return 0; }这里有一个细节在打印加号时用if (i 1) printf();来实现“第一个数字前没有加号”。如果你写成printf(%d, i);那么末尾就会多一个加号格式就错了。4. 常见问题与排查技巧实录4.1 读取多组输入时程序只处理了一行现象本地输入一个N输出一个结果看起来没问题。但提交到练习系统后发现输出和标准答案对不上尤其是在多组测试数据时。原因没有用while循环处理输入程序读取第一行后就结束了。排查方法在本地创建一个文本文件里面写上多行数字然后重定向输入运行程序。观察是否输出了对应多行的结果。如果没有就去检查读取输入的循环。# 在命令行中运行示例 ./a.out input.txt这个技巧对很多题目都适用建议养成习惯。4.2 使用int导致大数结果错误现象小N测试正确大N测试WA错误答案。原因int溢出。排查方法把存储结果的变量和N的类型改成long long再看看是否正常。也可以直接在代码里打印sizeof(int)和sizeof(long long)确认当前环境的字节数。4.3 公式中除法运算符与类型混用现象N是偶数时正常N是奇数时结果多1或少1。原因算式N * (N 1) / 2如果全用整数运算顺序是先乘后除通常没问题。但如果有人写成N / 2 * (N 1)在N为奇数时N / 2会先被截断成整数导致结果偏小。所以务必要保证先乘后除不要让整数除法过早发生。4.4 输出格式多了空格或换行现象答案数值正确但格式错误。原因输出时多了空白字符。排查方法对照题目描述逐字符检查。也可以将输出重定向到文件用十六进制查看器检查行尾是否有额外的空格。4.5 常见问题速查表症状可能原因解决方案只处理一行输入缺少while循环改用while (scanf(...) ! EOF)或while (cin N)大N时答案错误变量类型过小使用long long且配合%lld奇数N结果不对除法顺序错误采用N * (N 1) / 2先乘后除输出末尾多空格多余空白字符去掉最后一个空格或通过if判断控制运行超时循环次数过多改用公式法O(1)求解4.6 排查思路的优先级我个人在遇到这类基础题出错时会按以下顺序排查先看输入读取是否正确是否用循环处理了所有输入。再看数值类型把所有可能变大的变量都换成long long。再看输出格式对照题目输出样例逐字符比对。最后才怀疑算法本身的正确性。很多初学者一错就觉得自己思路错了但实际上90%的情况是输入输出或者类型的问题。把顺序定好排查效率会高很多。5. 这道题带给我的几个扩展思考5.1 从循环到公式的思维跃迁这道题最值得记住的地方不在于代码本身而在于一种思维模式当问题规模扩大时能不能找到一种不随规模增长而消耗更多时间的做法循环累加的时间是随着N线性增长的而公式法的时间是恒定的。这叫“从O(N)到O(1)的优化”。以后你还会遇到很多类似的题目比如求等差数列前n项和、等比数列前n项和甚至矩阵快速幂本质上都是在寻找一种“绕过枚举”的方法。5.2 多组输入模式是练习系统的常见约定我在某算法练习平台上做过很多题发现一个规律如果不是特别声明“单组输入”几乎默认都要支持多组输入。尤其是书名里有“例题”的题往往就是把书上的例题搬到系统里再加几组边缘数据去测试。所以咱在写代码时第一件事就是把输入循环写好避免事后返工。5.3 数学证明可以帮助检查答案即使你决定用循环法写也可以用公式法做交叉验证。比如N100时循环结果是5050公式结果也是5050。一旦两边对不上就说明某个环节出了问题。这种“用两种方法互相验证”的习惯在以后解决复杂题目时非常有价值。5.4 建议的练习节奏如果你的时间充裕我的建议是先独立写出循环版并自我分析时间复杂度。再尝试写出公式版并思考为什么能这样做。故意把代码改成错误版本观察错误现象加深记忆。最后整理成一篇笔记把思路、代码、踩坑都记录下来。我就是这样做的。当时我还在笔记本上画了一张“从循环到公式”的对比表左边是循环版右边是公式版中间写着一行红字不要急着写代码先想清楚有没有更好的数学工具。这句话后来帮我在很多题上少走了弯路。5.5 后续可以尝试的变体练习如果你觉得这道题太简单可以试着改一下条件来做扩展训练输入N和M求从N加到M的和。输入N但要求输出1到N之间的所有偶数之和或所有奇数之和。输入N要求输出1到N的平方和。输入N但N可能是一个非常大的数比如10^18要求结果对某个大质数取模。每做一种变形你都会发现新的坑。比如求平方和就必须用公式n(n1)(2n1)/6而取模运算又要处理除法逆元的问题。这些都由今天这道“简单题”延展出来可以说是整套练习体系里非常重要的一块基石。6. 说点题外话为什么我推荐记录练习过程我会建议每个人都建一个“练习记录”哪怕只是在本地写个文件把每天做的题目、思路、代码、错误点都记录下来。理由很简单编程能力的提升不是靠刷题数量堆出来的而是靠对错题的深度复盘堆出来的。我在做这道“连续自然数求和”时记录了三段内容第一段写“我最初用了循环嵌套后来优化成公式”。第二段写“要注意long long和%lld的配合”。第三段写“多组输入与文件结束符的读法”。三个月后回头看这些记录依然有用。准备面试或考试时我不需要把整本书重新翻一遍只需看自己的记录就能快速想起常见的坑在哪里。这比单纯重刷题效率高很多。还有一个小技巧给每个错误打标签比如“类型溢出”、“输入循环缺失”、“输出格式错误”。这样一来你可以统计自己最容易在哪类问题上翻车然后针对性地练习。我统计过一次发现自己最容易犯的是输出格式错误于是后来每写一道题都会先确认输出样例的每个字符错误率立刻下降了不少。如果你刚接触这类算法题目不用怕今天的代码看起来太短。越短的代码往往意味着越凝练的思考越值得反复品味。等你把这道题吃透了再去看后面的复杂算法你会发现自己已经建立起一个很重要的底层认知程序 数据结构 算法 细心而细心往往才是决定AC与WA的分界线。
阅读完成 · 觉得有帮助？
