C1-11 循环习题分析

枚举暴力、循环模拟

学习目标：理解循环不只可以打印图形，还可以逐个尝试答案、一步一步模拟过程；掌握枚举算法的基本思想和“范围—条件—记录答案”的分析方法；掌握模拟的基本思想；能够使用循环解决鸡兔同笼、百鸡百钱、勾股数、周期猜拳、分组发金币和最长连续段等问题。

---

一、本课在循环学习中的位置

1．第 10 课学了什么

第 10 课我们学习了循环嵌套：

• 外层循环负责大轮次，例如第几行；
• 内层循环负责小轮次，例如这一行的第几列；
• 外层循环每执行一次，内层循环就完整执行一遍。

循环嵌套最直观的应用是打印图形：

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

2．循环还可以解决哪些问题

循环不仅能“画图”，还可以：

• 把所有可能的答案逐个尝试一遍；
• 按照前面结果生成后面的数；
• 按照题目规定，一步一步模拟事情的发展；
• 让每个对象和其他对象逐个比较。

本课主要学习下面三类题目：

类型	主要问题	常用方法
枚举暴力类	答案藏在很多种可能中，逐个检查	枚举、判断、记录
循环模拟类	过程按固定规则一步一步发生	状态、轮次、周期、更新

---

二、第一类：枚举暴力题

1．什么是枚举

枚举算法 = 枚举 + 判断

枚举就是把可能的答案一个一个列出来，再检查当前答案是否符合题目要求。

例如，鸡兔同笼问题中，鸡的数量可能是 0、1、2、...、n。我们可以依次假设鸡的数量，再计算兔子的数量，检查脚的总数是否正确。

枚举并不是“没有方法地乱试”，而是：

1. 找出答案的范围；
2. 按顺序尝试范围内的每一种可能；
3. 用题目条件检查当前可能；
4. 找到符合条件的答案后输出或记录。

枚举题的三件重要事情：

事情	要问的问题	常见错误
确定范围	变量最小是多少，最大是多少？	范围太小，漏掉答案
写出条件	当前答案怎样才算正确？	少写条件或条件方向写反
记录结果	找到答案后要输出、计数还是求最值？	找到了却没有保存

如果一个问题有两个未知量，通常可以使用两层循环；如果有三个未知量，通常可以使用三层循环。但如果能够通过总量先算出一个变量，就可以减少一层循环。

---

2、例题一：鸡兔同笼

(1)．题目

笼子里有 n 个头、m 只脚。鸡有 2 只脚，兔有 4 只脚。求鸡和兔各有多少只。

(2)．分析

设鸡有 chicken 只，那么：

兔子数量 = n - chicken

鸡的数量可以从 0 枚举到 n。对于每一种鸡的数量，检查脚的总数是否为 m：

2 × 鸡的数量 + 4 × 兔子的数量 = m

(3)．参考代码

#include <iostream>
using namespace std;

int main() {
    int n, m;
    cin >> n >> m;

    for (int chicken = 0; chicken <= n; chicken++) {
        int rabbit = n - chicken;

        if (2 * chicken + 4 * rabbit == m) {
            cout << chicken << " " << rabbit << endl;
        }
    }

    return 0;
}

(4)．代码说明

• chicken 是被枚举的量；
• rabbit 不需要再枚举，可以用 n - chicken 算出；
• 条件成立时，说明这一组鸡兔数量符合题意；
• 如果题目保证答案唯一，找到后可以使用 break 结束循环；
• 如果题目可能无解，还要根据题意处理“没有找到答案”的情况。

(5)．何不直接枚举两个数量

也可以写成两层循环：

for (int chicken = 0; chicken <= n; chicken++) {
    for (int rabbit = 0; rabbit <= n; rabbit++) {
        if (chicken + rabbit == n &&
            2 * chicken + 4 * rabbit == m) {
            cout << chicken << " " << rabbit << endl;
        }
    }
}

这种写法更接近“把两种数量都试一遍”，但循环次数更多。能够根据总头数算出兔子数量时，一层循环就够了。

枚举时，优先寻找变量之间的关系，能少枚举一层，就少枚举一层。

---

3、例题二：百鸡百钱

(1)．题目

公鸡 5 文钱 1 只，母鸡 3 文钱 1 只，小鸡 1 文钱 3 只。现在用 100 文钱买 100 只鸡，求所有可能的购买方案。

(2)．分析

设：

公鸡数量为 cock
母鸡数量为 hen
小鸡数量为 chick

三个数量必须满足：

cock + hen + chick = 100
5 × cock + 3 × hen + chick / 3 = 100

由于小鸡是 1 文钱 3 只，所以只有 chick 能被 3 整除时，chick / 3 才表示完整的小鸡组数。

我们可以枚举公鸡和母鸡，小鸡数量由总数直接算出：

chick = 100 - cock - hen

(3)．参考代码

#include <iostream>
using namespace std;

int main() {
    for (int cock = 0; cock <= 100/5; cock++) {
        for (int hen = 0; hen <= 100/3; hen++) {
            int chick = 100 - cock - hen;

            if (chick < 0) continue;

            if (chick % 3 == 0 && 5 * cock + 3 * hen + chick / 3 == 100) {
                cout << cock << " " << hen << " " << chick << endl;
            }
        }
    }
    return 0;
}

(4)．枚举范围怎样确定

公鸡 5 文钱 1 只，最多买 20 只，所以：

cock = 0 ~ 20

母鸡 3 文钱 1 只，最多买 33 只，所以：

hen = 0 ~ 33

小鸡不用单独循环，因为它可以通过总数算出。

范围可以根据题目条件缩小，但不能超过题目允许的范围。写范围时要检查最小值、最大值是否包含在内。

---

4、例题三：勾股数

(1)．题目

输入正整数 n，找出所有满足下面条件的正整数三元组：

a < b < c ≤ n
a² + b² = c²

例如：

3² + 4² = 5²

所以 (3,4,5) 是一组勾股数。

(2)．三层枚举

如果暂时不知道 a、b、c 之间的其他关系，可以分别枚举三个数：

#include <iostream>
using namespace std;

int main() {
    int n;
    cin >> n;

    for (int a = 1; a <= n; a++) {
        for (int b = a + 1; b <= n; b++) {
            for (int c = b + 1; c <= n; c++) {
                if (a * a + b * b == c * c) {
                    cout << a << " " << b << " " << c << endl;
                }
            }
        }
    }

    return 0;
}

(3)．为什么循环从 a+1、b+1 开始

题目要求 a < b < c，因此：

• b 不必从 1 开始，可以从 a + 1 开始；
• c 不必从 1 开始，可以从 b + 1 开始；
• 这样可以避免重复枚举，例如不再重复检查 (4,3,5)。

(4)．枚举题的效率意识

三层循环比较直观，但循环次数会很快增加。写枚举题时，要先估计：

总尝试次数 ≈ 第一层次数 × 第二层次数 × 第三层次数

数据范围很小时，暴力枚举通常可以接受；数据范围很大时，需要继续学习更快的方法。

---

三、第二类：循环模拟题

1．什么是模拟

模拟就是按照题目给出的规则，让程序一步一步重现整个过程。

模拟题不一定需要复杂公式，关键是把题目中的状态说清楚：

例如：

• 现在进行到第几轮？
• 当前轮使用哪个数据？
• 状态怎样变化？
• 下一轮从哪里继续？

2、例题一：周期性石头剪刀布

(1)．题目

小 A 和小 B 都按照自己的出拳序列循环出拳：

A 的序列：石头、布、石头、剪刀
B 的序列：剪刀、石头、布

每一轮都取各自序列中的下一个动作。序列到末尾后，又从第一个动作开始。问进行 n 轮后，谁赢的轮数更多。

为了方便存储，可以约定：

0 表示石头
2 表示剪刀
5 表示布

这里的数字只是编码，不能直接用数字大小判断输赢。

(2)．用余数找到周期位置

如果 A 的周期长度是 na，第 i 轮对应的下标是：

i % na

例如 A 的序列长度为 4：

轮次 i	i % 4	使用的位置
0	0	第 1 个动作
1	1	第 2 个动作
2	2	第 3 个动作
3	3	第 4 个动作
4	0	回到第 1 个动作

(3)．判断谁赢

在 0、2、5 的编码中：

石头 0 胜 剪刀 2
剪刀 2 胜 布 5
布   5 胜 石头 0

可以写成一个判断函数：

bool win(int x, int y) {
    return (x == 0 && y == 2) ||
           (x == 2 && y == 5) ||
           (x == 5 && y == 0);
}

(4)．参考代码

#include <iostream>
using namespace std;

bool win(int x, int y) {
    return (x == 0 && y == 2) ||
           (x == 2 && y == 5) ||
           (x == 5 && y == 0);
}

int main() {
    int n, na, nb;
    cin >> n >> na >> nb;

    int a[105], b[105];

    for (int i = 0; i < na; i++) {
        cin >> a[i];
    }

    for (int i = 0; i < nb; i++) {
        cin >> b[i];
    }

    int scoreA = 0;
    int scoreB = 0;

    for (int i = 0; i < n; i++) {
        int x = a[i % na];
        int y = b[i % nb];

        if (x == y) {
            // 平局，不给任何一方加分
        } else if (win(x, y)) {
            scoreA++;
        } else {
            scoreB++;
        }
    }

    if (scoreA > scoreB) {
        cout << "A" << endl;
    } else if (scoreA < scoreB) {
        cout << "B" << endl;
    } else {
        cout << "draw" << endl;
    }

    return 0;
}

(5)．模拟过程中的三个状态

每一轮都要同时确定：

1. A 这一轮出什么；
2. B 这一轮出什么；
3. 当前比分怎样变化。

不要把 i % na 错写成 i % n。每个人的循环周期长度不同，必须使用各自的周期长度。

---

3、例题二：分组发金币

(1)．题目

第 1 天发 1 个金币；接下来连续 2 天每天发 2 个金币；再接下来连续 3 天每天发 3 个金币；继续这个规律。求第 k 天结束时一共发了多少个金币。

发放过程如下：

天数	当天金币数
第 1 天	1
第 2、3 天	2
第 4、5、6 天	3
第 7、8、9、10 天	4

(2)．需要保存哪些状态

每一天至少要知道：

• coin：当天发多少个；
• daysLeft：这一组还剩几天；
• total：到目前为止一共发了多少个。

(3)．参考代码

#include <iostream>
using namespace std;

int main() {
    int k;
    cin >> k;

    int total = 0;
    int coin = 1;
    int daysLeft = 1;

    for (int day = 1; day <= k; day++) {
        total += coin;
        daysLeft--;

        if (daysLeft == 0) {
            coin++;
            daysLeft = coin;
        }
    }

    cout << total << endl;
    return 0;
}

(4)．以 k = 10 为例

每天的金币数是：

1，2，2，3，3，3，4，4，4，4

总数是：

1 + 2 + 2 + 3 + 3 + 3 + 4 + 4 + 4 + 4 = 30

(5)．模拟题的关键

题目中的“连续若干天”不一定要先求出一个复杂公式，也可以用状态变量模拟：

当天发金币
→ 这一组剩余天数减 1
→ 如果这一组结束，就进入下一组

---

4、例题三：最长连续正常时间

(1)．题目

监护室每小时测量一次血压。如果收缩压在 90 到 140 之间，并且舒张压在 60 到 90 之间（包含端点），就认为这一小时血压正常。输入 n 次测量，求连续正常的最长小时数。

(2)．把问题变成连续段

例如每小时的结果是：

正常  不正常  正常  正常  正常  不正常

连续正常的长度是：

1      0       1     2     3      0

只要在扫描过程中维护两个变量：

• current：当前连续正常的长度；
• best：目前见过的最长连续长度。

(3)．参考代码

#include <iostream>
using namespace std;

int main() {
    int n;
    cin >> n;

    int current = 0;
    int best = 0;

    for (int i = 1; i <= n; i++) {
        int systolic, diastolic;
        cin >> systolic >> diastolic;

        bool normal = systolic >= 90 && systolic <= 140 &&
                      diastolic >= 60 && diastolic <= 90;

        if (normal) {
            current++;
            if (current > best) {
                best = current;
            }
        } else {
            current = 0;
        }
    }

    cout << best << endl;
    return 0;
}

(4)．为什么遇到“不正常”要清零

连续长度要求中间不能断开：

正常、正常、不正常、正常
  1      2      0      1

遇到不正常时，之前的连续段已经结束，所以必须：

current = 0;

而 best 不能清零，因为它保存的是历史上出现过的最大值。

“当前值”和“历史最好值”是连续段题中最常见的一对变量。