友情提示：视频教程观看时请手动设置清晰度。
第四讲 Scratch编程思想与数学问题（一）
本讲通过Scratch编程与数学问题的结合，讲解计算机编程中的主要思想，并利用Scratch求解三个典型的数学问题。
第四讲的第一节，主要讲解穷举的思想，并通过穷举法，求解数学中著名的百鸡问题。程序运行效果请看视频。
一、百鸡问题简介
百鸡问题，是一道中国古老的数学题，这个问题是这样的。
已知公鸡5块钱一只，母鸡3块钱一只，小鸡三只一块钱，现在用一百块钱正好买一百只鸡，问一共买了公鸡多少只，母鸡多少只，小鸡多少只。
（以下部分为用方程的方法求解答案，对于没有学过方程的低年级小朋友，这段可以忽略不看）
这个问题，从现代数学的角度看，是一道典型的不定方程求解整数解的问题。根据题意，可以列出如下的方程组：
设公鸡、母鸡、小鸡分别为x、y、z 只
x+y+z =100……①
5x+3y+(1/3)z=100……②
有两个方程，三个未知量，称为不定方程组，有多种解。
令②×3－①得：7x+4y=100；
所以y=(100-7x)/4=25-2x+x/4
因为x<21（否则5*x>100），y为整数
所以X的取值只能是0……20之间4的整数倍，只能取0，4，8，12，16，20
又因为y=25-2x+x/4，y>0
所以x<15，剔除掉16，20，x只能取0，4，8，12
最后答案：
x=0；y =25；z =75
x =4；y =18；z =78
x =8；y =11；z =81
x =12；y =4；z =84
（注意，百鸡问题根据题目假设是否可以买0只公鸡，第一组答案可有可没有，这个要根据题目要求，这里假设可以买0只公鸡）。
二、百鸡问题的电脑求解思路
以上是我们通过不定方程的方式求解百鸡问题的计算过程。我们发现这种方法对于大家的数学能力其实还是有一点要求的。现在我们需要问一下，如果使用电脑编程，我们怎么去求解百鸡问题呢？
这里我们介绍一种电脑求解数学问题的最常用思路。
我们首先回到问题本身，暂时忘掉你学过的数学方程，对于这个问题，最简单的思考方式是这样的：
我们随便假设三个数字，比如先假设公鸡有0只，母鸡有0只，小鸡有0只，我们看看这个假设的数字，能否同时满足两个条件，即鸡的总数为100，花费的总钱数为100，很显然这组数字是不满足要求的。
接着我们再假设另外一组数字，公鸡0只，母鸡0只，小鸡1只，再看看是否满足题目要求。
……
以此类推
我们知道，数字是有无穷多个的，实际上我们不可能尝试所有的数字，但是通过分析题目，我们是可以缩小尝试的范围的。比如鸡的总数有100只，所以不管公鸡、母鸡、小鸡，数量都不可能大于100，否则就没有意义了。
因为总钱数是100，所以公鸡的数量不能超过20，母鸡不能超过33，否则也不满足题目条件。
通过缩小数字的范围，我们可以把答案限定在有限组数字之内。这时，我们只需要把所有有限组可能的数字都尝试一次，就可以确切的知道究竟有哪些组数字，是可以满足题目要求的了。
如果是用人来完成这个工作，工作量是非常大的，需要很多时间，而且过程中还可能出现错误。但是通过计算机，我们可以很快的完成大量的数据运算工作。因此我们只需要把这个计算的思路，通过编程的形式告诉计算机，计算机就可以在很短的时间内完成运算并求出答案。
以上我们思考问题的方法，被称之为穷举法。穷举法的基本思想是根据题目的部分条件确定答案的大致范围，并在此范围内对所有可能的情况逐一验证，直到全部情况验证完毕。下面我们就通过穷举法，来求解百鸡问题的答案
三、Scratch编程解决百鸡问题的代码
穷举法，是把所有可能的答案全部验证一遍，因此，穷举法的关键就是如何设计规则，来保证所有的可能答案全部被验证到。对于自然数来说，最常见的方法是通过循环，来遍历所有的备选答案。
在Scratch中首先定义三个变量，分别叫做公鸡计数、母鸡计数、小鸡计数。这三个变量用于存储我们假设的备选答案。
下面这段代码，用于对所有可能的备选答案遍历一遍
并将答案保存在一个新建的链表当中。
这段代码通过三组循环来遍历所有答案，首先最外层，假设公鸡=0，其次第二层，假设母鸡=0，最后在第三层内控制小鸡的数量，小鸡计数从0到100循环101次，然后比较两个条件，一个是公鸡+母鸡+小鸡是否等于100，一个是公鸡母鸡小鸡的花费是否等于100，如果两个条件都满足，则说明这组数字是符合题目要求的，因此把这组数字保存在答案链表当中。
当小鸡循环结束后，让第二层的母鸡数量+1，这个时候公鸡=0，母鸡=1，小鸡再次从0开始到100做一次循环。当母鸡循环达到33时，公鸡数量+1，重新开始循环遍历所有数字。
通过这样一组三层循环的结构，我们就可以对所有的备选答案进行验证，并将符合条件的数字作为正确答案，存入最终结果链表。
实际编程中，我们还可以通过题目条件，进一步简化循环的过程，帮助计算机先期排除一些不可能的答案，进一步缩小穷举的范围。比如我们通过题目可以得出，小鸡数量=100-公鸡数量-母鸡数量。因此，我们可以把三层循环修改为两层。请看如下代码
这里通过对小鸡计数的直接设定，来减少一层循环，同时减少了“如果……”语句这里的判定条件。
最后我们给这段代码再进一步丰富，给小猫添加上输出答案的功能。全部代码如下：
始发于微信公众号：
一人耕者