L20-深高北-枚举算法
2026-04-24 17:22:36
发布于：广东
106阅读
0回复
0点赞
《枚举算法笔记》
一句话理解
枚举：把所有可能的情况一个一个试，找出正确答案。
就像开密码锁，从 000 试到 999，总有一个能打开。
一、什么是枚举
枚举 = 列出所有可能性 + 逐个检查
优点：简单粗暴，一定能找到答案（只要时间够）
缺点：可能很慢，情况太多时会超时
二、枚举的基本结构
// 枚举的通用模板
for (所有可能的情况) {
if (这种情况满足条件) {
记录答案 / 输出
}
}
三、经典例子
例子1：找最大值
int arr[5] = {3, 8, 2, 10, 5};
int maxVal = arr[0];
for (int i = 0; i < 5; i++) {
if (arr[i] > maxVal) {
maxVal = arr[i];
}
}
cout << maxVal; // 输出 10
// 枚举了数组中的每一个数
例子2：判断质数
int n = 17;
bool isPrime = true;
for (int i = 2; i < n; i++) {
if (n % i == 0) {
isPrime = false; // 能被整除，不是质数
break;
}
}
if (isPrime) cout << n << "是质数";
// 枚举了 2 到 n-1 的所有数
例子3：百钱百鸡问题
公鸡5文，母鸡3文，小鸡3只1文，100文买100只鸡，各几只？
for (int g = 0; g <= 20; g++) { // 公鸡最多20只
for (int m = 0; m <= 33; m++) { // 母鸡最多33只
int x = 100 - g - m; // 小鸡数量
if (x >= 0 && 5*g + 3*m + x/3 == 100 && x % 3 == 0) {
cout << g << " " << m << " " << x << endl;
}
}
}
// 枚举了所有公鸡和母鸡的可能数量
四、枚举的优化
枚举太慢怎么办？两个常用技巧：
技巧1：减少枚举范围
// 找 a + b = 100 的正整数解
// 笨办法：枚举 a 和 b（100×100=10000种）
for (int a = 1; a <= 100; a++) {
for (int b = 1; b <= 100; b++) {
if (a + b == 100) cout << a << " " << b << endl;
}
}
// 优化：枚举 a，b = 100 - a（只有100种）
for (int a = 1; a <= 99; a++) {
int b = 100 - a;
cout << a << " " << b << endl;
}
技巧2：利用对称性
// 找 a ≤ b 且 a + b = 10
// 优化前：枚举 a 和 b
// 优化后：a 只枚举到 5（因为 a ≤ b，a 最大是 5）
for (int a = 1; a <= 5; a++) {
int b = 10 - a;
cout << a << " " << b << endl;
}
五、时间复杂度
| 枚举类型 | 时间复杂度 | 例子 |
|---|---|---|
| 一重循环 | O(n) | 找最大值 |
| 两重循环 | O(n²) | 百钱百鸡 |
| 三重循环 | O(n³) | 找三个数和为定值 |
注意：n 很大时（如 n=10000），O(n²) 就有一亿种情况，会超时！
六、什么时候用枚举？
| 适合用枚举 | 不适合用枚举 |
|---|---|
| 数据范围小（n ≤ 20） | n 很大（n > 1000） |
| 情况数量有限 | 情况数量爆炸（2ⁿ 或 n!） |
| 没有更好的算法 | 有数学公式或贪心解法 |
| 用来验证其他算法 | 对时间要求严格 |
七、总结
枚举三步走：
- 确定所有可能的情况
- 逐个检查是否满足条件
- 记录符合条件的答案
优点：简单、可靠、不容易错
缺点：可能很慢
口诀：
枚举就是穷举法，一个一个全试它
数据大了会超时，范围小了就用它
有帮助，赞一个