经典算法-枚举法（百钱买百鸡问题）

目录

枚举法的基本思想

​​​​​​​题目：百钱买百鸡

方法1：三层循环结构

方法2：二层循环结构

方法3：一层循环结构

---

枚举法的基本思想

枚举法又称穷举法，枚举所有可能状态，并用问题给定的条件来约束状态，检验哪些是需要的，哪些是不需要的。
枚举结构：循环+判断语句。

用枚举法解题的最大缺点是运算量比较大，解题效率不高，如果枚举范围太大（一般以不超过两百万次为限），在时间上就难以承受。
但枚举算法思路简单，程序编写和调试方便，比赛中，时间是有限的，我们比赛的最终目标是求出问题解。
如果题目的规模不是很大，在规定的时间与空间限制内能够求出解，那么最好是采用枚举法。

枚举算法的优化
1)缩小枚举范围
2)减少枚举变量
3)使用其它算法

题目：百钱买百鸡

条件：现有 100 元，一共要买公鸡、母鸡、小鸡三种鸡，已知公鸡 5 元一只，母鸡 3 元一只，1 元可以买三只小鸡。
要求：公鸡、母鸡、小鸡都要有，一共买 100 只鸡。有哪几种买法，公鸡、母鸡、小鸡分别是多少只？

思路：

此题是一个三元一次方程。
假设公鸡、母鸡、小鸡分别有 x只，y只，z只。
条件1：5x + 3y + 1/3z = 100(元)；
条件2：x + y + z = 100(只)；得出 z = 100-x-y；
条件1*3 - 条件 2 得出：
14x + 8y = 200；y = (100-7x)/4；7x < 100 得出 x < 15；

方法1：三层循环结构

枚举变量：公鸡、母鸡、小鸡
枚举范围：公鸡、母鸡、小鸡都是1-100次，总计算次数100*100*100
枚举判断条件：
钱数=100:5公鸡+3母鸡+1/3小鸡=100
总鸡数=100:公鸡+母鸡+小鸡=100
小鸡%3==0
三层循环非常耗时，效率低下，我们要分析一下可以减少哪些循环次数。

for cock in range(1,101):
    for hen in range(1,101):
        for chicken in range(1,101):
             if (5*cock+3*hen+chicken/3==100 and chicken%3==0 and cock+hen+chicken==100):
                 print("公鸡=",cock,"母鸡=",hen,"小鸡=",chicken)

方法2：二层循环结构

枚举变量：公鸡、母鸡、小鸡
枚举范围：公鸡1-18、母鸡1-32、小鸡1-98次，总计算次数18*32*98（根据钱数来优化数量，例如100元钱最多20只公鸡，减掉1只母鸡和1只小鸡，那公鸡最多18只）
枚举判断条件：
钱数=100:5公鸡+3母鸡+1/3小鸡=100
总鸡数=100:公鸡+母鸡+小鸡=100
小鸡%3==0

我们再分析已有的条件，发现小鸡的枚举变量可以去掉。

因为枚举了公鸡和母鸡之后，小鸡的数量是固定的，小鸡=100-公鸡-母鸡；

减少了枚举变量，枚举次数大大减少，优化了循环次数和时间。

枚举变量：公鸡、母鸡
枚举范围：公鸡1-18、母鸡1-32，总计算次数18*32（根据钱数来优化数量，例如100元钱最多20只公鸡，减掉1只母鸡和1只小鸡，那公鸡最多18只）
枚举判断条件：
钱数=100:5公鸡+3母鸡+1/3小鸡=100
小鸡%3==0

#两层循环
for cock in range(1,19):            # 外层循环控制公鸡数cock在1~18
    for hen in range(1,34):         # 内层循环控制母鸡数hen在1~33
        chicken = 100-cock-hen      # 小鸡数chicken的值受cock和hen值的制约
        # 小鸡数chicken应该是三的倍数
        if chicken%3==0 and 5*cock+3*hen+chicken//3==100:    
            print("公鸡=",cock,"母鸡=",hen,"小鸡=",chicken)

输出：

公鸡= 4 母鸡= 18 小鸡= 78
公鸡= 8 母鸡= 11 小鸡= 81
公鸡= 12 母鸡= 4 小鸡= 84

方法3：一层循环结构

我们再次分析条件，看看有没有优化的地方。

根据钱数和鸡数分析

14*cock+8*hen=200
7*cock+4*hen=100
hen=(100-7*cock)//4
chicken=100-cock-(100-7*cock)//4

再次减少枚举变量hen。根据条件7*cock<100，我们发现公鸡数量小于14.

枚举变量：公鸡
枚举范围：公鸡1-14，总计算次数14（根据钱数来优化数量，例如100元钱最多20只公鸡，减掉1只母鸡和1只小鸡，那公鸡最多18只）
枚举判断条件：
钱数=100:5公鸡+3母鸡+1/3小鸡=100
（100-7*cock）%4 == 0
小鸡%3==0

# 只要一层循环，减少运算时间
for cock in range(1,15):
    hen=(100-7*cock)//4    #整数而不是浮点数
    chicken=100-hen-cock
    if((100-7*cock)%4==0):
        print("公鸡=",cock,"母鸡=",hen,"小鸡=",chicken)

输出：

公鸡= 4 母鸡= 18 小鸡= 78
公鸡= 8 母鸡= 11 小鸡= 81
公鸡= 12 母鸡= 4 小鸡= 84