20260228 142314 Cpp 入门第十三课

20260228_142314_CPP_入门第十三课.md
发布日期：2026年02月28日
文件：20260228_142314_CPP_入门第十三课.md
最后修改：2026-02-28 14:23:14

第十三章：枚举算法——一一列举，找出答案

你好！欢迎来到第十三章！你有没有遇到过这样的问题：一个密码锁有三位数字，忘了密码，只能一个一个试，直到打开。这种“把所有可能都试一遍”的方法，就是枚举算法（也叫穷举法）。虽然听起来有点笨，但计算机最擅长的就是重复劳动，而且速度飞快！这一章我们就来学习如何用枚举思想解决各种有趣的问题。

13.1 枚举算法程序范例

先来看一个最简单的枚举问题：找出1到100之间所有能被3整除的数。

#include <iostream>
using namespace std;

int main() {
    cout << "1到100之间能被3整除的数有：" << endl;
    for (int i = 1; i <= 100; i++) {
        if (i % 3 == 0) {
            cout << i << " ";
        }
    }
    cout << endl;
    return 0;
}

运行结果：

1到100之间能被3整除的数有：
3 6 9 12 15 18 21 24 27 30 33 36 39 42 45 48 51 54 57 60 63 66 69 72 75 78 81 84 87 90 93 96 99

这就是枚举：把所有可能的数（1到100）都拿出来，逐个判断是否满足条件（能被3整除）。虽然简单，但枚举是很多复杂算法的基础。

13.2 枚举算法的用法

13.2.1 什么是枚举算法？

枚举算法就是把所有可能的情况都列举出来，然后逐个检查哪些是符合要求的。就像警察破案时，把所有嫌疑人一个个调查，找出真正的罪犯。

枚举算法通常包含三个步骤：
1. 确定枚举范围：要试哪些可能性？比如1到100、所有的两位数等。
2. 确定判断条件：什么样的结果是我们要的？比如能被3整除、等于某个值等。
3. 用循环遍历所有可能：用 for 或 while 循环，对每个可能进行判断。

13.2.2 枚举的适用场景

  • 搜索空间有限，能全部枚举完（比如最多几百万次）。
  • 没有更高效的数学方法，或者问题很简单。
  • 常用于密码破解、组合问题、方程求解等。

13.2.3 枚举的优化——剪枝

有些时候枚举的范围很大，但很多情况明显不可能，我们可以提前排除，减少循环次数。这叫做剪枝。

例如，找三位数中满足 a² + b² = c² 的勾股数，如果 a 和 b 都从1枚举到100，c 也要从1到100，三重循环就是100万次。但我们可以利用 c = sqrt(a²+b²) 直接计算，并检查是否为整数，这样大大减少循环。

13.3 编程实例讲解

实例1：百钱买百鸡

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

分析：
- 设公鸡 x 只，母鸡 y 只，小鸡 z 只。
- 满足两个方程：
- x + y + z = 100
- 5x + 3y + z/3 = 100（注意小鸡价格是1元3只，所以 z 必须是3的倍数）
- 枚举范围：x 最多 20（因为5×20=100），y 最多 33（因为3×33=99），z = 100 - x - y 且必须是3的倍数且非负。

#include <iostream>
using namespace std;

int main() {
    cout << "所有可能的买法：" << endl;
    for (int x = 0; x <= 20; x++) {
        for (int y = 0; y <= 33; y++) {
            int z = 100 - x - y;
            if (z >= 0 && z % 3 == 0 && 5*x + 3*y + z/3 == 100) {
                cout << "公鸡：" << x << "只，母鸡：" << y << "只，小鸡：" << z << "只" << endl;
            }
        }
    }
    return 0;
}

运行结果：

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

实例2：水仙花数

题目：水仙花数是指一个三位数，其各位数字的立方和等于该数本身。例如 153 = 1³ + 5³ + 3³。找出所有的水仙花数。

分析：
- 枚举范围：100 到 999。
- 对每个数，分离出百位、十位、个位，计算立方和，判断是否相等。

#include <iostream>
using namespace std;

int main() {
    cout << "水仙花数有：" << endl;
    for (int num = 100; num <= 999; num++) {
        int a = num / 100;            // 百位
        int b = (num / 10) % 10;       // 十位
        int c = num % 10;              // 个位
        if (a*a*a + b*b*b + c*c*c == num) {
            cout << num << " ";
        }
    }
    cout << endl;
    return 0;
}

运行结果：

水仙花数有：
153 370 371 407

实例3：完美数

题目：完美数是指一个数恰好等于它的因子之和（不包括自身）。例如 6 = 1+2+3。找出1000以内的所有完美数。

分析：
- 枚举范围：2 到 1000（因为1不算）。
- 对每个数，找出所有小于它的因子，求和，判断是否相等。

#include <iostream>
using namespace std;

int main() {
    cout << "1000以内的完美数有：" << endl;
    for (int num = 2; num <= 1000; num++) {
        int sum = 0;
        for (int i = 1; i <= num / 2; i++) {   // 因子最大不超过 num/2
            if (num % i == 0) {
                sum += i;
            }
        }
        if (sum == num) {
            cout << num << " ";
        }
    }
    cout << endl;
    return 0;
}

运行结果：

1000以内的完美数有：
6 28 496

实例4：找零问题（枚举+优化）

题目：用1元、2元、5元纸币凑成10元，有多少种凑法？

分析：
- 设1元 x 张，2元 y 张，5元 z 张。
- 方程：x + 2y + 5z = 10，且 x,y,z ≥ 0。
- 枚举范围：z 从0到2（因为5*2=10），y 从0到5，x = 10 - 2y - 5z，检查是否非负。

#include <iostream>
using namespace std;

int main() {
    int count = 0;
    for (int z = 0; z <= 2; z++) {
        for (int y = 0; y <= 5; y++) {
            int x = 10 - 2*y - 5*z;
            if (x >= 0) {
                cout << "1元:" << x << "张, 2元:" << y << "张, 5元:" << z << "张" << endl;
                count++;
            }
        }
    }
    cout << "共有" << count << "种凑法" << endl;
    return 0;
}

实例5：质数判断（枚举因子）

虽然质数判断通常用数学优化，但也可以用枚举思想。

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

bool isPrime(int n) {
    if (n <= 1) return false;
    for (int i = 2; i <= sqrt(n); i++) {   // 枚举可能的因子
        if (n % i == 0) return false;
    }
    return true;
}

int main() {
    int num;
    cout << "请输入一个整数：";
    cin >> num;
    if (isPrime(num)) {
        cout << num << " 是质数" << endl;
    } else {
        cout << num << " 不是质数" << endl;
    }
    return 0;
}

13.4 枚举算法的优化技巧

  1. 缩小枚举范围：分析问题，去掉明显不可能的情况。例如百钱买百鸡中，公鸡最多20只，而不是100。
  2. 减少循环层数：能用公式计算的就不循环。比如勾股数中，c 可以用 a、b 计算。
  3. 利用对称性：如果 a 和 b 互换结果相同，可以只枚举 a ≤ b，避免重复。
  4. 剪枝：在循环中提前判断，如果某个条件已经不满足，就跳过后续循环。

13.5 阶段性编程练习

  1. 练习1：找出100到200之间所有的素数。
  2. 练习2：一个两位数，十位与个位之和是9，十位与个位之积等于这个两位数的一半，求这个两位数。
  3. 练习3：用1元、2元、5元、10元纸币凑成20元，有多少种凑法？
  4. 练习4：找出所有满足 a³ + b³ = c³ + d³ 的1到30之间的整数组合（a,b,c,d互不相等，且 a≤b, c≤d，避免重复）。
  5. 练习5：一个四位数的密码，已知千位是百位的2倍，十位是个位的3倍，且这个四位数各位数字之和是20，求这个密码。

13.6 第13章编程作业

作业1：搬砖问题

36块砖，36人搬，男人一次搬4块，女人一次搬3块，小孩两人抬1块。一次搬完，问男人、女人、小孩各多少人？

作业2：三色球问题

有红、黄、蓝三种颜色的球，红球3个，黄球3个，蓝球6个。从中任意摸出8个球，计算摸出的球的各种颜色搭配。

作业3：ABCD × 4 = DCBA

有一个四位数ABCD（A≠0），乘以4后等于DCBA，求这个四位数。（提示：A只能是1或2，D只能是4或8等）

作业4：完美立方

找出所有满足 a³ = b³ + c³ + d³ 的1到30之间的整数，其中 a,b,c,d 互不相等，且 b≤c≤d。

作业5：熄灯问题（选做）

有一个5×6的灯阵，按下一个灯会改变它自身和上下左右四个灯的状态（亮变灭，灭变亮）。给定初始状态，求一种按法使得所有灯都熄灭。这是一个经典的枚举问题，可以用枚举第一行所有可能（2^6=64种），然后递推后面。

恭喜你完成了第十三章的学习！枚举算法虽然简单，但它是很多复杂算法的基础。当你遇到一个问题不知道怎么做时，不妨想一想：能不能把所有可能都试一遍？加油！🚀