登陆注册
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?

同类推荐
  • 探索未知-认识自然的力量

    探索未知-认识自然的力量

    探索未知,追求新知,创造未来。本丛书包括:奇特的地理现象、遗传简介、生活物理现象解读、奥妙无穷的海洋、认识微生物、数学经典题、垃圾与环境、湛蓝浩瀚四大洋、生物的行为、漫谈电化学、数学古堡探险、中国的世界文化遗产、中国古代物理知识、中国三大三角洲、中国的地理风情、多姿的中国地形、认识少数民族医学、悠悠的中国河流等书籍。
  • 天文与地理科技大发现

    天文与地理科技大发现

    本套书简明扼要,通俗易懂,生动有趣,图文并茂,体系完整,有助于读者开阔视野,深化对于中华文明的了解和认识;有助于优化知识结构,激发创造激情;也有助于培养博大的学术胸怀,树立积极向上的人生观,从而更好地适应新世纪对人才全面发展的要求。
  • 探索未知丛书-动物乐园03

    探索未知丛书-动物乐园03

    探索未知,追求新知,创造未来。本丛书包括:地理世界、动物乐园、海洋与天空、化学天地、计算机王国、历史趣闻、美术沙龙、农业科学、少年楷模、物理城堡、艺术天地、音乐之声、幼儿教育、语文大观、植物之谜、走遍天下、祖国在我心中等书籍。
  • 低碳经济

    低碳经济

    《低碳经济--让地球和人类一起再继续(典藏版)》由石晓娜所著,《低碳经济--让地球和人类一起再继续(典藏版)》旨在引导新时代的青少年一起行动起来,为了我们共同的家园,用自己的实际行动把生活耗用能量降到最低,从而减少二氧化碳的排放,实现绿色低碳生活。低碳生活是一种态度,也是一种责任,更是一种爱,让我们的爱更宽广,更包容,更细致吧!
  • 科学大探险:寻找尼斯湖水怪大冒险

    科学大探险:寻找尼斯湖水怪大冒险

    来自二十三世纪的小朋友,带着他的宠物猪寻找尼斯湖水怪!他们来到了苏格兰去尼斯湖探险。他们采用守株待兔的方法还潜入了水底,陷入了淤泥、遇到了鳄鱼的追赶……这几个小朋友到底还会遇到多少危险,能不能找到尼斯湖水怪呢?
热门推荐
  • 记者生涯

    记者生涯

    长篇小说连载:一报社记者在采访一起集体食物中毒事件时与一风月女子邂逅,其中各种曲折隐晦,一一述来,这是一段现代都市的幽暗奇情。
  • 再世为妃

    再世为妃

    原本是现代的特工,转眼却成了丞相的废物女儿,但是废物还是天才却只在一念之间,看她如何征服皇宫?
  • 远武迹

    远武迹

    英雄,只是历史长河中的标点符号。要做便做那神雄,吼一声天地为之颤抖,身后立一碑亦当永震星河之下,令妖邪不再。远去的武斗已无踪可觅,可关于它的传说,有如回声一样荡漾在岁月中,依旧有迹可寻。在那混沌之中,为万物苍生而战为万物苍生而斗,开启和平纪元的神豪们,或重现笙歌中,或再武戏词里......
  • 傀儡师

    傀儡师

    自古流传的傀儡术,是一种神秘而强大的奇术,不仅能用来操纵生物,甚至还能操纵非生物。这种奇术的传承者李然,凭着这种奇术,在奇案不断发生的校园中,不断地解开迷题,让那血案背后的凶手暴露在阳光之下。
  • 当希翼被折断

    当希翼被折断

    现实与幻想就像实物与虚无,你去碰就会受伤。
  • 从一条蛇吞噬进化

    从一条蛇吞噬进化

    “叮!你杀死一头神龙,进化点+1000万。”“叮!你杀死一只凤凰,进化点+1000万。”“叮!你获得宇宙至尊果实,进化点+1000万。”“.......”“叮!恭喜宿主进化成神兽。”某一天,李云站在巅峰俯视苍生,“原来我已经无敌了。”
  • 申山传说

    申山传说

    “国者,无民不立,无王不兴。王本就是民献给国的祭品,领受民之膏血,是为以王之牺牲换取国之昌盛。”“骖逝水兮云骓,寐长夜兮纶垂,余青华兮葳蕤,终天风兮星颓。”“愿我人族,于此魂梦江海,万古河山之间,星火世传,奋飞不辍。”
  • 焚影异闻录

    焚影异闻录

    不管遇到什么困难都不要害怕,要勇敢的去面对它,克服最好的恐惧就是面对恐惧,干就完了!奥利给!
  • 重生99次后我开挂了

    重生99次后我开挂了

    在那个少年进入江家的第一天,江梨就对他抱着万分的恶意,她使尽一切恶劣的手段去欺负他,结果在他手里栽倒了98次。在99次的时候,她把一切都看淡了,却发现这一世的偏差有点多。
  • 向新四军学习

    向新四军学习

    在写作本书的过程中,既有诚惶诚恐之感,又有难尽表达之虑,不过我们的心灵却受到了一次次极大震憾,精神受到了一次次重要洗礼,深深地感受到:蕴含内容如此丰富、教育意义如此深刻的伟大而高尚的人民解放军的精神与品质,是我们取之不渴的精神食粮,是引导我们前行的方向标。