枚举与模拟经典例题

枚举与模拟：从百元买百鸡学会暴力解题

枚举和模拟是编程中最基础、最直接的解题方法。当你面对一个问题，不知道该用什么高级算法时，不妨试试“暴力破解”——把所有可能的情况都试一遍，让计算机替你检查，这就是枚举；而模拟则是让程序一步一步模仿现实过程，比如计算游戏角色移动、模拟排队等待。这两种方法在 CSP-J 的题目中非常常见，尤其是入门阶段。下面我们用一个经典的“百元买百鸡”故事，带你彻底搞懂枚举和模拟。

1. 什么是枚举？ —— 像查字典一样挨个试

枚举（也叫穷举法）就是把所有可能的情况都列出来，然后逐一检查是否符合条件。就像你去超市找一款饮料，不知道它在哪个货架，那就从第一排走到最后一排，每排每个位置都看一眼——虽然慢，但一定找得到。

生活中的例子：
老师让你猜一个1到100之间的数字，你可以从1开始，一个一个猜：“是1吗？不是。是2吗？不是……是66吗？是的！”这就是枚举。计算机做这件事比人快得多，一秒能试几千万次。

枚举的要点：

• 确定范围：哪些数值需要尝试？比如公鸡数量可以是0~100，但可以缩小范围（比如公鸡最多20只，因为20×5=100元已经花完）。
• 列出所有组合：一般用循环嵌套来遍历每一种可能。
• 检查条件：用 if 语句判断当前组合是否满足题目要求。
• 注意整数与小数：涉及到除法时，要确保能整除，避免出现“半只鸡”的尴尬。

2. 经典入门：百元买百鸡（枚举实现）

题目：用100元买100只鸡，公鸡5元1只，母鸡3元1只，小鸡1元3只。问公鸡、母鸡、小鸡各多少只？

完整代码（原版保留）

#include <iostream>
using namespace std;
int main() {
    // 公鸡5元，母鸡3元，小鸡1元三只
    // 用100元买100只鸡
    for (int g = 0; g <= 100; ++g) {            // 枚举公鸡数量
        for (int m = 0; m <= 100; ++m) {        // 枚举母鸡数量
            int x = 100 - g - m;                // 小鸡数量
            if (x < 0) continue;                // 小鸡不能是负数
            // 总价 = 公鸡*5 + 母鸡*3 + 小鸡/3 (因为三只一元)
            int money = g * 5 + m * 3 + x / 3;
            // 检查总价是不是100元，并且小鸡只数能被3整除
            if (money == 100 && x % 3 == 0) {
                cout << g << "只公鸡, " << m << "只母鸡, " << x << "只小鸡" << endl;
            }
        }
    }
    return 0;
}

代码解释：

• 外层循环枚举公鸡数量 g，从0到100。实际上公鸡最多20只（20×5=100），但这里为了简单，直接枚举到100（后面会检查总价）。
• 内层循环枚举母鸡数量 m，同样从0到100。
• 小鸡数量 x 直接用总只数减去公鸡和母鸡：100 - g - m。
• 检查 x < 0 跳过非法情况（比如公鸡母鸡加起来超过100）。
• 计算总价时，注意小鸡是“三只一元”，所以实际价格是 x / 3，但前提是 x 能被3整除。用 x % 3 == 0 检查。
• 如果总价等于100并且整除条件成立，就输出结果。

运行结果（四种买法）：

0只公鸡, 25只母鸡, 75只小鸡  
4只公鸡, 18只母鸡, 78只小鸡  
8只公鸡, 11只母鸡, 81只小鸡  
12只公鸡, 4只母鸡, 84只小鸡  

3. 枚举的优化：减少无用的尝试

上面的代码虽然正确，但循环次数太多了：外层100次，内层100次，总共10000次。其实我们可以通过数学关系缩小范围：

• 公鸡最多20只（因为5×20=100，就算母鸡小鸡不花钱也不可能更多）。
• 母鸡最多33只（3×33=99，还剩1元买不了小鸡？但是总数量要100，所以母鸡最多33只，但实际还要考虑小鸡的3倍关系）。
• 更聪明的做法：根据总价和总量列方程，但初学者只需要知道枚举时范围可以更精确，比如 g <= 20，m <= 33。

// 优化版循环范围
for (int g = 0; g <= 20; ++g) {           // 公鸡最多20只
    for (int m = 0; m <= 33; ++m) {       // 母鸡最多33只
        int x = 100 - g - m;              // 小鸡数量
        if (x % 3 != 0) continue;         // 小鸡数量必须是3的倍数
        if (g * 5 + m * 3 + x / 3 == 100) {
            // 输出结果
        }
    }
}

这样循环次数从10000降到714次，快了很多。

4. 什么是模拟？ —— 让程序“演一遍”过程

模拟就是按照题目描述的规则，一步一步进行“表演”。比如你要写一个程序判断一个同学从排队到买饭需要多长时间，你可以用变量记录时间，每一步更新状态（人往前走、点餐、付款）。模拟不需要试所有可能，而是严格按照步骤执行。

生活中的例子：
老师让全班同学按学号轮流回答一个问题，学号1回答完，学号2回答，一直到最后一个人。你可以用循环模拟这个过程：用变量表示当前学号，每次加1，直到超过总人数。

模拟的一般步骤：

1. 定义状态变量（位置、时间、分数、人数等）。
2. 按照题目描述的次序一步步更新状态。
3. 在每一步可能进行判断，比如是否到达终点，是否满足条件。
4. 最后输出结果。

一个小模拟例子：
模拟一只蜗牛爬井，井深10米，白天爬3米，晚上滑2米，问第几天爬出井？
代码片段：

int deep = 0;                // 当前深度
int day = 0;                 // 天数
while (deep < 10) {          // 没到井口就继续
    day++;                   // 新的一天
    deep += 3;               // 白天爬3米
    if (deep >= 10) break;   // 如果白天就爬出，结束
    deep -= 2;               // 晚上滑2米
}
cout << day << "天爬出" << endl;

5. 枚举与模拟的“黄金搭档”

很多题目既需要枚举所有可能，又需要模拟过程。比如：枚举游戏的每一步操作，然后模拟这个操作后的结果，判断是否成功。在 CSP-J 中，这类题目通常被称为“暴力模拟”或“枚举+模拟”。

例子：
有一个棋盘，机器人从(0,0)出发，每次可以向上、下、左、右走一步。问走恰好5步后，有多少种不同的路径能到达终点(2,3)？
解法：枚举所有可能的路径（每个方向有4种选择，共4^5=1024种），然后模拟每一步走法的结果，检查最后位置是否等于(2,3)。这就是枚举+模拟。

6. 新手最容易犯的错误

1. 枚举范围太大或太小

   • 太大导致超时（比如循环10亿次）。
   • 太小漏掉正确答案，比如把小鸡数量的上限定为99（实际可以到100）。
     解决：先根据条件粗略估算最大值，如果时间允许，可以稍微扩大。

2. 整数除法与整除条件

   • 在百元买百鸡中，x / 3 是整数除法，如果 x 不是3的倍数，比如 x=4，4/3 结果是1（而不是1.333），这就导致总价计算错误。
   • 所以必须加上 x % 3 == 0 的条件。
     教训：涉及除法时，一定要先判断能否整除。

3. 循环嵌套顺序导致重复或遗漏

   • 比如在枚举中，如果直接 for (int g = 0; g <= 20; g++) 但忘了 m 也有限制，可能造成某只鸡的种类被重复计算？不会，因为嵌套循环每种组合只出现一次。但要注意不要用多重循环时把条件写错。

4. 忘记 continue 或 break

   • 比如小鸡数量为负数时，直接跳过不处理，否则后面 x%3 会出错（负数取模结果非预期）。

5. 模拟时变量更新顺序错误

   • 比如先减后加，结果就错了。一定要按照题目描述的先后顺序写代码。

7. 完整代码示例（带注释的优化版）

#include <iostream>
using namespace std;
int main() {
    // 公鸡5元，母鸡3元，小鸡1元三只，100元买100只
    cout << "所有可能的买法：" << endl;
    
    // 枚举公鸡数量：最多20只（20*5=100）
    for (int g = 0; g <= 20; ++g) {
        // 枚举母鸡数量：最多33只（33*3=99，剩下1元买小鸡，但需要凑100只，实际上更少）
        for (int m = 0; m <= 33; ++m) {
            int x = 100 - g - m;          // 小鸡数量
            if (x < 0) continue;          // 排除总数超过100的情况
            if (x % 3 != 0) continue;     // 小鸡只数是3的倍数才能按1元3只算
            
            // 计算总价
            int money = g * 5 + m * 3 + x / 3;
            if (money == 100) {
                cout << "公鸡=" << g << ", 母鸡=" << m << ", 小鸡=" << x << endl;
            }
        }
    }
    return 0;
}

运行输出（和之前一样）：

所有可能的买法：
公鸡=0, 母鸡=25, 小鸡=75
公鸡=4, 母鸡=18, 小鸡=78
公鸡=8, 母鸡=11, 小鸡=81
公鸡=12, 母鸡=4, 小鸡=84

8. 小挑战（自己动手试试）

把题目改一下：公鸡6元一只，母鸡4元一只，小鸡1元三只，依然100元买100只鸡。请你修改上面的代码，把单价数字换掉，然后运行看看结果。提示：公鸡最多16只（16×6=96），母鸡最多25只（25×4=100）。试试看你能得到几种答案？

9. 相关知识点指引

• 循环结构：for 循环是枚举的基础，必须熟练掌握。
• 条件判断：if 语句用来检查是否满足条件。
• 整数运算：取模 % 和整除 / 在枚举模拟中经常用到。
• 变量与数据类型：int 类型足够表示题目中的数量。
• 时间复杂度初步：了解枚举次数，避免超时。
• 接下来可以学习：暴力搜索（DFS/BFS）、模拟算法进阶（如日期模拟、队列模拟）。

记住：计算机最不怕重复，让枚举和模拟帮你“自动思考”。多写多练，你也能成为暴力破解高手！