明德-枚举算法

张kk

2026-06-03 17:04:00

发布于：广东

40阅读

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!）
没有更好的算法	有数学公式或贪心解法
用来验证其他算法	对时间要求严格