Scratch教程：用编程方法解奥数题目”鸡兔同笼”

鸡兔同笼，应该是最经典的小学奥数题目。每个学过奥数的孩子，没有不知道鸡兔同笼的，解题过程，不外乎算术方法和解方程的两种基本解法。那么，怎么才能用计算机编程的方法把题目解出来呢？

 

 

 

这几日，网上有关于鸡兔同笼问题的编程方法的讨论，海有教练团队的老师们也就这个问题开始讨论。

 

 

在Lisa老师看来：

 

根据鸡兔同笼问题，可以设定4个未知数，那就是鸡、兔头脚的数量。

像上图这样，把关系式（方程）列出来，用数学思维先把鸡兔和头脚的关系列方程解答。 

1

先用数学方法把应用题目中的关系用方程式列出来。鸡兔同笼是已知头和脚的数量的，这，可以作为程序的输入部分（C里面是用scanf，C++里面是用cin，Scratch里面使用“回答”）引入已知的数值。

2

然后，我们把手推导出来的公式加入到计算机的运算式里，也就是一条计算机语句。

3

然后，计算机就可以根据输入值，计算出输出值，然后用输出语句给出答案（C里面是用printf，C++里面是用cout，Scratch里面使用“说”）

 

以Scratch编程解题为例

变量这么设定

算法逻辑的主体是这样的：

其中，输入值是这样的（相当于应用题的题干）：

下面是解题的步骤，只需要2条语句，相当于把数学的方程式转换为编程思维的程序语句：

最后，是程序的输出结果，相当于数学应用题的最后的“答”：

如此这样编写，把数学思维转化为编程思维，鸡兔同笼的奥数题用Scratch编程的方法解出来了。

 

当Lisa老师讲解完自己的编程思维后，Marvin老师又讲了这道题目的另一种算法。

 

在Marvin老师看来：

 

鸡兔同笼问题，可以使用“穷举法”来求解。也就是利用计算机的快速计算能力，将所有可能的解的组合都试验一下，从而找到可能的解。

基本思路：

由于用户已经输入了总头数，所以鸡（或兔）的只数只能是从0到总头数。这样，让计算机从0到总头数循环计算去求解。

首先，将兔子的数量设置为0.进入循环（循环的结束条件是兔子的只数大于总只数）。

之后，根据 鸡数＝总头数－兔子数，计算出鸡的数量。

然后，再使用条件判断，看当前的鸡和兔子的脚数一共是多少，是否与给的条件相等。如果相等，则显示结果，并结束程序。

如果试验了所有的可能组合，都没有找到解，则说明给的条件可能存在问题。显示无解。

这种算法的核心思想是用计算机生成并测试所有可能的解，一一测试。如果有多个解，也能够求出来（对于鸡兔问题，只可能有唯一解）。

 

从编程技术上说，一般需要结合循环语句（有时是多重循环），和循环体内的判断语句来完成穷举法。

这个算法的优点是自动对不合法的输入条件进行了处理（会造成无解），缺点是，当解的可能很多时，可能会需要非常长的时间。

破解密码的“暴力破解”实际上就是穷举法，所以必须保证密码的位数及复杂程度足够高，才能对抗这种破解方法。

无论是经典奥数题还是我们其它数学题，使用编程来解决，都需要一个从数学思维转换为编程思维的过程。

Lisa老师和Marvin老师抛砖引玉，不同的算法，解决相同的问题。同学们，也可以试着用C++编写一个程序解决一些经典奥数问题，训练一下自己的编程能力。