1.3 项目实战

1.3.1 项目描述

公元前5世纪，我国古代数学家张丘建在他的《算经》中提出了著名的百鸡百钱问题。

有一人去买鸡，公鸡每只5元，母鸡每只3元，小鸡3只1元，用100元钱去买100只鸡，公鸡、母鸡、小鸡应该各买多少？

1.3.2 项目分析

根据问题中的约束条件将可能的情况一一列举出来，但如果情况很多，排除一些明显的不合理的情况，尽可能减少问题可能解的列举数目，然后找出满足问题条件的解。

完成百鸡百钱问题的有常规算法（懒惰枚举）和改进算法（非懒惰枚举）两种算法设计，不同算法对于同一问题可以有不同的枚举范围，不同的枚举对象解决问题的效益差别会很大。

（1）算法设计一

懒惰枚举法：首先问题有三种不同的鸡，那么我们可以设公鸡为x只，母鸡为y只，小鸡为z只。由题意给出一共要用100钱买一百只鸡，如果我们全部买公鸡最多可以买100/5＝20只，显然x的取值范围是1～20之间；如果全部买母鸡最多可以买100/3＝33只，显然y的取值范围在1～33之间；如果全部买小鸡最多可以买100*3＝300只，可是题目规定是买100只，所以z的取值范围是1～100.那么约束条件为：x＋y＋z＝100且5*x＋3*y＋z/3＝100。

（2）算法设计二

非懒惰枚举法：假如我设了公鸡和母鸡的个数为x和y了，那么公鸡和母鸡的数量就是确定的，那么小鸡的数量就是固定的为100－x－y，那么此时就不再需要进行枚举了，约束条件就只有一个了：5*x＋3*y＋z/3＝100。

1.3.3 项目编写

算法设计一

算法设计二

运行结果如图1.15所示。