大家一定很熟悉鸡兔同笼的问题,不少同学还掌握了解这类问题的多种方法。那么,计算机是怎样解这种题目的?说来也许你不相信,计算机做这类题,常常用的是最笨的方法。为了便于说明问题,我们先举一个简单的例子。
例1、鸡兔同笼,总头数为6,总脚数为16,求鸡兔各有多少只?
计算机用“穷举”的方法来解这个题,具体思路是:先假定有1只鸡,则有5只兔,算算脚数(22只)不是16只;再假定有2只鸡,则有4只兔,算算脚数(20只),还不对。再假定有2只鸡,则有3只兔,算算脚数(18只),仍然不对。再假定有4只鸡,则有两只兔。算算脚数:2×4+4×2=16,这次对了。好,答案找到了。
看,这有多麻烦呀。可是计算机算得快,它也不嫌烦。用这种方法它能解出许多困难的题目来。
把上面的解题思路写成程序,就是:程序1
10REM鸡兔同笼
20FOR JI=1 TO 6
30TU=6-JI
40IF 2*JI+4*TU=16 THEN PRINT“鸡=”;JI,“兔=”;TU:GOTO 70
50NEXT JI60PRINT“无解”
70END
20—50语句行构成循环,鸡的数目最少是1,最多是6,所以JI从1到6循环。
30语句行:根据JI(鸡)的当前值,求出相应的TU(兔)的个数。
40语句行:算算鸡、兔的脚数是不是16只,如果是,就显示出JI、TU的个数,然后结束。否则执行50语句行,接着循环。
60语句行:如果循环完了,没有显示出结果,程序也没有结束,那就是因为给的数据不合理,此题无解。
如果题目改成:鸡兔同笼,总头数为80,总脚数为200,求鸡兔各有多少只?
请读者修改上面的程序,让计算机找到本题的答案。
例2、有100匹马,驮100块瓦。1匹大马驮3块瓦,1匹老马驮两块瓦,两匹小马驮1块瓦。求大马、老马、小马各有多少匹?
这道题,用一般列方程的方法不易解出,因为它有三个未知数,只能列出两个独立的方程(这类方程叫不定方程,常有多组解)。
计算机解这种题目,也是用“穷举法”。请看程序。
程序2:
10REM百马百瓦问题
20REM X——大马,Y——老马,Z——小马30FOR X=1 TO 33
40FOR Y=1 TO 50
50Z=100-X-Y
60IF 3*X+2*Y+Z/2=100 THEN PRINT“大马:”X,“老马:”Y,“小马:”Z70NEXTY80NEXTX90END本程序使用了双重循环,遍举所有可能的大马、老马和小马的匹数,即大马老马小马11981297……15049
21972296……25048……331663326533364
……335017
总共搜索了:50×33=1650
1650种三种马的不同组合。对每一种组合情况,都在60语句行判断是否驮的瓦数正好是100
块。如果是就显示出这一组解,否则不显示。因为可能有多组解,所以无论是否显示了解都要继续循环。
请读者想一想,X的循环为什么从1到33,Y的循环是从1到50?