百钱百鸡问题

《百钱百鸡问题》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

百鸡问题公元5世纪末，我国古代数学家张丘建在他所撰写的《算经》中，提出了这样的一个问题：“鸡翁一，值钱五，鸡母一，值钱三，鸡雏三，值钱一．百钱买百鸡，问鸡翁、鸡母、鸡雏各几何？”意思是公鸡5元一只，母鸡3元一只，小鸡1元三只。用100元100只鸡，求公鸡、母鸡、小鸡各买几只。假设a为公鸡只数，b为母鸡只数，c为小鸡只数，如果把问题转化为n元钱买n只鸡，针对上述问题n=100，根据题意可得出下面的约束方程:用穷举法实现如下所示：

1图4.3穷举法求解百鸡问题这个算法有三重循环，枚举公鸡数量的外循环，枚举母鸡数量的中间循环以及枚举小鸡数量的内循环，主要执行时间取决于内循环的循环体的执行次数，需要执行(n+1)3次，当n=100时，内循环需要执行大于100万次。考虑到n元钱只能买到n/5只公鸡或n/3只母鸡，因此有些组合可以不必考虑，而小鸡的数目又取决于公鸡和母鸡的只数，上述的内循环可以省去。

2上述算法可以改为：图4.3改进算法求解百鸡问题改进算法只有两层循环，枚举公鸡数量的外循环和枚举母鸡数量的内循环，内循环的执行次数为(n/5+1)(n/3+1)。当n=100时，内循环执行21*34=714次，这和穷举算法的100万次相比，仅为原来的万分之七，有重大改进。