书城科普读物探索未知丛书-计算机王国
45421700000069

第69章 什么是穷举法

大家一定很熟悉鸡兔同笼的问题,不少同学还掌握了解这类问题的多种方法。那么,计算机是怎样解这种题目的?说来也许你不相信,计算机做这类题,常常用的是最笨的方法。为了便于说明问题,我们先举一个简单的例子。

例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?