一文搞懂穷举算法

在我们的日常生活中，经常会遇到一些需要解决的小问题，这些问题可能并不需要复杂的算法，但是如果我们能够运用穷举算法的思想，就能够轻松地找到问题的答案。本文将介绍穷举算法的基本思想，并通过程序示例来深入了解它的实现过程。
 

一、穷举算法基本思想

穷举算法，顾名思义，就是通过列举所有可能的情况来寻找问题的解决方案。它的核心思想是将问题的所有可能解逐一列举出来，然后逐一判断，找出满足条件的解。
 

二、穷举算法应用场景

穷举算法适用于问题的解空间是有限的，且问题的规模较小的情况；对于某些问题，穷举法是唯一可行的解决方法。
 

三、穷举算法应用示例

鸡兔同笼问题是中国古代著名趣题之一。该问题记载于1500年前的《孙子算经》中：今有雉兔同笼，上有三十五头，下有九十四足，问雉兔各几何？

为了解决这个问题，我们可以使用代数方法。假设鸡的数量为x，兔子的数量为y。我们有以下两个方程：

x + y = 头数
2x + 4y = 脚数

穷举每一个可能的 x（0~头数），通过 x 计算出 y（头数-x），逐个判断 x 和 y 的组合是否符合题目的其它条件（2x + 4y = 脚数），从而得到题目的解。以下为 Python 代码示例：

def jttl(head, foot):
    for x in range(0, head + 1):  # 穷举鸡可能的数目
        y = head - x  # 兔可能的数目
        if 2 * x + 4 * y == foot:  # 满足脚数
            return x, y
 
 
print("鸡兔同笼问题")
head = int(input("请输入头数："))
foot = int(input("请输入脚数："))
x, y = jttl(head, foot)
print(f"{x}只鸡，{y}只兔")

百鸡百钱问题，也是出自《孙子算经》一书：鸡翁一值钱五，鸡母一值钱三，鸡雏三值钱一。百钱买百鸡，问鸡翁、鸡母、鸡雏各几何？

仍然使用代数方法，假设公鸡、母鸡、小鸡的数量分别为 x, y, z，得出以下三元一次方程组：

x + y + z = 100（只）
5x + 3y + z/3 = 100（钱）

可以限定穷举的范围：x 在 0~20 之间，y 在 0~33 之间，z 在 0~99 之间。可以使用两个循环来穷举 x 和 y，然后计算出 z（总数 - x - y），逐个判断 x, y 和 z 的组合是否符合方程组中的其它方程，从而得到题目的解。以下为 Python 代码示例：

for x in range(0, 20):  # 穷举鸡翁可能的数目
    for y in range(0, 33):  # 穷举鸡母可能的数目
        z = 100 - x - y  # 鸡雏的数量
        if 5 * x + 3 * y + z / 3 == 100:  # 判断钱数是否满足条件
            print("鸡翁: %2d, 鸡母: %2d, 鸡雏: %2d" % (x, y, z))

一共有四组解：

鸡翁:  0, 鸡母: 25, 鸡雏: 75
鸡翁:  4, 鸡母: 18, 鸡雏: 78
鸡翁:  8, 鸡母: 11, 鸡雏: 81
鸡翁: 12, 鸡母:  4, 鸡雏: 84

四、总结

穷举算法是一种简单直接的解决问题的方法，适用于小规模问题。随着问题规模的增大，计算量也会增长，导致效率降低（如穷举法破解密码）。因此，在实际应用中，需要根据问题的具体特点选择合适的算法。