cpp-courseware/2.Course/1.深入浅出程序设计竞赛（基础篇）/1.语言入门/第4章 循环结构程序设计/3.多重循环/讲义资料/多重循环 讲义.md

C++ 程序与算法：多重循环与循环嵌套

一、单层循环到循环嵌套

1. 从小任务开始

还记得怎样在同一行输出 4 个星号吗？用一个循环就可以：

for (int j = 1; j <= 4; j++) {
    cout << "*";
}
cout << '\n';

循环每执行一次，就输出一个星号。重复 4 次，屏幕上就有了：

****

这里的换行为什么写在循环后面？

因为这一行的 4 个星号要先全部输出，再换行。如果把换行放进循环，每输出一个星号就换行，它们就会排成一列。

如果要输出 3 行，每行仍然是 4 个星号呢？

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

把“输出一行并换行”的代码复制 3 遍，也能完成。不过，行数变成 100 时，复制起来就麻烦了；每行的星号数量要改，还得改很多处。

我们可以把“输出一行并换行”看成一件事，再用一个循环重复它。这样，循环里面就有了另一个循环，这种写法叫作循环嵌套。

2. 学习它有什么用？

许多题目都能像这样拆开：先重复处理一个对象，再重复处理它里面的内容。

场景	第一层任务	第二层任务
输出矩形或三角形	逐行处理	输出当前行的内容
输出乘法表	确定当前行	计算这一行中的各个乘积
求多个阶乘的和	逐项处理阶乘	计算当前这一项的乘积
统计数字出现次数	枚举一个整数	检查这个整数的每一位
处理二维表格	枚举每一行	枚举该行中的每一列

算法竞赛中的枚举、模拟和表格处理，经常用到循环嵌套。以后学到数组、矩阵和图像处理时，我们还会遇到它。

二、核心思想：把完整的小任务放进循环体

1. 什么是循环嵌套？

在一个循环的循环体里，再放入另一个循环，就是循环嵌套。

for (外层初始化; 外层条件; 外层更新) {
    // 开始处理一个新的大任务

    for (内层初始化; 内层条件; 内层更新) {
        // 完成当前大任务中的一个小步骤
    }

    // 当前大任务的收尾工作
}

这段写法用来说明两层循环的结构；实际写程序时，需要把中文占位内容换成 C++ 语句。

外面的叫外层循环，里面的叫内层循环。两层循环也称为二重循环，题目需要时还可以嵌套三层或更多层。

判断是否嵌套，要看一个循环有没有放进另一个循环的循环体里。

for (int i = 1; i <= 3; i++) {
    cout << i;
}
for (int j = 1; j <= 4; j++) {
    cout << j;
}

上面两个循环是先做完一个，再做另一个。它们没有互相包含，所以不属于循环嵌套。

2. 一次外层循环中，内层会执行多少次？

输出星号矩形时，两层循环是这样配合的：

for (int i = 1; i <= 3; i++) {
    for (int j = 1; j <= 4; j++) {
        cout << "*";
    }
    cout << '\n';
}

外层每一轮都要完成一整行：

外层第 1 轮：内层输出 4 个星号 → 换行
外层第 2 轮：内层输出 4 个星号 → 换行
外层第 3 轮：内层输出 4 个星号 → 换行

这里容易看错：外层进行一轮时，内层要从初始化开始，把当前行的 4 个星号全部输出。

输出这一行时，i 保持不变，内层执行 j++ 只会改变行内位置。等这一行输出完并换行后，才轮到外层的 i++。

3. 为什么新的一行，j 又从 1 开始？

内层循环写的是：

for (int j = 1; j <= 4; j++) {
    cout << "*";
}

因为每次执行到这条 for 语句，程序都会先执行 int j = 1。所以，新的一行总是从第一个位置开始。

本例中的 j 只在内层 for 的范围内有效。内层结束后，这一轮的 j 就不能再使用了；下一次进入内层时，会重新创建并初始化 j。

4. 哪些语句属于外层？看大括号

下面的代码中，整个内层循环和后面的换行，都在外层的大括号里面：

for (int i = 1; i <= 3; i++) {
    // 任务 1：输出当前行的 4 个星号
    for (int j = 1; j <= 4; j++) {
        cout << "*";
    }

    // 任务 2：当前行结束，换行
    cout << '\n';
}

C++ 根据大括号判断语句属于哪一层。初学时，建议大家把大括号写完整。即使循环体只有一条语句，也先保留它，以后添加代码时就不容易放错位置。

三、例题重点回顾

例一：输出 3 行 4 列的星号矩形

这道题要输出的图形是：

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

一行的写法已经会了，把“输出 4 个星号，再换行”交给外层，重复 3 次就可以。

for (int i = 1; i <= 3; i++) {      // 当前是第 i 行。
    for (int j = 1; j <= 4; j++) {  // 当前行的第 j 个位置。
        cout << '*';
    }
    cout << endl;  // 一行全部输出后再换行。
}

回顾这段代码时，留意变量和换行的位置：

• i 控制行号；处理一行时，i 保持不变。
• j 控制行内位置；每进入新的一行，都重新从 1 开始。
• 换行放在内层结束后、外层之内，每行执行一次。

因此，星号输出 3\times4=12 次，换行执行 3 次。

写循环嵌套的四个步骤

写类似的题目时，可以按这四步想：

步骤	要想清楚什么？	星号矩形中的安排
① 拆任务	外层和内层分别做什么？	外层输出一整行，内层每次输出一个星号
② 判断循环范围	每层从哪里开始，到哪里结束？	外层从 1 到 3，共 3 行；内层从 1 到 4，每行 4 个星号
③ 设置变量	变量表示什么，在哪里初始化？	i 表示行号；j 表示行内位置，每行重新从 1 开始
④ 写循环语句	每个动作放在哪一层才合适？	内层输出星号，内层结束后、外层之内换行

遇到编号、总和这样的变量，再问自己一句：“下一轮还要接着用这个值吗？”要接着用，就在外层前初始化；每轮重新计算，就在外层内初始化。

例二：连续编号的数字直角三角形

输入整数 n，范围是 1 ≤ n ≤ 13，输出 n 行数字。第一行有 n 个数，以后每行少一个；编号从 1 开始，换行后接着往下数。每个数显示两位，不足两位补 0，数字之间不加空格。

n=5 时：

0102030405
06070809
101112
1314
15

这道题要分清“这一行有几个数”和“当前输出哪个数”：

• 第 i 行比第一行少 i-1 个数，所以第 i 行有 n-（i-1） 个数，内层上界随行号变化。
• i 记录行号，j 记录行内位置，cnt 才是实际输出的编号。
• cnt 要在外层前设为 1，每输出一个数后加 1。换到下一行时，编号还要接着用，所以不能重置。
• 个位数前先输出字符 '0'，这一行的数字全部输出后再换行。

int cnt = 1;  // 保留编号
for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= n - i + 1; j++) {
        if (cnt < 10) {
            cout << '0';
        }
        cout << cnt;
        cnt++;
    }
    cout << '\n';  // 一行结束后换行。
}

例三：计算阶乘之和

输入正整数 n，范围是 1 ≤ n ≤ 20，求 $S=1!+2!+3!+\cdots+n!$。

重点看乘积和 和 总和各自怎么保存：

• 外层依次处理每一项，内层从 1 乘到 i，算出当前的 i!。
• 总和 ans 从 0 开始，一直保留前面各项的结果；乘积 factor 从 1 开始，每算新的一项都要重新准备。
• 等内层乘完后，再执行 ans += factor。放进内层的话，计算过程中的乘积也会被加进去。
• factor 和 ans 都要用 long long，因为 13! 已经超出常见的 32 位 int 范围。

读入 n 后，关键循环如下：

long long ans = 0;  // 保留所有已完成项的总和。
for (int i = 1; i <= n; i++) {
    long long factor = 1;  // 每一项都从头计算。
    for (int j = 1; j <= i; j++) {
        factor *= j;
    }
    ans += factor;  // 当前阶乘算完后再累加。
}
cout << ans << '\n';

本题 n≤20，用 long long 可以保存阶乘和总和。不过，这种类型也有上限，不能一直用它计算更大的阶乘。

简单改进：利用已经算出的阶乘

上一项的阶乘已经算好了，下一项可以接着乘。利用 $i!=(i-1)!\times i$，就能省去内层的重复计算：

long long ans = 0, factor = 1;
for (int i = 1; i <= n; i++) {
    factor *= i;
    ans += factor;
}
cout << ans << '\n';

这时要把 factor 放到循环外，因为下一轮还要接着用上一次的乘积。变量放在哪里，要看当前算法怎样使用它。

例四：统计数字出现的次数

输入 n 和 x，统计 1 到 n 的所有整数中，数字 x 一共出现了多少次。输入范围为 1≤n≤1000000、0≤x≤9。

这里要把“取出一个整数”和“检查它的每一位”分开：

• 外层 for 逐个取出从 1~n 的每一个整数，内层 while 检查这个整数的全部数位。
• 先用 int tmp = i 复制一份，再对副本拆位，因为外层变量 i 需要记住处理到哪个整数，所以不能把 i 给拆掉。
• 然后用 tmp % 10 取个位，检查完后用 tmp /= 10 去掉个位。等 tmp 变成 0，就检查完了。
• 每找到一个符合条件的数位，就计数一次。例如 11 里面有两个 1，要计两次。

读入 n 和 x 后，关键循环如下：

int ans = 0;
for (int i = 1; i <= n; i++) {
    int tmp = i;  // 用副本去拆位，保留外层进度。
    while (tmp != 0) {
        int digit = tmp % 10;
        if (digit == x) {
            ans++;
        }
        tmp /= 10;  // 无论是否匹配，都继续处理下一位。
    }
}
cout << ans << '\n';

这里容易写错的是 tmp /= 10 的位置：无论当前数位是否匹配，都要继续处理下一位，所以它应放在 if 外面。注意不能直接对 i 拆位，外层的进度就会被改掉，反复回到 1。

四、要点总结

• 外层每轮完成一个完整任务，内层处理其中的重复动作。for 和 while 可以根据题目需要搭配使用。
• 写代码时，先拆任务，再判断循环范围、设置变量，最后安排循环里的语句。
• 变量要跨轮保留，就在外层前初始化；每轮要重新准备，就在外层内、内层前初始化。
• 每个元素都要做的操作放内层，一轮结束后的收尾放在内层后、外层内，最终结果等外层结束后再处理。
• 内层每轮次数相同时，可以用乘法算总次数；次数随外层变化时，就把每轮的次数加起来。
• 算过的结果有时还能接着用。像阶乘之和，就可以保留上一项，减少重复计算。