4.0 KiB
第8课：枚举与模拟（三级工具降维）
等级说明：本课使用三级工具帮助解决一级、二级综合问题。
教学目标
- 理解枚举算法的核心思想：列举所有可能，逐一验证
- 掌握枚举优化的两个技巧：缩小范围、提前终止
- 理解模拟算法的核心思想：按题目描述一步步翻译成代码
核心考点：枚举范围与模拟执行顺序
考什么
枚举所有可能并逐一________，或按题目规则一步一步更新________。
必须理解
枚举三步是：确定________、确定合法________、写出验证________。模拟时必须保持题目规定的________顺序。是否使用 break，取决于题目要________________。
核心写法
for (int i = ________; i <= ________; i++) {
if (____________________) {
// 记录、计数或输出
}
}
for (int i = 1; i <= ________; i++) {
// ____________________
}
常见错误
- 枚举范围漏掉端点会怎样？________________
- 什么情况下不能找到答案就
break？________________ - 模拟步骤颠倒是否会影响答案？________
判断是否掌握
- 我能确定候选变量和完整范围。
- 我能写出验证条件。
- 我能按正确顺序模拟状态变化。
课堂编程题
课堂1：鸡兔同笼【适中】
题目描述： 笼中只有鸡和兔。输入头数与脚数，输出鸡和兔的数量；没有合法方案时输出 NONE。
输入格式： 输入动物总数和脚的总数。
输出格式： 输出鸡的数量和兔的数量，或输出 NONE。
数据范围： 动物总数为 1～1000，脚数为非负整数。
输入样例：
10 28
输出样例：
6 4
解题思路： 枚举鸡的数量，兔的数量由总数减去鸡数得到，再验证脚数。
易错提醒： 枚举范围必须包含 0 和动物总数；题目只需一个方案，找到后可以结束循环。
课堂2：硬币组合【适中】
题目描述： 用 1 元、2 元和 5 元硬币凑出指定金额，要求硬币总数固定。输出所有方案，每行依次输出三种硬币数量。
输入格式： 输入目标金额和硬币总数。
输出格式： 输出全部合法方案；没有方案时输出 NONE。
数据范围： 目标金额和硬币总数均为 1～100。
输入样例：
10 4
输出样例：
1 2 1
解题思路： 枚举 1 元和 2 元硬币数量，5 元硬币数量由总数直接计算，再检查金额。
易错提醒： 第三种硬币无需再枚举；题目要求全部方案，找到后不能提前结束。
课堂3：斐波那契数列【适中】
题目描述： 数列前两项为 1，之后每项等于前两项之和。输入项数，输出前若干项。
输入格式： 输入需要输出的项数。
输出格式： 输出数列前若干项，以空格分隔。
数据范围： 项数为 1～45。
输入样例：
6
输出样例：
1 1 2 3 5 8
解题思路： 用两个变量保存连续两项；先计算下一项，再按顺序更新两个变量。
易错提醒： 更新顺序不能颠倒，必须先用旧值计算下一项。
课堂4：交通灯状态【适中】
题目描述： 交通灯按"绿灯 30 秒、黄灯 5 秒、红灯 25 秒"循环。第 1 秒为绿灯。输入秒数，输出当时颜色以及该颜色已经持续的秒数。
输入格式： 输入一个正整数，表示经过的秒数。
输出格式： 输出颜色和当前颜色已持续的秒数。
数据范围： 秒数不超过十亿。
输入样例：
34
输出样例：
YELLOW 4
解题思路： 一个周期共 60 秒，将时间映射到 1～60，再按三个区间判断。
易错提醒： 第 60 秒仍在本周期，第 61 秒才回到绿灯第 1 秒。
课后作业
请完成本课对应的课后作业，见编程题文件。