# 第8课：枚举与模拟（三级工具降维）

> 等级说明：枚举与模拟属于 GESP 三级知识。本课把它们作为工具，用来简化一级、二级的循环、分支与简单数学问题。

## 教学目标
- 理解枚举算法的核心思想：列举所有可能，逐一验证
- 掌握枚举优化的两个技巧：缩小范围、提前终止
- 理解模拟算法的核心思想：按题目描述一步步翻译成代码

## 核心考点：枚举范围与模拟执行顺序

### 考什么
枚举题要求列出所有可能答案并逐一验证；模拟题要求按照题目描述复现一个变化过程。两者都依赖清晰的范围、条件和执行顺序，常考输出满足条件的方案、计数或最终状态。

### 必须理解
枚举包含三步：确定候选变量、确定合法范围、写出验证条件。范围必须覆盖所有可能答案，但可以利用题目约束缩小。找到答案后是否 `break`，取决于题目要第一个答案还是全部答案。模拟则要把文字规则拆成按顺序执行的动作，明确每一步读取旧状态还是更新后的状态；若多个变量应同时变化，不能让前一个更新意外影响后一个计算。

### 核心写法
```cpp
for (int candidate = lower; candidate <= upper; candidate++) {
    if (满足全部条件) {
        // 记录、计数或输出 candidate
    }
}

for (int step = 1; step <= totalSteps; step++) {
    // 按题意顺序更新当前状态
}
```
枚举是在“答案空间”中找；模拟是在“时间步骤”中走。先判断题目属于哪一种，再确定循环变量的含义。

### 常见错误
- 枚举范围少一个端点，漏掉合法答案。
- 未判断题目要全部解，找到第一个就错误 `break`。
- 把模拟步骤顺序颠倒，得到不同状态。
- 明明能由约束缩小范围，却枚举过多无效候选，造成超时。

### 判断是否掌握
能指出循环变量代表候选答案还是执行步数，能给出完整上下界和验证条件，并能用手算前几步检查模拟更新顺序。

---

## 题目一：鸡兔同笼（枚举入门）

### 核心代码（一句话）
> 枚举的核心：**`for` 循环遍历所有可能的答案**，用 `if` 判断是否满足条件，满足就输出。

### 自然语言思路
笼子里有鸡和兔，一共 n 个头、m 只脚。鸡有 2 只脚，兔有 4 只脚。问鸡和兔各有几只？

第一步，鸡的数量可能是 0 到 n（因为总共 n 个头），让 `chicken` 从 0 循环到 n。
第二步，兔的数量 = 总数 - 鸡数：`rabbit = n - chicken`。
第三步，验证脚数：`chicken * 2 + rabbit * 4 == m`，如果成立，这就是答案。
第四步，输出鸡和兔的数量。

> 枚举就像"地毯式搜索"——把所有可能性都试一遍，看哪个符合条件。

### 伪代码
```
1. 输入 n（头数）, m（脚数）
2. for chicken = 0 到 n：
3.     rabbit = n - chicken
4.     if chicken * 2 + rabbit * 4 == m：
5.         输出 chicken 和 rabbit
```

### 真实代码
```cpp
#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 (chicken * 2 + rabbit * 4 == m) {
            cout << "鸡：" << chicken << "，兔：" << rabbit << endl;
        }
    }
    return 0;
}
```

### 注意点
1. **枚举范围 0 到 n**：不要漏掉 0（可能全是兔子）和 n（可能全是鸡）。
2. **兔的数量直接算**：因为鸡兔总数固定，所以兔 = n - 鸡，不需要再套一层循环枚举兔。这是"间接枚举"——少一个变量就少一层循环。
3. **可能无解**：如果循环结束都没输出，说明数据有问题（比如输入 2 个头 100 只脚）。
4. **脚数奇偶性判断**：实际上可以先用 `if (m % 2 != 0)` 快速判断无解（因为每只动物脚数都是偶数），但这是优化技巧，初学者先掌握枚举思路。

---

## 题目二：找完数（枚举进阶）

### 核心代码（一句话）
> 完数判断的核心：**枚举所有小于 n 的正整数 i，如果 `n % i == 0`，i 就是 n 的因子，把因子累加起来**，最后比较和是否等于 n。

### 自然语言思路
完数是指一个数等于它所有真因子（不包括自身）之和。比如 6 = 1 + 2 + 3，28 = 1 + 2 + 4 + 7 + 14。请找出 1000 以内的所有完数。

第一步，外层枚举：`for (n = 2; n <= 1000; n++)`，对每个 n 判断它是不是完数。
第二步，对每个 n，用内层循环从 1 到 n-1 找它的因子：`if (n % i == 0)` 则 `sum += i`。
第三步，遍历完所有因子后，`if (sum == n)` 则 n 是完数，输出。
第四步，优化：找因子只需要搜到 `n/2`（因为大于 n/2 的数不可能是 n 的因子，除了 n 自身）。不过用 `sqrt(n)` 也行但要处理成对出现的情况。

### 伪代码
```
1. for n = 2 到 1000：
2.     sum = 0
3.     for i = 1 到 n-1：
4.         if n % i == 0：
5.             sum += i
6.     if sum == n：
7.         输出 n
```

### 真实代码
```cpp
#include <iostream>
using namespace std;

int main() {
    for (int n = 2; n <= 1000; n++) {
        int sum = 0;
        // 找因子并累加（优化：只需搜到 n/2）
        for (int i = 1; i <= n / 2; i++) {
            if (n % i == 0) {
                sum += i;
            }
        }
        if (sum == n) {
            cout << n << " ";    // 输出：6 28 496
        }
    }
    cout << endl;
    return 0;
}
```

### 注意点
1. **sum 必须在内层循环前清零**：每次换一个 n，sum 要重新从 0 开始累加，忘了清零会累加前面所有数的结果。
2. **优化枚举范围**：因子搜索范围从 `n-1` 优化到 `n/2`，因为大于 n/2 且小于 n 的数不可能是 n 的因子。
3. **1 不是完数**：1 的真因子之和是 0（1 没有真因子），不等于 1，所以从 2 开始枚举。
4. **1000 以内的完数只有 3 个**：6、28、496。如果输出不止这些，说明逻辑有误。

---

## 题目三：斐波那契数列（模拟算法）

### 核心代码（一句话）
> 模拟的核心：**按照规则，用变量记录当前状态，一步一步更新**。斐波那契的规则是：**第三项 = 前两项之和**，用 `a, b` 两个变量滚动更新即可。

### 自然语言思路
斐波那契数列：1, 1, 2, 3, 5, 8, 13, 21, 34, 55……每一项等于前两项之和。输入 n，输出前 n 项。

第一步，用两个变量 `a` 和 `b` 分别记录"当前项"和"下一项"，初始 `a = 1, b = 1`。
第二步，循环 n 次，每次输出 `a`（当前项），然后计算新的两项：`temp = a + b; a = b; b = temp;`。
第三步，模拟过程：a=1,b=1 → 输出1 → a=1,b=2 → 输出1 → a=2,b=3 → 输出2 → a=3,b=5 → 输出3 …… 就像"滚动更新"。

> 模拟算法 = 读懂题目规则 → 翻译成代码。不需要聪明，只需要认真。

### 伪代码
```
1. 输入 n
2. a = 1, b = 1
3. for i = 1 到 n：
4.     输出 a
5.     temp = a + b
6.     a = b
7.     b = temp
```

### 真实代码
```cpp
#include <iostream>
using namespace std;

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

    int a = 1, b = 1;
    for (int i = 1; i <= n; i++) {
        cout << a << " ";
        int temp = a + b;   // 计算下一项
        a = b;               // a 前进
        b = temp;            // b 前进
    }
    cout << endl;
    return 0;
}
```

### 注意点
1. **更新顺序不能错**：必须先算 `temp = a + b`（基于旧值），再更新 a 和 b。如果先改 a 再算 `a + b`，用的就是新的 a 了，结果全乱。
2. **n=1 和 n=2 的情况**：循环 1 次输出 1，循环 2 次输出 "1 1"。代码不用特殊处理，天然正确。
3. **数据范围**：斐波那契数列增长很快，第 46 项就超过 20 亿了。如果 n 大到 50+，要用 `long long` 替代 `int`（因为 `int` 最大约 21 亿）。
4. **另一种写法 — 数组存储**：`int fib[100]; fib[1]=1; fib[2]=1; fib[i]=fib[i-1]+fib[i-2];` 更直观但占内存。

---

## 枚举 vs 模拟 对比

| 对比维度 | 枚举 | 模拟 |
|----------|------|------|
| 核心思路 | 列举所有可能 → 逐一验证 | 按照规则 → 逐步执行 |
| 适用场景 | 答案范围有限、可以逐一验证 | 题目有明确的步骤描述 |
| 典型题目 | 鸡兔同笼、百钱百鸡、完数 | 斐波那契、杨辉三角、日期计算 |
| 优化方向 | 缩小范围、提前终止、剪枝 | 找规律、用公式替代逐步模拟 |

---

## 本课打油诗

> 枚举就是全试过，循环里面 if 判断。
> 范围要想清边界，找到答案就停站。
> 模拟照着步骤走，题目说啥咱干啥。
> 变量更新看顺序，一步一步不出错。

---

## 课后作业
1. 找出 1000 以内所有的"亲密数对"（a 的因子之和等于 b，b 的因子之和等于 a，且 a ≠ b）
2. 百钱百鸡：公鸡 5 元/只，母鸡 3 元/只，小鸡 1 元 3 只。用 100 元买 100 只鸡，输出所有方案
3. 输出杨辉三角的前 n 行
4. 输出所有三位数的水仙花数（如 153 = 1³ + 5³ + 3³）