【MagO第三期】经典枚举算法题：百钱买百鸡

01

历史故事

张邱建提出的百钱买百鸡问题：

山东临清的数学家——张邱建，约公元5世纪著名的大数学家。他将毕生的精力投入到算学研究之中，为数学的不断发展和完善，做出了重大贡献。

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

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

02

百钱买百鸡问题

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

题目答案应为四组解：

公鸡有0 母鸡有25 小鸡有75

公鸡有4 母鸡有18 小鸡有78

公鸡有8 母鸡有11 小鸡有81

公鸡有12 母鸡有4 小鸡有84

题目链接地址：

https://oj.coding61.com/problem/%E6%9E%9A%E4%B8%BE-20

03

思路分析

假设公鸡、母鸡、小鸡数量分别为mj,gj和xj。根据百钱买百鸡的规则可以得到如下不定方程组。

（1）gj+mj+xj=100

（2）5*gj+3*mj+1*xj=100

由于“百钱”是定值，所以 mj,gj和xj有取值范围。5*gj