1、选修选修1 1算法与程序设计算法与程序设计选修选修1 1算法与程序设计算法与程序设计百鸡问题百鸡问题佛山市高明区第一中学授课人：何桂红选修选修1 1算法与程序设计算法与程序设计 在求解一个较小规模的问题时，可以在求解一个较小规模的问题时，可以根据问题中的约束条件把可能的情况一一根据问题中的约束条件把可能的情况一一列举出来，然后注意尝试从中找到满足约列举出来，然后注意尝试从中找到满足约束条件的解，若该问题规模较大，符合条束条件的解，若该问题规模较大，符合条件的情况很多，则需要进一步考虑，排除件的情况很多，则需要进一步考虑，排除一些明显不合理的情况，尽可能减少问题一些明显不合理的情况，尽可能减少问
2、题可能解的列举数目。可能解的列举数目。选修选修1 1算法与程序设计算法与程序设计百鸡问题百鸡问题的故事的故事:中国中国古代数学名著张邱建算经中曾记载一道闻名世界的百鸡问题，题古代数学名著张邱建算经中曾记载一道闻名世界的百鸡问题，题曰：曰：“公鸡一只值钱公鸡一只值钱5，母鸡一只值钱，母鸡一只值钱3，小鸡三只值钱，小鸡三只值钱1，今有钱一百，买鸡一，今有钱一百，买鸡一百只，问公鸡、母鸡、小鸡各几何？百只，问公鸡、母鸡、小鸡各几何？”这这是一道不定方程的问题，它可以在许多不定方程的书中找到，百鸡问题是一道不定方程的问题，它可以在许多不定方程的书中找到，百鸡问题既很实际又很有趣，在其流传的一千多年中，
3、人们为它的来源编织既很实际又很有趣，在其流传的一千多年中，人们为它的来源编织了了很很多多美妙美妙的传说，下面的故事就是其中的一例：公元前五世纪，有位姓张的贫苦人家的的传说，下面的故事就是其中的一例：公元前五世纪，有位姓张的贫苦人家的少年，他们全家只靠少年的父亲张老头卖鸡来维持生活。这位少年聪明好学，少年，他们全家只靠少年的父亲张老头卖鸡来维持生活。这位少年聪明好学，又特别喜爱数学，他在十二三岁时，就已攻读了九章算术等数学名著，当又特别喜爱数学，他在十二三岁时，就已攻读了九章算术等数学名著，当地人称他为地人称他为“张神童张神童”，“张神童张神童”的名字传开后，引起了一些人的兴趣。一的名字传开后，
4、引起了一些人的兴趣。一天，一位官员拿来一百文钱，要求按当时的鸡价：公鸡每只五文，母鸡每只三天，一位官员拿来一百文钱，要求按当时的鸡价：公鸡每只五文，母鸡每只三文，小鸡每三只一文，购买恰好一百只鸡。文，小鸡每三只一文，购买恰好一百只鸡。“张神童张神童”为一愁莫展的父亲解决为一愁莫展的父亲解决了难题，他给来人送上了难题，他给来人送上4只公鸡，只公鸡，18只母鸡和只母鸡和78只小鸡，共百鸡，值钱百文。只小鸡，共百鸡，值钱百文。第二天此人又带来一百文钱，还要买一百只鸡，但不能与上次重复。这次第二天此人又带来一百文钱，还要买一百只鸡，但不能与上次重复。这次“张张神童神童”让父亲拿出让父亲拿出18只公鸡，
5、只公鸡，11只母鸡和只母鸡和81只小鸡，显而易见鸡值百钱，满足只小鸡，显而易见鸡值百钱，满足了来人的要求。第三天，这个人带着一百文钱再次来到张家，还要求百钱买百了来人的要求。第三天，这个人带着一百文钱再次来到张家，还要求百钱买百鸡，且不能与上两次重复，鸡，且不能与上两次重复，“张神童张神童”又一次为父亲解了围，他让父亲给来人又一次为父亲解了围，他让父亲给来人12只公鸡，只公鸡，4只母鸡和只母鸡和84只小鸡，又凑成了百鸡值百钱，三次的考验使这位官只小鸡，又凑成了百鸡值百钱，三次的考验使这位官员对员对“张神童张神童”的神机妙算赞叹不已，从此的神机妙算赞叹不已，从此“张神童张神童”的名气更大了，这位
6、的名气更大了，这位“张神童张神童”据说就是我国著名的数学家张邱建。据说就是我国著名的数学家张邱建。选修选修1 1算法与程序设计算法与程序设计具体问题（百鸡问题）：具体问题（百鸡问题）：公鸡一只值钱公鸡一只值钱5，母鸡一只值钱，母鸡一只值钱3，小鸡三只值钱，小鸡三只值钱1，今有钱一百，买鸡一百，今有钱一百，买鸡一百只，问公鸡、母鸡、小鸡各几何？只，问公鸡、母鸡、小鸡各几何？分析问题：分析问题：百鸡问题实际上是不定方程问题，用现在的解法比较容易。我们不妨设公鸡、百鸡问题实际上是不定方程问题，用现在的解法比较容易。我们不妨设公鸡、母鸡、小鸡各为母鸡、小鸡各为x、y、z，则根据题意得：，则根据题意得：
7、求此方程的正整数解。求此方程的正整数解。将（将（2）3代入代入（1）得）得7x+4y=100（3）由此得出）由此得出x是是4的倍数，且的倍数，且x14，于是于是x只能是只能是4，8，12代入（代入（3）可得）可得y的三个对应解是的三个对应解是8，11，4，所以此问题有三，所以此问题有三组正整数解：组正整数解：选修选修1 1算法与程序设计算法与程序设计具体问题（百鸡问题）：具体问题（百鸡问题）：公鸡一只值钱公鸡一只值钱5，母鸡一只值钱，母鸡一只值钱3，小鸡三只值钱，小鸡三只值钱1，今有钱一百，买鸡一百，今有钱一百，买鸡一百只，问公鸡、母鸡、小鸡各几何？只，问公鸡、母鸡、小鸡各几何？分析问题：分析
8、问题：百鸡问题实际上是不定方程问题，用现在的解法比较容易。我们不妨设公鸡、百鸡问题实际上是不定方程问题，用现在的解法比较容易。我们不妨设公鸡、母鸡、小鸡各为母鸡、小鸡各为x、y、z，则根据题意得：，则根据题意得：求此方程的正整数解。求此方程的正整数解。将（将（2）3代入代入（1）得）得7x+4y=100（3）由此得出）由此得出x是是4的倍数，且的倍数，且x14，于是于是x只能是只能是4，8，12代入（代入（3）可得）可得y的三个对应解是的三个对应解是8，11，4，所以此问题有三，所以此问题有三组正整数解：组正整数解：所以y=(100-7x)/4=25-2x+x/4，令x/4=t,（t为整数）所
9、以x=4t，把x=4t代入7x+4y=100得到：y=25-7t，易得z=75+3t，所以：x=4t，y=25-7t，z=75+3t。因为x,y,z大于等于0 所以4t大于等于0，25-7t大于等于0，75+3t大于等于0。解得t大于等于0小于等于25/7 又因为t为整数，所以t=0,1,2,3（这里不要忘记t有等于0得可能）。当t=0时：x=0,y=25,z=75；当t=1时x=4；y=18；z=78当t=2时x=8；y=11；z=81当t=3时x=12；y=4；z=84 选修选修1 1算法与程序设计算法与程序设计百鸡问题百鸡问题:公鸡一只值钱公鸡一只值钱5，母鸡一只值钱，母鸡一只值钱3，小
10、鸡三只值钱，小鸡三只值钱1，今有钱一百，买鸡一百，今有钱一百，买鸡一百只，问公鸡、母鸡、小鸡各几何？只，问公鸡、母鸡、小鸡各几何？算法设计：算法设计：根据问题中的约束条件将可能的情况一一列举出来，但如根据问题中的约束条件将可能的情况一一列举出来，但如果情况很多，排除一些明显的不需要理会的情况，尽可能减少果情况很多，排除一些明显的不需要理会的情况，尽可能减少问题可能解的列举数目，然后找出满足问题条件的解。问题可能解的列举数目，然后找出满足问题条件的解。完成百鸡百钱问题的常规算法（懒惰枚举）的实现和改进完成百鸡百钱问题的常规算法（懒惰枚举）的实现和改进算法（非懒惰枚举）的实现，以证明对于同一问题可
11、以有不同算法（非懒惰枚举）的实现，以证明对于同一问题可以有不同的枚举范围，不同的枚举对象，解决问题的效益差别会很大。的枚举范围，不同的枚举对象，解决问题的效益差别会很大。选修选修1 1算法与程序设计算法与程序设计百鸡问题百鸡问题:公鸡一只值钱公鸡一只值钱5，母鸡一只值钱，母鸡一只值钱3，小鸡三只值钱，小鸡三只值钱1，今有钱一百，买鸡一百，今有钱一百，买鸡一百只，问公鸡、母鸡、小鸡各几何？只，问公鸡、母鸡、小鸡各几何？算法设计：算法设计：此算法的流程图此算法的流程图算法思想算法思想一一懒惰枚举法懒惰枚举法：首先问题有三种不同的鸡，我们可以设公鸡为x只，母鸡为y只，小鸡为z只。由题意给出一共要用1
12、00钱买一百只鸡，如果我们全部买公鸡最多可以买100/5=20只，显然x的取值范围是120之间；如果全部买母鸡最多可以买100/3=33只，显然y的取值范围在133之间；如果全部买小鸡最多可以买100*3=300只，可是题目规定是买100只，所以z的取值范围是1100.那么约束条件为：x+y+z=100且5*x+3*y+z/3=100。则则x,y,z当前的值就是答案。当前的值就是答案。选修选修1 1算法与程序设计算法与程序设计算法思想一的流程图：算法思想一的流程图：开始开始定义定义x,y,zx,y,z,contcont变量变量X=20y=33z=33百鸡和百钱？百鸡和百钱？输出百输出百鸡以及统
13、计鸡以及统计时间的结果时间的结果YYYY结束结束NNNN请同学们根据流程图，设计程序。请同学们根据流程图，设计程序。选修选修1 1算法与程序设计算法与程序设计算法一参考程序代码：Private Sub Command1_Click()Dim x,y,z,cont As Longcont=0Print 公鸡 母鸡 小鸡 For x=1 To 20 For y=1 To 33 For z=1 To 100 If x+y+z=100 And 5*x+3*y+1/3*z=100 Then Print x,y,z cont=cont+1 Next z Next y Next x Print 共计算;co
14、nt;次。End Sub百鸡问题百鸡问题:公鸡一只值钱公鸡一只值钱5，母鸡一只值钱，母鸡一只值钱3，小鸡三只值钱，小鸡三只值钱1，今有钱一百，今有钱一百，买鸡一百只，问公鸡、母鸡、小鸡各几何？买鸡一百只，问公鸡、母鸡、小鸡各几何？选修选修1 1算法与程序设计算法与程序设计百鸡问题百鸡问题:公鸡一只值钱公鸡一只值钱5，母鸡一只值钱，母鸡一只值钱3，小鸡三只值钱，小鸡三只值钱1，今有钱一百，买鸡一百，今有钱一百，买鸡一百只，问公鸡、母鸡、小鸡各几何？只，问公鸡、母鸡、小鸡各几何？算法设计：算法设计：此算法的流程图此算法的流程图算法思想算法思想二二非懒惰枚举法：假如我设了公鸡和母鸡的个数为非懒惰枚举
15、法：假如我设了公鸡和母鸡的个数为x和和y了，那么小鸡和母鸡的数量了，那么小鸡和母鸡的数量就是确定的，那么小鸡的数量就是固定的为就是确定的，那么小鸡的数量就是固定的为100-x-y,此时就不再需要进行枚举了，此时就不再需要进行枚举了，约束条件就只有一个了：约束条件就只有一个了：5*x+3*y+z/3=100.选修选修1 1算法与程序设计算法与程序设计算法思想二的流程图：算法思想二的流程图：开始开始定义定义x,y,z,contx,y,z,cont变量变量X=20y=33如果如果z mod 3=0 and 5*x+3*y+z/3=100输出百输出百鸡以及统计鸡以及统计时间的结果时间的结果YYY结束结
16、束NNNZ=100-x-yZ=100-x-y请同学们根据流程图，设计程序。请同学们根据流程图，设计程序。选修选修1 1算法与程序设计算法与程序设计算法二参考程序代码：Private Sub Command2_Click()Dim x,y,cont As Longcont=0Print 公鸡 母鸡 小鸡 For x=1 To 20 For y=1 To 33 z=100-x-y If z Mod 3=0 And 5*x+3*y+z/3=100 Then Print x,y,z cont=cont+1 Next y Next x Print 共计算;cont;次。End Sub百鸡问题百鸡问题:公
17、鸡一只值钱公鸡一只值钱5，母鸡一只值钱，母鸡一只值钱3，小鸡三只值钱，小鸡三只值钱1，今有钱一百，今有钱一百，买鸡一百只，问公鸡、母鸡、小鸡各几何？买鸡一百只，问公鸡、母鸡、小鸡各几何？选修选修1 1算法与程序设计算法与程序设计算法分析：算法分析：百鸡问题百鸡问题:公鸡一只值钱公鸡一只值钱5，母鸡一只值钱，母鸡一只值钱3，小鸡三只值钱，小鸡三只值钱1，今有钱一百，今有钱一百，买鸡一百只，问公鸡、母鸡、小鸡各几何？买鸡一百只，问公鸡、母鸡、小鸡各几何？懒惰枚举法需要尝试懒惰枚举法需要尝试2020*3434*100=66000100=66000次，算法的效次，算法的效率显然很低。非懒惰枚举法只须率
18、显然很低。非懒惰枚举法只须尝试尝试2020*33=66033=660次。实现时约束次。实现时约束条件又限定条件又限定z z能被能被3 3整除时，才会整除时，才会判断判断“5 5*x+3 x+3*y+z/3=100 y+z/3=100”。这样省去。这样省去了了 不整除不整除3 3时的算术计算和条件判断，进一步提高了时的算术计算和条件判断，进一步提高了算法的效率。算法的效率。选修选修1 1算法与程序设计算法与程序设计结束语：结束语：百鸡问题百鸡问题:公鸡一只值钱公鸡一只值钱5，母鸡一只值钱，母鸡一只值钱3，小鸡三只值钱，小鸡三只值钱1，今有钱一百，今有钱一百，买鸡一百只，问公鸡、母鸡、小鸡各几何？
19、买鸡一百只，问公鸡、母鸡、小鸡各几何？通过以上两种算法可以看出，枚举法是蛮力策通过以上两种算法可以看出，枚举法是蛮力策略的一种表现形式，也是一种使用非常普遍的思维略的一种表现形式，也是一种使用非常普遍的思维方法。然而对于同一个问题，可以选择不同的枚举方法。然而对于同一个问题，可以选择不同的枚举范围、不同的枚举对象，这样解决问题的效率差别范围、不同的枚举对象，这样解决问题的效率差别可能会很大。所以选择合适的方法会让解决问题的可能会很大。所以选择合适的方法会让解决问题的效率大大提高。效率大大提高。希望同学们通过这节课，能感受到算法与程序希望同学们通过这节课，能感受到算法与程序设计的魅力，我们要继续加油，在算法的道路中，设计的魅力，我们要继续加油，在算法的道路中，走的更远。走的更远。
