16 百钱买百鸡A

描述

我国古代数学家张丘建在《算经》一书中提出的数学问题：鸡翁一值钱五，鸡母一值钱三，鸡雏三值钱一。百钱买百鸡，如果要求鸡翁、鸡母、鸡雏都不为零，问鸡翁、鸡母、鸡雏各几何？

输入格式

该题目没有输入

输出格式

每行输出一组结果，按鸡翁数、鸡母数、鸡雏数的顺序输出，数字之间用空格分隔；
如果有多组解时，按鸡翁数量由少到多输出;

百钱百鸡是一道非常经典的遍历问题，三个未知数却只有两个方程，数学上不好求解，但可以通过遍历所有可能的公鸡数量、母鸡数量和小鸡数量找到所有正确的解。下面的代码通过三重循环对三种鸡的数量进行遍历，每种鸡都遍历从1-100的每个数量，再满足三个条件即为可能的解：
下面解法最内层语句执行100 100 100次，共100万次。

for cock in range(1,101):     # 从1 开始遍历可能满足要求的公鸡数量
    for hen in range(1,101):  # 从1 开始遍历可能满足要求的母鸡数量
        for chicken in range(3, 101, 3): # 从3开始遍历可能满足要求的小鸡数量，步长为3
            if cock + hen + chicken == 100:
                if 5 * cock + 3 * hen + chicken // 3 == 100:
                    print(cock, hen, chicken)

这三个条件可以合并用一个逻辑运算表达式判定这组数据是否符合要求，即三种鸡的数量共100，三种鸡的总价100。：

if chicken % 3 == 0 and 5 * cock + 3 * hen + chicken // 3 == 100

for cock in range(1,101):     # 从1 开始遍历可能满足要求的公鸡数量
    for hen in range(1,101):  # 从1 开始遍历可能满足要求的母鸡数量
        for chicken in range(3, 101, 3): # 从3开始遍历可能满足要求的小鸡数量，步长为3
            if cock + hen + chicken == 100 and 5 * cock + 3 * hen + chicken // 3 == 100:
                print(cock, hen, chicken)

实际上，当公鸡各母鸡数量确定的时候，小鸡的数量可以用 chicken = 100 - cock - hen 计算获得，不需要再进行遍历，可减少一重循环，总循环次数从100万次降为1 万次。

for cock in range(1,101):     #
    for hen in range(1,101):
        chicken = 100 - cock - hen # 公鸡和母鸡数量确定时，小鸡数量可计算，不需再遍历
        if chicken % 3 == 0 and 5 * cock + 3 * hen + chicken // 3 == 100:
            print(cock, hen, chicken)

根据题目要求，每种鸡都要有，那么公鸡最多不超过20只，母鸡不超过33只，可以缩小区间以减少循环次数：

for cock in range(1,20):                # 因每种鸡都要有，所以公鸡数量不超过20
    for hen in range(1,34):              # 母鸡数量不超过34
        chicken = 100 - cock - hen # 公鸡和母鸡数量确定时，小鸡数量可计算，不需再遍历
        if chicken % 3 == 0 and 5 * cock + 3 * hen + chicken // 3 == 100:
            print(cock, hen, chicken)

如果适当利用数学方法，这个问题的程序还可以近一步修改，根据下面两个公式：
cock + hen + chicken == 100
5 cock + 3 hen + chicken // 3 == 100
约去 chicken：
15 cock + 9 hen + 100 - cock - hen == 300
移项并整理可得：
hen == 25 - cock * 7 // 4
因hen 为正整数，所以cock 必为4的倍数，且最大值不超过12（cock = 16时，hen 为负值了）
cock 取值只能为4，8，12，这样遍历次数可以减少到3次：

for cock in range(4,13,4):
    hen = 25 - cock * 7 // 4
    chicken = 100 - cock - hen
    print(cock, hen, chicken)

如果要求每种鸡数量均不为0，那么此问题有三种可能的购买方案：

4 18 78
8 11 81
12 4 84

如果允许某种鸡的数量为0，则此题有4组解：

0 25 75
4 18 78
8 11 81
12 4 84

我们还可以用蒙特卡洛方法求解这个问题，随机产生公鸡、母鸡和小鸡的数量，若符合条件且是未发现的解，就保存下来：
下面代码的输出结果为：[[8, 11, 81], [12, 4, 84], [4, 18, 78]]

import random
def monte_carlo_cock(num):
    answer = []
    for i in range(num):
        hen = random.randint(1, 20)
        cock = random.randint(1, 33)
        chicken = 100 - cock - hen
        if chicken % 3 == 0 and 5 * cock + 3 * hen + chicken // 3 == 100 and cock + hen + chicken == 100:
            group = [cock, hen, chicken]
            if group not in answer:
                answer.append(group)
    return answer
if __name__ == '__main__':
    result = monte_carlo_cock(10000)
    print(result)