四、循环：计数、累加与遍历

循环是编程真正开始的地方。

前面所有程序都只能处理固定几个数——读两个数、算一个结果。循环让你处理一串数：100 个数求和、1 到 n 里有多少个素数、一个 n 位数的每一位。

这一页 3 章 28 题，核心就三件事：

1. for 和 while 分别什么时候用
2. 累加变量的初值该给多少（这是初学者最高频的 bug 来源）
3. 怎么在一堆数里找最大最小

把这三件事做熟，后面数组、字符串、结构体，全都是在循环上套壳。

12. 计数循环与图形输出

12.1 for：重复做同一件事

for (int i = 1; i <= n; i++) {
    printf("%d\n", i);
}

for 括号里三段，用分号隔开：

执行顺序是：初始化 → 检查条件 → 循环体 → 第三段 → 检查条件 → 循环体 → ……

循环从 1 开始还是从 0 开始？ 数数用 1 到 n（i = 1; i <= n），数组下标用 0 到 n-1（i = 0; i < n）。这两种写法都常见，看场景。

一个必须警惕的错：循环条件写错，会多跑或少跑一轮。

for (int i = 1; i < n; i++)    // 少一轮，n 本身没取到
for (int i = 1; i <= n; i++)   // 对，1 到 n

差一个等号，结果就少一个数。遇到「答案差一点」的情况，第一个怀疑对象就是循环边界。

12.2 循环里控制输出：画图形

图形输出题考的不是循环本身，而是「第 i 行该输出几个字符」这个规律能不能找出来。

以等腰三角形为例，n = 4 时：

   *
  ***
 *****
*******

每行的规律：

规律是：空格 = n - i，星号 = 2i - 1。

for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= n - i; j++) printf(" ");
    for (int j = 1; j <= 2 * i - 1; j++) printf("*");
    printf("\n");
}

做这类题的固定流程：

1. 先画一个 n = 4 或 5 的样例
2. 列表格：行号 / 空格数 / 字符数
3. 找出「行号 → 数量」的公式
4. 写代码

跳过第 2 步直接写代码的人，90% 会卡住。因为图形题的公式不是想出来的，是数出来的。

12.3 双重循环

一个循环里套另一个循环，用于「每一行还要做很多事」。

最典型的例子是九九乘法表：

for (int i = 1; i <= 9; i++) {
    for (int j = 1; j <= i; j++) {
        printf("%dx%d=%d\t", j, i, j * i);
    }
    printf("\n");
}

注意内层是 j <= i，不是 j <= 9——第 i 行只有 i 个式子，这就是三角形的形状。

双重循环的执行次数 = 外层次数 × 内层次数。 外层 9 次、内层最多 9 次，总共 45 次。这个概念在第 15 章判断素数时会用到（为什么试除到根号就够了）。

12.4 while：次数不确定的时候

for 适合「我知道要循环几次」，while 适合「我不知道几次，但知道什么时候停」。

int n;
scanf("%d", &n);
while (n > 1) {
    if (n % 2 == 0) n = n / 2;
    else n = n * 3 + 1;
    cnt++;
}

这段是角谷猜想（第 20 章会做）。你不知道要走多少步，只知道「只要还大于 1 就继续」。

while 的两种写法等价：

while (n > 1) { ... }
for (; n > 1; ) { ... }     // 三段的中间那一段就叫 while

选哪种看可读性：循环次数已知或可数 → for；循环次数未知、靠条件退出 → while。

while (n > 1) {
    n = n * 2;      // n 永远大于 1，循环停不下来
}

13. 累加、累乘与最值

这一章是循环里最实用的三件套，也是 bug 最密集的地方。

13.1 累加器：从 0 开始

int sum = 0;              // 关键：初值 0
for (int i = 1; i <= n; i++) {
    sum += i;             // 等于 sum = sum + i
}

sum += i 是 sum = sum + i 的简写。-=、*=、/= 同理。

累加的初值必须是 0。这不是习惯，是数学要求：0 加上任何数都不变，所以从 0 开始才能正确累加。

int sum;              // 错！未初始化，值是随机的
for (...) sum += i;   // 结果是一个随机数

未初始化的局部变量，值是内存里残留的垃圾。它可能每次都不一样——本地跑对了、交上去错了，是最难查的那种 bug。

13.2 最值的初值：这是本章最大的坑

找最大值，标准写法：

int mx = -1000000000;     // 或者 -1e9，或者 INT_MIN
for (int i = 1; i <= n; i++) {
    int x; scanf("%d", &x);
    if (x > mx) mx = x;
}

初值为什么不能给 0？ 因为如果所有数都是负数，mx 会一直是 0，而 0 根本不在数据里。

int a[] = {-5, -3, -8};
int mx = 0;              // 错！结果输出 0，正确答案是 -3

三种正确写法，选一种：

第三种写法最严谨：

int n; scanf("%d", &n);
int mx; scanf("%d", &mx);       // 先读第一个
for (int i = 2; i <= n; i++) {
    int x; scanf("%d", &x);
    if (x > mx) mx = x;
}

注意循环从 i = 2 开始，因为第一个已经读过了。

13.3 累乘与幂

累乘和累加一模一样，只有初值不同：累乘从 1 开始。

long long fact = 1;           // 关键：初值 1，不是 0
for (int i = 1; i <= n; i++) {
    fact *= i;
}

初值给 0 的话，乘什么都是 0。

阶乘增长极快：13! 就超过 int 上限了。所以阶乘题一律用 long long，而且题目通常会限制 n 的范围。

求 a 的 n 次方，原理相同：

long long p = 1;
for (int i = 1; i <= n; i++) p *= a;

别用 pow(a, n)：它返回 double，结果大于 2^53 就开始丢精度，而且转回整数时可能差 1。

13.4 级数求和与精度

e = 1 + 1/1! + 1/2! + 1/3! + ...

这类题的写法是边算边累加，直到某一项足够小：

double e = 1.0, term = 1.0;
int i = 1;
while (term > 1e-10) {
    term /= i;          // 上一项除以 i 得到这一项
    e += term;
    i++;
}

注意 term /= i 这个技巧：1/i! = 1/(i-1)! ÷ i，所以不用每次重算阶乘，用上一项除以 i 就行。这比每次都算阶乘快得多，也避免阶乘溢出。

13.5 组合：最大跨度

14. 序列遍历与条件筛选

这一章的模式是：读入一串数，边读边处理，不存下来。

14.1 边读边算

大多数题不需要把数据全部存起来。读到就处理，处理完就扔：

int n; scanf("%d", &n);
int sum = 0;
for (int i = 0; i < n; i++) {
    int x; scanf("%d", &x);
    sum += x;
}
printf("%d\n", sum);

这样做的好处是用多少内存都行——100 万个数也只占一个变量的空间。

什么时候必须存下来？ 当后面的处理需要回头访问前面的数时。比如「找出最大值的位置」「判断是否递增」「排序」。这些要到第 22 章数组才讲。

14.2 筛选与计数

「满足条件的数有几个」「把满足条件的都输出」，模式是在循环里加一个 if：

int cnt = 0;
for (int i = 1; i <= n; i++) {
    if (i % 3 == 0 && i % 5 == 0) {
        cnt++;
    }
}

这个模式后面会用到无数次：素数计数、闰年计数、成绩分段统计……循环负责遍历，if 负责筛选，变量负责累计。

14.3 相邻比较：需要「记住上一个」

「是否连续上升」「连续相同的有多长」——这类题的关键是保存上一个数：

int prev, cur;
scanf("%d", &prev);
for (int i = 2; i <= n; i++) {
    scanf("%d", &cur);
    if (cur > prev) { /* 上升 */ }
    prev = cur;              // 关键：更新 prev
}

prev = cur 这一行千万别忘。忘了的话，prev 永远是第一个数，比较就全错了。

这是「需要一个变量记住之前状态」的第一个例子。 后面动态规划、滑动窗口，都是这个思路的升级版。

14.4 标记法：用一个变量记住「有没有发生过」

有时候不需要计数，只需要知道「有没有」：

bool found = false;
for (int i = 1; i <= n; i++) {
    if (满足条件) {
        found = true;
        break;              // 找到了就可以停
    }
}
if (found) printf("yes\n");
else printf("no\n");

bool 类型只有 true 和 false 两个值。用 int 存 0/1 也行，但 bool 更能表达意图。

break 是立刻跳出当前这一层循环。找到了就停，不用继续跑完剩下的——这在数据量大时能省很多时间。

延伸阅读

服务器上有一整套 OI-Wiki（621 页），是给竞赛选手写的参考手册。下面几页跟这一页相关，但不是每一页都该现在看——标了「现在跳过」的，等以后再说。

• 可以先看：循环 —— for 的三个部分分别什么时候执行——这个必须搞清楚，不然嵌套循环必错