原题解答

本次的题目如下所示（原题出处：NOC）：

《张邱建算经》卷下第三十八题。文曰：“今有鸡翁一值钱五，鸡母一值钱三，鸡雏三值钱一，凡百钱买鸡百只，问鸡翁、母、雏各几何？”在题中有三个未知数，却只有两个方程，为不定方程组。

张邱建对此题给出了三组答案：第一组：公鸡四、母鸡十八，小鸡七十八；第二组：公鸡八、母鸡十一，小鸡八十一；第三组：公鸡十二、母鸡四、小鸡八十四。

题目的意思为：公鸡每只5元，母鸡每只3元，三只小鸡1元，用100元买100只鸡，问公鸡、母鸡、小鸡各多少只？

输入：无

输出：公鸡、母鸡、小鸡的个数，以空格隔开，一行输出一组

输入样例：无

输出样例：

0 25 75

4 18 78

8 11 81

12 4 84

本题是一个典型的不定方程组问题。我们知道，在数学上有n个未知数，就需要有n个方程组成方程组。但是这道题，我们从已知条件只能得出3个未知数和2个方程，假设公鸡、母鸡、小鸡的数量分别为x、y、z：

由于少一个方程，这个方程组我们没有办法求解，理论上有无数个解。但是因为实际问题的限制，方程的解只能是正整数，所以我们可以得到有限个解。遇到此类问题，我依然采用枚举的方式解决问题。

在三个未知数的不定方程组中，我们需要确定其中两个未知数的枚举范围，第三个未知数由方程组中的其中一个方程得到。另一个方程用于做判断条件。这样就得到我们的答案了。

本题中公鸡的价格是每只5元，从总价100元可以得知，公鸡的数量不会超过20只；同理，母鸡的价格为每只3元，母鸡的数量不会超过33只。因此，公鸡的数量范围是0~20、母鸡的数量范围是0~33，小鸡的数量为100-公鸡数量-母鸡数量。

由此思路我们可以得到代码如下：

for cock in range(0, 20):    for hen in range(0, 33):        chick = 100 - cock - hen        if 5 * cock + 3 * hen + chick / 3 == 100:            print(cock, hen, chick)

该题目是一条不定方程题，考查范围包括枚举算法，题目难度：★★★

不定方程组的这类题型只要知道这种解题思路，无论题目如何变化，都能很容易做出来。

我们再来看下一道题，也是一个非常经典的问题：

100匹马驮100担货，大马一匹驮3担，中马一匹驮2担，小马两匹驮1担。编写程序计算大、中、小马的数目。

输入：无

输出：大马、中马、小马的数量，以空格隔开，每行输入一组

输入样例：无

输出样例：

2 30 68

5 25 70

8 20 72

11 15 74

14 10 76

17 5 78

20 0 80

这道题本质上与上一道题没什么差别。同样我们列出方程组：

根据三个未知数都是正整数这个条件，我们可以得出x的取值范围是0~33，y的取值范围是0~50。由第一个方程得出z = 100 - x - y。通过第二个方程验证结果，代码如下：

for large in range(0, 33):    for medium in range(0, 50):        small = 100 - large - medium        if 3 * large + 2 * medium + small / 2 == 100:            print(large, medium, small)