228 lines
9.0 KiB
Markdown
228 lines
9.0 KiB
Markdown
# 第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³）
|