枚举算法¶

1. 枚举思想¶

枚举算法也称为穷举算法，核心思想是：在解决问题时，将事件发生的每一种可能全部列举出来，然后逐一判断，最终得出结论。

在 Python 中，通常通过 while 语句或 for 语句配合 if 判断来实现枚举算法。其基本步骤为：

1. 分析对象：明确枚举的目标变量。
2. 确定范围：划定变量的取值范围。
3. 判断条件：筛选满足条件的解。
4. 逐一测试：在范围内对所有值进行循环测试。

枚举算法的流程可概括为：

判断值是否在范围内 → 判断是否符合条件 → 输出结果或取下一个值 → 直到结束

下面通过两道经典例题来理解这种算法思想。

2. 经典例题一：水仙花数¶

问题描述

"水仙花数"是指一个三位数，其各位数字的立方和等于该数本身。例如 153 是一个水仙花数，因为：

问题分析

• 取值范围：100 ~ 999
• 条件限制：各位数字的立方和等于该数本身

代码实现

count = 0
for i in range(100, 1000):
    count += 1
    a = int(i / 100)        # 百位
    b = int(i / 10 % 10)    # 十位
    c = int((i % 10))       # 个位
    if pow(a, 3) + pow(b, 3) + pow(c, 3) == i:
        print('水仙花数:', i)
print('枚举次数:', count)

运行结果

水仙花数: 153
水仙花数: 370
水仙花数: 371
水仙花数: 407
枚举次数: 900

小结

首先规定枚举范围为 100 ~ 999，再通过 if 判断数值是否满足条件，最后输出枚举次数——这就是一个最简单的枚举问题。

3. 经典例题二：百元买百鸡¶

问题描述

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

问题分析

根据价格快速缩小枚举范围：

由此可以通过两层循环 + 一个判断来枚举所有可能的组合。

代码实现

for rooster in range(21):           # 公鸡 0~20 只
    for hen in range(34):           # 母鸡 0~33 只
        chicken = 100 - rooster - hen
        if chicken >= 0 and rooster * 5 + hen * 3 + chicken / 3 == 100:
            print('公鸡 %d 只 + 母鸡 %d 只 + 小鸡 %d 只 = 100 只。' % (rooster, hen, chicken))

运行结果

公鸡 0 只 + 母鸡 25 只 + 小鸡 75 只 = 100 只。
公鸡 4 只 + 母鸡 18 只 + 小鸡 78 只 = 100 只。
公鸡 8 只 + 母鸡 11 只 + 小鸡 81 只 = 100 只。
公鸡 12 只 + 母鸡 4 只 + 小鸡 84 只 = 100 只。

小结

本题先通过价格约束缩小取值范围：公鸡最多 20 只，母鸡最多 33 只。然后用两层循环分别遍历公鸡和母鸡的数量，小鸡数量由总数 100 减去两者得到，最后用 if 判断总价格是否恰好为 100 元。

4. 总结¶

优点¶

• 直观易懂：枚举法一般是现实问题的"直译"，思路简单清晰。
• 正确性强：基于"枚举所有可能"的思想，理论上能保证找到所有满足条件的解，正确性易于证明。
• 实现方便：程序编写和调试都非常直接，比赛时容易想到并且快速实现。

缺点¶

• 效率较低：枚举法建立在考察大量状态、甚至穷举所有状态的基础上，运算量较大，解题效率不高。
• 范围受限：当枚举范围过大（一般以不超过两百万次为限）时，在时间上就难以承受。

使用建议¶

竞赛的最终目标是求出问题解，时间是有限的。如果题目的规模不是很大，在规定的时间与空间限制内能够用枚举法求出解，那么优先采用枚举法，而无需追求更复杂的算法——这样可以让你把更多时间留给其他难题。