很多人在刷到“洛谷-入门3-循环结构3”这一组题的时候会产生一个很真实的怀疑循环结构我不是已经会了吗for 和 while 翻来覆去就那么几行怎么到了这一组突然就看不懂了我自己也经历过这个阶段前面那些题基本是“照着题意翻译成代码”输入什么、输出什么全都明明白白到了循环结构3题目开始变成“给你一个问题你得自己想清楚循环怎么安排”。这篇文章就围绕这一组题里最典型的几类内容展开数学建模题、数列递推题、图形打印题、模拟题把它们的通用套路和我踩过的坑一次说清楚。无论你是在哪个刷题平台上做循环专题这套思路都通用。1. 循环结构3的题到底想让你练什么1.1 它和入门1、入门2的差距在哪入门阶段的前面两组题本质上是在练“顺序执行”和“按条件分支”。循环结构的前半部分呢也还是温和的输入 n求 1 到 n 的和求最大值数一数有几个符合条件的数。这些题的代码骨架几乎是固定的一个循环、一个累加变量、一个 if写完就完事。循环结构3这批题就不太一样了。我看到的明显变化有三个循环不再只有一个。很多题需要嵌套循环外层管行、内层管列或者外层管范围、内层管枚举。双重循环一旦出现代码的复杂度立刻上了一个台阶。循环体里要做的不再只是累加。经常需要在循环里判断质数、拆分数字、统计约数甚至要在循环过程中维护好几个状态变量。题面开始涉及“数据规模”的概念。n 大的时候O(n²) 的写法会超时你得主动去想怎么少算一点。举个例子最典型的“求 n 以内的质数个数”。如果只会在主函数里写一个 for根本无从下手如果你知道要写一个函数判断质数再写一个循环枚举 1 到 n那你已经踏入“用循环表达数学模型”的门槛了。但真正让新手难受的是最后那一下如果 n 是 10 的 6 次方你每个数都从 2 试到它本身最后大概率超时。于是题目表面是循环实际却在逼你理解“约数成对出现只需要枚举到根号 n”。这就是循环结构3的定位它不是循环语法题是“循环思维题”。语法只是工具箱这一组题真正想练的是你从问题里提取规律的能力。1.2 从“写循环”到“用循环想问题”的思维转变我见过太多人卡在这一组原因不是不会写 for而是不知道 for 里面该放什么。本质上是把循环当成了一种“按顺序执行的操作”而没有把它当成一种“表达规律的工具”。循环真正的含义是用一个重复的结构去表达一个逐步推进的数学规律。序列求和是一个规律质数测试是一个规律图形中每一行的行列关系也是一个规律。做题的第一步永远是把题目里的规律翻译成“每一轮循环到底在推进什么”。这里分享一个我反复跟新手强调的方法拿到题先不要写代码先手算一个小规模样例。比如 n3 的时候把每一步变化写在纸上然后问自己两个问题每一轮循环结束后哪些变量的值发生了变化循环什么时候停下来停下来的时候哪个变量正好是我想求的答案想清楚这两点代码其实就是手算过程的机械翻译。我打一个不太严谨的比方写循环就像做菜时数土豆。你不会一只一只数完所有土豆再决定炒几盘而是一边数一边往盆里放每放一个手上计数加一。循环体就是“拿起一个土豆、计数加一”这个动作循环条件就是“盆里还有没有土豆”。循环结构3里的大量题目都是这种“一边处理、一边推进、直到满足终止条件”的模型。你一旦把思维从“写几步代码”切换成“设计一个推进过程”后面那些题会顺很多。2. 数学题型的循环建模质数、约数与公约数2.1 质数判断的写法与边界质数判断几乎是循环结构3必出场的题。先从最标准、也最常用的写法说起bool isPrime(int x) { if (x 2) return false; for (int i 2; i * i x; i) { if (x % i 0) return false; } return true; }为什么循环条件是i * i x而不是i x / 2因为约数永远是成对出现的。比如 36约数有 1 和 36、2 和 18、3 和 12、4 和 9、6 和 6。每一对里面至少有一个因子小于等于根号 36。如果从 2 一直试到根号 x 都没找到因子那后半段也不可能有因子这是一个非常省时间的结论。这里有一个我自己也犯过的边界错误把条件写成i * i x也就是漏了等号。这样对于 4、9、16 这类完全平方数恰好会漏判。为什么因为 x4 时i22*24 不成立循环直接结束4 就被当成质数了。所以我现在的习惯是要么写i * i x要么更稳妥一点写成i x / i后者还能避免i * i在 x 很大时溢出。虽然刷题平台给的数据大多不会让 int 溢出但这个习惯能帮你省掉很多莫名其妙的 RE运行错误。另一个容易被忽略的点是质数判断经常出现在循环里面。如果要求你输出 n 以内的全部质数那么外层枚举 1 到 n内层做质数判断本质上是一个双重循环。这时候外层是“范围”内层是“判定”两层各管各的不要混在一起。很多新手写半天写不出来就是因为把判定逻辑和枚举逻辑搅在了同一个循环里。2.2 枚举约数为什么用根号优化和质数判断配套出现的是“求一个数的所有约数”或者“统计约数个数”。最直观的写法当然是从 1 枚举到 n遇到 n % i 0 就记下来。但是数据一大这种写法就吃不住了。利用刚才说的约数成对性质可以砍掉一半计算量vectorint factors; for (int d 1; d n / d; d) { if (n % d 0) { factors.push_back(d); if (d * d ! n) factors.push_back(n / d); } } sort(factors.begin(), factors.end());这里有几个细节值得讲。第一d n / d和d * d n等价但前者更安全。第二当d * d n时比如 n36、d66 和 36/6 是同一个数如果两个都 push 进去最后排序完会发现 6 出现两次。所以要加一个d * d ! n的判断。这个边界例子我见过不止一个新手踩进去。第三这样收集出来的约数顺序是乱的前半段从小到大后半段从大到小。所以最后要sort一下除非题目只要求数量。如果你不想排序也可以先把前半段 push 进去再从大到小把后半段 push 进去效果一样但排序是最省脑子的写法。约数枚举还有个变体是“统计约数个数”本质上就是把 push 换成计数器加一思路完全一样。这一类题的核心目的其实是让你体会一件事循环的效率不等于循环的次数多就好能少算就少算才是这一组的进阶方向。2.3 辗转相除的循环实现公约数问题在循环结构3里通常会以“求最大公约数”的方式出现。很多语言的标准库里已经有现成的 gcd 函数但这一阶段我强烈建议你亲手写一遍。因为实现 gcd 的循环过程本身就是一个非常好的“循环不变量”教学案例。int gcd(int a, int b) { while (b ! 0) { int t a % b; a b; b t; } return a; }你可以手动走一遍gcd(12, 18)。第一轮 a18、b12假设你把大的赋给 at6a12b6第二轮 t0a6b0退出返回 6。整个过程里有一个不变的东西a 和 b 的最大公约数始终等于最开始那个 a 和 b 的最大公约数。每一步我们把 (a, b) 替换成 (b, a % b)这个替换不会改变最大公约数于是当 b 变成 0 时a 自然就是答案。从循环的角度看这个 while 和前面的 for 不一样它没有固定的循环次数循环什么时候结束取决于传入的数据。这种“循环次数不确定”的循环在循环结构3里会越来越多比如接下来的 3n1 问题也是同样的类型。你需要习惯的是for 适合“我知道要循环几次”while 适合“我知道什么时候停但不知道要循环几次”。很多新手两个用混代码就会变得非常别扭。如果你理解了 gcd顺手就能求最小公倍数 lcm公式是a / gcd(a, b) * b。注意顺序先除后乘因为a * b可能超过 int 范围而先除完再乘通常还在安全范围内。这个细节在涉及大数的循环题里非常实用。3. 数列与递推题累加累乘之外的思路3.1 数列求和的三种常见形态数列求和的题从“求 1 到 n 的和”开始很快会升级成各种形态。我总结了一下循环结构3里常见的三种第一种是直接累加比如求 1 到 n 的和一重 for 搞定。第二种是交错项求和比如 1 - 2 3 - 4 5 ...。新手第一次遇到这种题往往会想着分两个循环分别求奇数和、偶数和再相减。这当然能过但更简洁的思路是让符号跟着项数变化long long sum 0; for (int i 1; i n; i) { if (i % 2 1) sum i; else sum - i; }或者用(i % 2 ? 1 : -1)直接生成符号。这个技巧不复杂但它代表了一种意识用循环变量的奇偶性去控制“这一轮做什么动作”。第三种是“嵌套数列”比如求 1! 2! 3! ... n!。最容易想到的写法是外层循环枚举 1 到 n内层循环每次重新算一个阶乘。这个写法没错但时间浪费在重复计算上。更好的做法是让阶乘这个变量自己滚动。long long fact 1; long long sum 0; for (int i 1; i n; i) { fact * i; sum fact; }第 i 轮结束时fact 正好是 i!。因为我们知道 i! (i-1)! * i根本不需要从头再乘一遍。这个“用上一个状态推下一个状态”的思想就是后面递推题的雏形。循环结构3里有很多题表面是求和本质是在考察你有没有这种“保留中间状态”的意识。3.2 递推关系怎么用循环维护如果说累加是“往一个变量里不断加东西”那递推就是“多个变量之间不断循环更新”。最经典的例子是斐波那契数列每一项等于前两项之和。如果你只需要求第 n 项不需要开一个数组用三个变量滚动就行long long a 1, b 1, c; for (int i 3; i n; i) { c a b; a b; b c; }这个代码里最容易错的是更新顺序。你必须在算出 c 之后再把 a 和 b 往前挪。如果顺序反了比如先执行a b然后再算c a b那 c 就变成了两个旧 b 的和答案直接废掉。这里有一个辅助技巧写这种滚动更新时先想清楚“这三行代码执行完毕后a、b 各自代表第几项”把注释写到代码旁边而不是凭感觉猜。递推题在循环结构3里的另一个常见变体是杨辉三角。它本质上是二维的递推每一行的中间项等于上一行相邻两项的和。如果你学过数组这会展开成二维数组的嵌套循环如果还没学到数组可以先只观察它的行规律第 i 行的第 j 个数是组合数 C(i-1, j-1)。这时候循环结构会让你用组合数的递推公式C(n, k) C(n, k-1) * (n - k 1) / k去一行一行生成本行的所有数值。这个做法完全不用数组只用两个循环套着。递推题的共性就一句话新的状态只依赖旧的几个状态用变量把这些状态保存下来在循环里同步更新。3.3 取模与溢出的时机数列累加累乘类的题目经常会在最后加一句“结果对 1000000007 取模”。很多新手会想我先把真实结果算出来最后再取模不就行了问题是中间结果可能早就爆了。举个例子n20 时 20! 大约是 2.4e18已经接近 long long 的上限n30 时早就溢出了。所以只要题目要求取模就应该每一步都取模const long long MOD 1000000007; long long fact 1; long long sum 0; for (int i 1; i n; i) { fact fact * i % MOD; sum (sum fact) % MOD; }这里背后是模运算的分配律(a * b) % MOD 等于 (a % MOD) * (b % MOD) 再取模。加法同理。所以每一步取模不会改变最终结果反而能保证中间值始终在一个安全的范围内。这属于那种“知道原理之后永远不会再错”的知识点但第一次遇到时几乎人人都会踩一下。还有一类题是“求 1 到 n 的和”当你发现 n 非常大比如 10^9 量级的时候for 循环根本跑不完。这时候要学会用等差数列求和公式直接算。这可能听起来不像“循环结构”该管的事但它恰恰是这一组想传达的另一层意思循环不是万能的当数学公式能代替循环时优先用公式。做题时先看一眼数据范围再决定是开循环还是开公式这个习惯越早养成越好。4. 嵌套循环打印图形把坐标当规律4.1 行列与坐标 (i, j) 的对应关系图形打印题是很多新手的噩梦但也是最容易打通的题型。核心套路只有一个把输出想象成一个二维字符矩阵第 i 行第 j 列的位置上要么是字符要么是空格然后找出“什么时候填字符、什么时候填空格”的规律。拿最基础的直角三角形来说* ** *** ****第 1 行有 1 个星号第 2 行有 2 个第 i 行有 i 个。对应到循环就是外层循环 i 从 1 到 n内层循环 j 从 1 到 i每次输出一个星号一行结束输出换行。for (int i 1; i n; i) { for (int j 1; j i; j) { cout *; } cout \n; }这个代码看着简单但它里面有一个所有图形题都通用的“黄金法则”外层循环管行数内层循环管这一行里要输出的字符个数而内层循环的结束条件通常和当前外层变量 i 有关。一旦你能把“第 i 行输出几个字符”想清楚三角形、正方形、倒三角就都没问题了。如果遇到需要判断位置填什么的题比如实心菱形内部的每一行就不要再想着“一行一行写死”而是把位置当成坐标用 (i, j) 去套一个条件表达式。哪个方向对称就加哪个方向的绝对值哪个方向偏移就减哪个方向的偏移。图形题刷到后面其实就是解不等式。4.2 空格的坑空格也是输出内容打印图形最常见的翻车点不是星号是空格。很多人把空格当成“看不见就不存在”结果输出完全错位。来看菱形。假设你要输出一个 n3 的菱形* *** ***** *** *每一行实际是由两部分组成的前面若干空格加上后面若干星号。空格数量是可见的字符必须单独用一个内层循环输出。上半部分第 i 行的空格数是 n - i星号数是 2*i - 1。下半部分是从 n-1 到 1 倒过来行号 i 逐渐变小但空格和星号的公式不变。// 上半部分 for (int i 1; i n; i) { for (int j 1; j n - i; j) cout ; for (int j 1; j 2 * i - 1; j) cout *; cout \n; } // 下半部分 for (int i n - 1; i 1; i--) { for (int j 1; j n - i; j) cout ; for (int j 1; j 2 * i - 1; j) cout *; cout \n; }注意下半部分循环是从n - 1开始不是从n开始否则中间那一行会输出两次。这个边界在写的时候很容易忽略。我一般会建议新手先手动画一张 n3 或 n4 的表格把每一行的空格数和星号数列出来再对着表写循环基本万无一失。4.3 从三角形到菱形对称规律怎么用图形题到了菱形这一档就是在考你“能不能把一个图形拆成两个规则图形的组合”。上半部分是“空格递减、星号递增”下半部分完全对称把上半部分的循环反过来走一遍就行。更进一步的图形题比如蛇形方阵、螺旋矩阵则开始涉及“方向”和“边界”的切换。这类题在循环结构3里偶尔会出现它的核心已经不是打印本身而是模拟一个状态机的过程你有一个当前方向走到边界或已经填过的位置就转向。处理这类题建议用一个方向数组把“右、下、左、上”四个方向的行列增量提前存好再在循环里根据边界条件切换到下一个方向。这种“用方向数组模拟状态切换”的做法会一直沿用到后面更复杂的算法里早接触早受益。不过如果循环结构3只让你做数字方阵、九九乘法表、杨辉三角这类你只需要记住一句口诀先分行再分列最后抠边界。别一上来就想着写出完整代码先把图形拆成“哪几行、每行什么内容”写出来代码就是照抄。5. 看着像循环其实是模拟边界条件才是重头戏5.1 多组数据与未知组数的循环读入循环结构3里开始频繁出现“输入包含多组测试数据每组数据以某个条件结束”这类题。很多新手第一次碰到“不知道一共有多少组”时完全不知道该怎么写循环。标准做法是使用while (cin n)int n; while (cin n) { // 处理这一组数据 }它的原理是cin 在读取失败时比如读到文件末尾会返回一个“假”值循环自然结束。如果你用的是 scanf就写成while (scanf(%d, n) 1)判断依据是成功读取的变量个数。这类题最经常错的地方不是读入而是每组数据开始前变量没有重新初始化。比如求每组数据的平均值sum 和 count 必须在 while 循环体内部、处理整组数据之前清零。如果写在 while 外面第一组算完第二组的 sum 还带着上一组的数据结果就全错了。我见过好几个人查了半小时最后发现只是变量位置放错。还有一个细节如果题目的输入里每一行可能有若干个整数但你不需要知道一共有几个只要读到这一行结束可以配合getline配合stringstream去切分。不过在循环结构3这个阶段大多数题的输入格式都比较规整先用好while (cin x)就足够。5.2 死循环的常见成因和定位方法写循环最怕遇到死循环。尤其是 OJ 上跑起来直接 TLE超时或者卡住不动第一反应就应该是是不是某个 while 根本退不出去我总结了几种最常见的死循环成因循环体内没有更新循环控制变量。比如写while (n 0)循环体里却忘了写n--或n / 10n 永远不变。更新方向搞反。比如想不断除以 10 来统计位数结果写成n * 10数字越乘越大永远结束不了。用浮点数做精确比较。比如while (x ! 0.0)浮点数因为精度问题很可能永远不等于 0。应该用while (fabs(x) 1e-9)这种带误差范围的写法。变量在循环里被意外改回原值。常见于循环体里调用了一个会修改全局变量的函数互相干扰。定位死循环的方法很简单在循环体开头加一句调试输出打印当前的循环变量比如cerr n endl;跑一遍你就知道它卡在了哪个值上。如果是 OJ 上不方便调试就在本地复制数据手工跑。死循环的修复往往比定位容易得多麻烦的是那种“看似会停、实际多跑了一点点”的循环比如下面要说的边界问题。5.3 循环体里修改循环变量的连锁反应有些新手为了图省事会在循环体里直接修改循环变量。比如for (int i 0; i n; i) { // 某些条件下希望多处理当前项 if (条件) i--; }这种写法在某些情况下能跑出正确结果但非常容易失控。比如 i-- 之后又执行到 for 的 i导致 i 原地踏步如果条件一直成立就是死循环。即使没有死循环这种跳来跳去的控制流也很难让人判断“当前到底处理到哪了”。我的建议很简单循环控制变量的更新只放在 for 的第三表达式里循环体内不要改它。如果你确实需要“在当前项多做几轮”的逻辑换一种建模方式把当前项的值提前存到另一个变量里用 while 对这个变量做处理处理完再回到外层 for。比如去除一段数据中连续重复的内容时就可以用 while 跳过所有和当前相同的元素外层循环继续从下一个不同元素开始。这个思路既不破坏循环变量也更好读。3n1 冰雹猜想是这一节最好的练习题。它的循环次数完全由数据决定过程是如果当前数奇数就乘 3 加 1偶数就除以 2。直到变成 1 为止。while (n ! 1) { // 通常需要先输出当前值 if (n % 2 1) n 3 * n 1; else n / 2; }这里有几个坑第一如果题目要求输出整个变化过程你要想清楚是先输出再变换还是先变换再输出顺序错了输出结果就完全不对。第二奇数乘 3 加 1 之后数值可能比初始值大很多倍int 很容易溢出建议直接用 long long。第三这个循环是靠“n 变成 1”来结束的所以循环体里必须有改变 n 的操作。如果你发现这道题过了却总觉得理解得不踏实多半是因为没有亲手把一个数的变化过程完整写出来过。6. 踩坑记录循环题里最容易错的五个细节6.1 终止条件差一用代入法检查边界循环结构3的很多错误都出在i n和i n的区别上。差一个数在某些题里就是正确和错误的天壤之别。我的检查方法很笨但很有效把两端值代进去看看循环体执行不执行、执行时 i 是什么。比如for (int i 1; i n; i)当 in 时循环不执行所以循环体一共执行了 n-1 次改成i n就执行 n 次。遇到不确定的情况直接取 n1 或 n2 手算一遍正确性一目了然比反复瞪眼强太多。同理while 循环的终止条件也要用极端数据验证。比如统计一个正整数的位数while (n 0)对于 n0 会直接跳过如果题目里 n 可以是 0你就得单独判断“0 是一位数”这个特殊情况。边界值往往是大量 WA答案错误的来源。6.2 输出格式空格和换行要按题面来OJ 对输出格式的校验是逐字符的多一个空格、少一个换行都可能判错。最常见的是“行末不要有多余空格”和“每个测试数据之间要空一行”。处理办法是把输出格式也当成数据处理不要只盯着结果。如果要求一组数据输出一行就明确在每组计算结束后输出\n如果用循环输出一个数组/序列第一个元素前不要空格后面每个元素前加空格这是最稳的写法for (int i 1; i n; i) { if (i 1) cout ; cout a[i]; }还有一种情况是“每个输出占一行”那就要确保没有任何一处多打印了调试内容。很多新手把调试输出直接留在提交代码里导致格式错误我自己也干过这种事。现在我的习惯是所有调试用 cerr 而不是 cout这样提交前不用删因为 cerr 不影响 OJ 的答案输出判断。6.3 i 和 i 在循环里的区别在 for 的第三表达式中写上i和i的效果完全一样因为这一句表达式的返回值没有被使用。但在其他表达式里两个就有区别了int x i先用 i 的旧值赋值再把 i 加一int x i先把 i 加一再用新值赋值。循环结构3里会出现一些“在循环体里顺手做某件事”的写法比如cout a[i]这种代码如果对 i 和 i 不敏感非常容易出问题。我的建议是入门阶段避免这种“顺手表达式”老老实实把下标自增写成单独一行可读性高且不容易错。等到你完全掌握表达式求值顺序之后再考虑玩这些花活。6.4 变量初始化位置循环外还是循环内求一组数的最大值很多人会写int maxn 0;然后遍历。如果这组数全是负数最大值就会错误地变成 0。正确做法是把 maxn 初始化为第一个元素的值或者初始化为一个足够小的数比如-1e9。比初始化成什么更常踩的坑是初始化写在了错误的层级上。循环结构3经常有多组样例规范结构是这样的while (cin n) { int sum 0; // 每组样例都要重新初始化 for (int i 1; i n; i) { sum i; } cout sum \n; }sum 必须定义在 while 内部。如果你把 sum 定义在 while 外面第一组算完第二组就会把第一组的结果继续累加进去。这个错误很难肉眼发现因为你只盯着 sum 的变化看很难注意到它没有归零。我建议养成“和一组数据相关的变量都定义在这一组数据的处理代码内部”的习惯能从根本上避免串数据。6.5 用中间输出定位问题把循环变量打印出来很多循环题写错了但你又说不出到底哪一步开始错的。这时候最有效的手段就是把循环过程可视化。在循环体里临时加一行cerr i i , sum sum endl;然后跑一遍小数据观察每一轮的变量变化是否符合预期。这个方法几乎能解决所有“循环状态更新出错”的问题。比如递推题里 a、b 滚动更新反了一经打印立刻暴露打印图形题里空格数不对把n - i的值打印出来很快就能发现规律错了。等到你确认代码正确再把这些调试输出删掉或注释掉。记住一个原则不要用眼睛盯着代码硬想让程序自己告诉你它每一步在做什么。这是我从入门到现在一直沿用的排查方式。最后再分享一个实际体会写循环结构3这段时间我最大的收获不是掌握了某个具体语法而是学会了一件事写循环前先问自己“每一轮循环结束之后状态和刚进循环时相比发生了什么变化”。想清楚这个问题代码基本不会错想不清楚写出来必然到处是坑。如果现在你正卡在某道循环题上我建议你试一下这个办法把变量列表写在纸上手算一个最小的样例走一遍循环每一步更新所有变量。你会发现很多“它怎么会输出这个”的问题答案都在你自己的纸面上。等你过了这一关再去翻数组、字符串专题会发现世界豁然开朗了——因为循环结构真的是后面所有内容的地基。