CC++ & Algorithm

C++枚举与模拟经典例题

困难24
语言版本:C++Python
概述:通过“百钱百鸡”和“模拟钟表”两个经典例题,展示如何将枚举与模拟用于解决实际问题。

枚举与模拟:用代码解决生活中的计数和过程问题

枚举和模拟是编程中两种非常实用的思想。简单来说,枚举就是“把所有可能性都试一遍”,比如猜数字时,从1猜到100;模拟就是“按照规则一步步做”,比如记下自己从起床到上学每分每秒做的事。在C++中,我们可以用循环和条件语句轻松实现它们。下面通过两个经典例题,你会看到它们是如何解决真实问题的。

枚举:逐项检查,找出所有答案

枚举适合解决“找出所有符合条件的组合”这类问题。比如:你有5元、3元、1元三种面值的硬币,要凑出100元,有多少种方法?枚举就是让程序自动尝试所有可能的硬币数量,检查是否满足条件。

例题1:百钱百鸡——古代数学家的枚举题

中国古代数学家张丘建在《算经》中提出了一道名题:
公鸡5文钱一只,母鸡3文钱一只,小鸡3只一文钱。用100文钱正好买100只鸡,问公鸡、母鸡、小鸡各多少只?

解题思路
我们用三个变量分别表示公鸡、母鸡、小鸡的数量。因为总数量是100只,所以小鸡的数量 = 100 - 公鸡 - 母鸡。我们只需要枚举公鸡和母鸡的数量,然后算出小鸡的数量,再检查总钱数是否等于100文。注意:小鸡3只一文钱,所以小鸡的数量必须是3的倍数。

公鸡最多20只(因为5×20=100),母鸡最多33只(3×33=99),这就是枚举的范围。

代码示例(变量用英文单词,并加中文注释):

#include <iostream>
using namespace std;

int main() {
    cout << "可能的购买方案:" << endl;
    // 枚举公鸡数量,范围0~20
    for (int cock = 0; cock <= 20; cock++) {
        // 枚举母鸡数量,范围0~33
        for (int hen = 0; hen <= 33; hen++) {
            int chick = 100 - cock - hen;      // 小鸡数量 = 100 - 公鸡 - 母鸡
            // 小鸡数量必须非负,且是3的倍数(因为3只1文)
            if (chick >= 0 && chick % 3 == 0) {
                int money = 5 * cock + 3 * hen + chick / 3;
                if (money == 100) {
                    cout << "公鸡=" << cock << " 母鸡=" << hen << " 小鸡=" << chick << endl;
                }
            }
        }
    }
    return 0;
}

运行结果
可能的购买方案:
公鸡=0 母鸡=25 小鸡=75
公鸡=4 母鸡=18 小鸡=78
公鸡=8 母鸡=11 小鸡=81
公鸡=12 母鸡=4 小鸡=84

生活联想
想象一下,你有100元钱,想买100个水果。苹果5元一个,梨3元一个,橘子1元3个。那么你也可以用同样的枚举方法,找出所有可能的购买组合。枚举就是“穷举法”,把所有可能性都列出来,再筛选。

新手容易犯的错误

  1. 枚举范围不对:比如公鸡数量写成 cock <= 100,虽然程序不会错,但会多运行很多无意义的循环,降低效率。正确范围是 cock <= 20(100÷5)。
  2. 忘记小鸡数量的条件:小鸡3只一文钱,所以小鸡数量必须是3的倍数。没有这个检查,可能会输出“公鸡=1 母鸡=1 小鸡=98”这种虽然总钱数对了(5+3+98/3≈5+3+32.667,实际不是整数),但实际买鸡时无法做到。
  3. 误把除法结果当作整数chick / 3 在C++中是整数除法,只有当 chick 是3的倍数时,结果才正确。所以先检查 chick % 3 == 0 是必须的。

模拟:按规则推进,再现过程

模拟适合描述一个随时间或步骤变化的过程。比如:记录一天中的时间流逝、模拟运动员跑步的圈数、计算排队等候的时间等。我们用一个“电子钟表”的例子来理解。

例题2:模拟钟表时钟——一步步走过每一秒

模拟一个电子时钟,从0:00开始,每过1秒,秒针加1,一直走到1:00停止。要求每分钟(即整分钟的时刻)输出一次当前时间。

解题思路
用三个变量 hour, minute, second 分别表示时、分、秒。用一个循环(比如 while)控制时间前进,每次循环代表一秒。每秒秒数加1,然后检查是否需要进位(满60秒进1分钟,满60分钟进1小时)。当秒数为0时(即整分钟),输出当前时间。循环直到小时达到1结束。

代码示例(变量已为英文,加中文注释):

#include <iostream>
#include <iomanip>   // 用于格式化输出,如 setw, setfill
using namespace std;

int main() {
    int hour = 0, minute = 0, second = 0;   // 时、分、秒初始为0
    cout << "模拟开始(只输出整分钟的时刻):" << endl;
    while (hour < 1) {   // 在1小时内循环
        // 模拟一秒过去
        second++;
        if (second == 60) {   // 满60秒进1分钟
            second = 0;
            minute++;
        }
        if (minute == 60) {   // 满60分钟进1小时
            minute = 0;
            hour++;
        }
        // 如果是整分钟(second == 0),则输出当前时间
        if (second == 0) {
            // 用 setw(2) 和 setfill('0') 保证两位宽度,不足补0
            cout << setw(2) << setfill('0') << hour << ":"
                 << setw(2) << setfill('0') << minute << endl;
        }
    }
    return 0;
}

运行结果
模拟开始(只输出整分钟的时刻):
00:00
00:01
00:02
...
00:59

(注意:00:00 在开始时秒数为0,所以立即输出;之后每过60秒输出一次。)

生活联想
想象你在操场跑步,每跑一圈记一次时间。你可以模拟这个过程:从0秒开始,每秒检查是否跑完一圈(比如一圈400米,速度恒定),然后输出圈数和时间。模拟的核心就是“按真实规则一步一步来”。

新手容易犯的错误

  1. 进位顺序搞错:先判断秒满60,再判断分满60。如果先判断分再判断秒,会导致秒数为60时,分钟已经进位了,但秒还没重置。正确顺序是先处理秒的进位,再处理分的进位。
  2. 输出条件判断不对:题目要求“每分钟输出一次”,即秒为0时输出。如果写成 if (second == 0) 放在进位之前,可能输出时秒还是0,但时间已经过了?实际上代码中先增加秒再判断进位,再判断输出,所以第一次循环时秒变成1,不会输出;第二次秒变成2……直到秒变成60,进位后秒为0,然后判断输出。这样每60秒输出一次,正好是整分钟。
  3. 忘记格式化输出:如果不使用 setwsetfill,输出可能是 0:0 而不是 00:00,不符合时间表示习惯。

常见错误汇总(枚举与模拟)

错误类型具体表现解决方法
枚举范围太大或太小漏掉或增加无意义循环仔细分析上限,比如钱数、数量等
缺少关键条件检查输出错误组合仔细阅读题目条件,如倍数关系、非负等
模拟的顺序颠倒进位或输出时机错误按真实过程一步步写,先事件再更新状态
变量未初始化结果随机定义变量时赋初值,如 int hour = 0;
循环条件出错死循环或提前结束检查循环终止条件,如 while (hour < 1)

完整可运行代码示例

下面将上面两个例题的代码整理到一起,方便你直接复制运行。

百钱百鸡(枚举)

#include <iostream>
using namespace std;

int main() {
    cout << "可能的购买方案:" << endl;
    for (int cock = 0; cock <= 20; cock++) {       // 公鸡最多20只
        for (int hen = 0; hen <= 33; hen++) {      // 母鸡最多33只
            int chick = 100 - cock - hen;          // 小鸡数量
            // 小鸡数量非负且是3的倍数
            if (chick >= 0 && chick % 3 == 0) {
                int money = 5 * cock + 3 * hen + chick / 3;
                if (money == 100) {
                    cout << "公鸡=" << cock << " 母鸡=" << hen << " 小鸡=" << chick << endl;
                }
            }
        }
    }
    return 0;
}

模拟钟表(模拟)

#include <iostream>
#include <iomanip>
using namespace std;

int main() {
    int hour = 0, minute = 0, second = 0;   // 初始时间
    cout << "模拟开始(只输出整分钟的时刻):" << endl;
    while (hour < 1) {   // 循环到1小时
        second++;        // 过1秒
        if (second == 60) {
            second = 0;
            minute++;
        }
        if (minute == 60) {
            minute = 0;
            hour++;
        }
        if (second == 0) {   // 整分钟输出
            cout << setw(2) << setfill('0') << hour << ":"
                 << setw(2) << setfill('0') << minute << endl;
        }
    }
    return 0;
}

你可以先编译运行这两个程序,观察输出,再尝试修改参数(比如把100文改为200文,或把模拟时间延长到2小时),加深理解。


相关指引

  • GESP三级考试:枚举与模拟是必考内容,除了百钱百鸡和钟表,还有“猜数字”“数数问题”“排队问题”等。建议多做练习题,熟悉两种思想的典型场景。
  • 进阶学习
    • 枚举可以与剪枝结合,减少循环次数(比如通过数学推导缩小范围)。
    • 模拟时要注意时间复杂度,如果模拟次数很大(比如10亿秒),就需要优化(如用数学公式直接计算)。
    • 在竞赛中,枚举和模拟经常组合使用,比如先枚举所有可能方案,再模拟检查是否可行。
  • 生活延伸:试试用枚举解决“买文具”问题:铅笔2元,笔记本5元,橡皮1元,用20元买10件物品,有多少种买法?用模拟解决“电梯运行”问题:电梯从1层开始,每层停1秒,到顶楼再返回,模拟全程的时间。

掌握枚举和模拟,你就拿到了解决许多实际问题的钥匙。勤加练习,很快你就能写出自己的“解题小工具”。

例题精讲

1单选题

在“百钱百鸡”问题中,公鸡5文一只,母鸡3文一只,小鸡1文三只,用100文买100只鸡。如果用枚举法求解,公鸡数量x的范围最优是?

A0 <= x <= 20
B0 <= x <= 33
C0 <= x <= 100
D0 <= x <= 25
2判断题

在“百钱百鸡”问题中,如果采用三重循环分别枚举公鸡、母鸡、小鸡的数量,并检查总钱数=100且总数量=100,那么枚举次数为101^3,这是不可接受的,因此必须优化枚举范围。

3单选题

模拟钟表问题中,分针每分钟走6度,时针每分钟走0.5度。在3点整时,时针与分针的夹角是多少度?

A90度
B180度
C0度
D45度
4填空题
以下代码是百钱百鸡问题的优化枚举,请填写空缺条件,使得程序输出所有解。\n#include <iostream>\nusing namespace std;\nint main() {\n    for (int x = 0; x <= 20; x++) {\n        for (int y = 0; y <= 33; y++) {\n            int z = 100 - x - y;\n            if (___ ) {\n                cout << x << " " << y << " " << z << endl;\n            }\n        }\n    }\n    return 0;\n}
5填空题
以下代码模拟计算从0:00开始经过t分钟时时针与分针的夹角(取最小角度0~180度)。请填写空缺部分。\n#include <iostream>\n#include <cmath>\nusing namespace std;\nint main() {\n    int t;\n    cin >> t;\n    double hour_angle = 0.5 * t;\n    double minute_angle = 6 * (t % 60);\n    double diff = fabs(hour_angle - minute_angle);\n    double angle = ___;\n    cout << angle << endl;\n    return 0;\n}