选修1算法与程序设计课件

百鸡问题佛山市高明区第一中学授课人：何桂红百鸡问题佛山市高明区第一中学授课人：何桂红

在求解一个较小规模的问题时，可以根据问题中的约束条件把可能的情况一一列举出来，然后注意尝试从中找到满足约束条件的解，若该问题规模较大，符合条件的情况很多，则需要进一步考虑，排除一些明显不合理的情况，尽可能减少问题可能解的列举数目。在求解一个较小规模的问题时，可以根据问题中的约束条件把百鸡问题的故事:

中国古代数学名著《张邱建算经》中曾记载一道闻名世界的百鸡问题，题曰：“公鸡一只值钱5，母鸡一只值钱3，小鸡三只值钱1，今有钱一百，买鸡一百只，问公鸡、母鸡、小鸡各几何？”

这是一道不定方程的问题，它可以在许多不定方程的书中找到，百鸡问题既很实际又很有趣，在其流传的一千多年中，人们为它的来源编织了很多美妙的传说，下面的故事就是其中的一例：公元前五世纪，有位姓张的贫苦人家的少年，他们全家只靠少年的父亲张老头卖鸡来维持生活。这位少年聪明好学，又特别喜爱数学，他在十二三岁时，就已攻读了《九章算术》等数学名著，当地人称他为“张神童”，“张神童”的名字传开后，引起了一些人的兴趣。一天，一位官员拿来一百文钱，要求按当时的鸡价：公鸡每只五文，母鸡每只三文，小鸡每三只一文，购买恰好一百只鸡。“张神童”为一愁莫展的父亲解决了难题，他给来人送上4只公鸡，18只母鸡和78只小鸡，共百鸡，值钱百文。第二天此人又带来一百文钱，还要买一百只鸡，但不能与上次重复。这次“张神童”让父亲拿出18只公鸡，11只母鸡和81只小鸡，显而易见鸡值百钱，满足了来人的要求。第三天，这个人带着一百文钱再次来到张家，还要求百钱买百鸡，且不能与上两次重复，“张神童”又一次为父亲解了围，他让父亲给来人12只公鸡，4只母鸡和84只小鸡，又凑成了百鸡值百钱，三次的考验使这位官员对“张神童”的神机妙算赞叹不已，从此“张神童”的名气更大了，这位“张神童”据说就是我国著名的数学家张邱建。百鸡问题的故事:具体问题（百鸡问题）：

公鸡一只值钱5，母鸡一只值钱3，小鸡三只值钱1，今有钱一百，买鸡一百只，问公鸡、母鸡、小鸡各几何？分析问题：

百鸡问题实际上是不定方程问题，用现在的解法比较容易。我们不妨设公鸡、母鸡、小鸡各为x、y、z，则根据题意得：求此方程的正整数解。

将（2）×3代入（1）得7x+4y=100……（3）由此得出x是4的倍数，且x＜14，于是x只能是4，8，12代入（3）可得y的三个对应解是8，11，4，所以此问题有三组正整数解：具体问题（百鸡问题）：

公鸡一只值钱5，母具体问题（百鸡问题）：

公鸡一只值钱5，母鸡一只值钱3，小鸡三只值钱1，今有钱一百，买鸡一百只，问公鸡、母鸡、小鸡各几何？分析问题：

百鸡问题实际上是不定方程问题，用现在的解法比较容易。我们不妨设公鸡、母鸡、小鸡各为x、y、z，则根据题意得：求此方程的正整数解。

将（2）×3代入（1）得7x+4y=100……（3）由此得出x是4的倍数，且x＜14，于是x只能是4，8，12代入（3）可得y的三个对应解是8，11，4，所以此问题有三组正整数解：所以y=(100-7x)/4=25-2x+x/4，令x/4=t,（t为整数）所以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

具体问题（百鸡问题）：

公鸡一只值钱5，母百鸡问题:

公鸡一只值钱5，母鸡一只值钱3，小鸡三只值钱1，今有钱一百，买鸡一百只，问公鸡、母鸡、小鸡各几何？算法设计：根据问题中的约束条件将可能的情况一一列举出来，但如果情况很多，排除一些明显的不需要理会的情况，尽可能减少问题可能解的列举数目，然后找出满足问题条件的解。完成百鸡百钱问题的常规算法（懒惰枚举）的实现和改进算法（非懒惰枚举）的实现，以证明对于同一问题可以有不同的枚举范围，不同的枚举对象，解决问题的效益差别会很大。百鸡问题:

公鸡一只值钱5，母鸡一只值钱3百鸡问题:

公鸡一只值钱5，母鸡一只值钱3，小鸡三只值钱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。则x,y,z当前的值就是答案。百鸡问题:

公鸡一只值钱5，母鸡一只值钱3算法思想一的流程图：开始定义x,y,z,cont变量X<=20y<=33z<=33百鸡和百钱？输出百鸡以及统计时间的结果YYYY结束NNNN请同学们根据流程图，设计程序。算法思想一的流程图：开始定义x,y,z,cont变量X<=2算法一参考程序代码：PrivateSubCommand1_Click()Dimx,y,z,contAsLongcont=0Print"公鸡母鸡小鸡"Forx=1To20Fory=1To33Forz=1To100Ifx+y+z=100And5*x+3*y+1/3*z=100ThenPrintx,y,zcont=cont+1NextzNextyNextxPrint"共计算";cont;"次。"EndSub百鸡问题:

公鸡一只值钱5，母鸡一只值钱3，小鸡三只值钱1，今有钱一百，买鸡一百只，问公鸡、母鸡、小鸡各几何？算法一参考程序代码：PrivateSubCommand1百鸡问题:

公鸡一只值钱5，母鸡一只值钱3，小鸡三只值钱1，今有钱一百，买鸡一百只，问公鸡、母鸡、小鸡各几何？算法设计：此算法的流程图算法思想二

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

公鸡一只值钱5，母鸡一只值钱3算法思想二的流程图：开始定义x,y,z,cont变量X<=20y<=33如果zmod3=0and5*x+3*y+z/3=100输出百鸡以及统计时间的结果YYY结束NNNZ=100-x-y请同学们根据流程图，设计程序。算法思想二的流程图：开始定义x,y,z,cont变量X<=2算法二参考程序代码：PrivateSubCommand2_Click()Dimx,y,contAsLongcont=0Print"公鸡母鸡小鸡"Forx=1To20Fory=1To33z=100-x-yIfzMod3=0And5*x+3*y+z/3=100ThenPrintx,y,zcont=cont+1NextyNextxPrint"共计算";cont;"次。"EndSub百鸡问题:

公鸡一只值钱5，母鸡一只值钱3，小鸡三只值钱1，今有钱一百，买鸡一百只，问公鸡、母鸡、小鸡各几何？算法二参考程序代码：PrivateSubCommand2算法分析：百鸡问题:

公鸡一只值钱5，母鸡一只值钱3，小鸡三只值钱1，今有钱一百，买鸡一百只，问公鸡、母鸡、小鸡各几何？懒惰枚举法需要尝试20*34*100=66000次，算法的效率显然很低。非懒惰枚举法只须尝试20*33=660次。实现时约束条件又限定z能被3整除时，才会判断“5*x+3*y+z/3=100”。这样省去了不整除3时的算术计算和条件判断，进一步提高了算法的效率。算法分析：百鸡问题:

公鸡一只值钱5，母鸡结束语：百鸡问题:

公鸡一只值钱5，母鸡一只值钱3，小鸡三只值钱1，今有钱一百，买鸡一百只，问公鸡、母鸡、小鸡各几何？通过以上两种算法可以看出，枚举法是蛮力策略的一种表现形式，也是一种使用非常普遍的思维方法。然而对于同一个问题，可以选择不同的枚举范围、不同的枚举对象，这样解决问题的效率差别可能会很大。所以选择合适的方法会让解决问题的效率大大提高。希望同学们通过这节课，能感受到算法与程序设计的魅力，我们要继续加油，在算法的道路中，走的更远。结束语：百鸡问题:

公鸡一只值钱5，母鸡一百鸡问题佛山市高明区第一中学授课人：何桂红百鸡问题佛山市高明区第一中学授课人：何桂红

在求解一个较小规模的问题时，可以根据问题中的约束条件把可能的情况一一列举出来，然后注意尝试从中找到满足约束条件的解，若该问题规模较大，符合条件的情况很多，则需要进一步考虑，排除一些明显不合理的情况，尽可能减少问题可能解的列举数目。在求解一个较小规模的问题时，可以根据问题中的约束条件把百鸡问题的故事:

中国古代数学名著《张邱建算经》中曾记载一道闻名世界的百鸡问题，题曰：“公鸡一只值钱5，母鸡一只值钱3，小鸡三只值钱1，今有钱一百，买鸡一百只，问公鸡、母鸡、小鸡各几何？”

这是一道不定方程的问题，它可以在许多不定方程的书中找到，百鸡问题既很实际又很有趣，在其流传的一千多年中，人们为它的来源编织了很多美妙的传说，下面的故事就是其中的一例：公元前五世纪，有位姓张的贫苦人家的少年，他们全家只靠少年的父亲张老头卖鸡来维持生活。这位少年聪明好学，又特别喜爱数学，他在十二三岁时，就已攻读了《九章算术》等数学名著，当地人称他为“张神童”，“张神童”的名字传开后，引起了一些人的兴趣。一天，一位官员拿来一百文钱，要求按当时的鸡价：公鸡每只五文，母鸡每只三文，小鸡每三只一文，购买恰好一百只鸡。“张神童”为一愁莫展的父亲解决了难题，他给来人送上4只公鸡，18只母鸡和78只小鸡，共百鸡，值钱百文。第二天此人又带来一百文钱，还要买一百只鸡，但不能与上次重复。这次“张神童”让父亲拿出18只公鸡，11只母鸡和81只小鸡，显而易见鸡值百钱，满足了来人的要求。第三天，这个人带着一百文钱再次来到张家，还要求百钱买百鸡，且不能与上两次重复，“张神童”又一次为父亲解了围，他让父亲给来人12只公鸡，4只母鸡和84只小鸡，又凑成了百鸡值百钱，三次的考验使这位官员对“张神童”的神机妙算赞叹不已，从此“张神童”的名气更大了，这位“张神童”据说就是我国著名的数学家张邱建。百鸡问题的故事:具体问题（百鸡问题）：

公鸡一只值钱5，母鸡一只值钱3，小鸡三只值钱1，今有钱一百，买鸡一百只，问公鸡、母鸡、小鸡各几何？分析问题：

百鸡问题实际上是不定方程问题，用现在的解法比较容易。我们不妨设公鸡、母鸡、小鸡各为x、y、z，则根据题意得：求此方程的正整数解。

将（2）×3代入（1）得7x+4y=100……（3）由此得出x是4的倍数，且x＜14，于是x只能是4，8，12代入（3）可得y的三个对应解是8，11，4，所以此问题有三组正整数解：具体问题（百鸡问题）：

公鸡一只值钱5，母具体问题（百鸡问题）：

公鸡一只值钱5，母鸡一只值钱3，小鸡三只值钱1，今有钱一百，买鸡一百只，问公鸡、母鸡、小鸡各几何？分析问题：

百鸡问题实际上是不定方程问题，用现在的解法比较容易。我们不妨设公鸡、母鸡、小鸡各为x、y、z，则根据题意得：求此方程的正整数解。

将（2）×3代入（1）得7x+4y=100……（3）由此得出x是4的倍数，且x＜14，于是x只能是4，8，12代入（3）可得y的三个对应解是8，11，4，所以此问题有三组正整数解：所以y=(100-7x)/4=25-2x+x/4，令x/4=t,（t为整数）所以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

具体问题（百鸡问题）：

公鸡一只值钱5，母百鸡问题:

公鸡一只值钱5，母鸡一只值钱3，小鸡三只值钱1，今有钱一百，买鸡一百只，问公鸡、母鸡、小鸡各几何？算法设计：根据问题中的约束条件将可能的情况一一列举出来，但如果情况很多，排除一些明显的不需要理会的情况，尽可能减少问题可能解的列举数目，然后找出满足问题条件的解。完成百鸡百钱问题的常规算法（懒惰枚举）的实现和改进算法（非懒惰枚举）的实现，以证明对于同一问题可以有不同的枚举范围，不同的枚举对象，解决问题的效益差别会很大。百鸡问题:

公鸡一只值钱5，母鸡一只值钱3百鸡问题:

公鸡一只值钱5，母鸡一只值钱3，小鸡三只值钱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。则x,y,z当前的值就是答案。百鸡问题:

公鸡一只值钱5，母鸡一只值钱3算法思想一的流程图：开始定义x,y,z,cont变量X<=20y<=33z<=33百鸡和百钱？输出百鸡以及统计时间的结果YYYY结束NNNN请同学们根据流程图，设计程序。算法思想一的流程图：开始定义x,y,z,cont变量X<=2算法一参考程序代码：PrivateSubCommand1_Click()Dimx,y,z,contAsLongcont=0Print"公鸡母鸡小鸡"Forx=1To20Fory=1To33Forz=1To100Ifx+y+z=100And5*x+3*y+1/3*z=100ThenPrintx,y,zcont=cont+1NextzNextyNextxPrint"共计算";cont;"次。"EndSub百鸡问题:

公鸡一只值钱5，母鸡一只值钱3，小鸡三只值钱1，今有钱一百，买鸡一百只，问公鸡、母鸡、小鸡各几何？算法一参考程序代码：PrivateSubCommand1百鸡问题:

公鸡一只值钱5，母鸡一只值钱3，小鸡三只值钱1，今有钱一百，买鸡一百只，问公鸡、母鸡、小鸡各几何？算法设计：此算法的流程图算法思想二

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

公鸡一只值钱5，母鸡一只值钱3算法思想二的流程图：开始定义x,y,z,cont变量X<=20y<=33如果zmod3=0and5*x+3*y+z/3=100输出百鸡以及统计时间的结果YYY结束NNNZ=100-x-y请同学们根据流程图，设计程序。算法思想二的流程图：开始定义x,y,z,cont变量X<=2算法二参考程序代码：PrivateSubCommand2_Click()Dimx,y,contAsL