登陆注册
15875100000069

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

同类推荐
  • 鹰隼突击——空中武器

    鹰隼突击——空中武器

    本书从战斗机、攻击机、轰炸机、直升机、运输机、侦察机、预警机、反潜机、加油机九个方面详细地介绍了每种飞机的用途和它们的代表机型。书中介绍的每一种战机都具有鲜明特色,力求让喜爱现代军事的读者获得视觉和阅读的双重享受。同时,本书也加入了与之相关的一些趣闻阅读和知识链接,详细介绍军用飞机漫长的发展史,同时详细解读隐身技术、变后掠翼技术、矢力推量技术等现代军用飞机的高端技术,目的是增加阅读的趣味性,旨在让青少年走进科学殿堂,探索航空知识。
  • 小学生最想知道的100个为什么——身边的秘密

    小学生最想知道的100个为什么——身边的秘密

    有时候,最让人感觉难解的秘密就在我们面前。本书发掘了这些问题背后的原因,以及日常生活中其他120个让人迷惑的难题。这些都是发生在我们身边的未解难题——院子里的生物学、厨房中的化学和日常生活中的前沿物理学。本书从《纽约时报》之《350天为什么》专栏摘取日常生活的问题集结成书。在此书中,所有的问题均是由现实生活中的孩子们(部分是成人)提出的,他们对我们身边的世界充满了好奇。
  • 探索未知-奇妙地理景观

    探索未知-奇妙地理景观

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

    新课程百科知识——世界著名物理学家

    本书介绍了多位世界著名物理学家,如帕斯卡、惠更斯、胡克、法拉第等。
  • 探索神秘的科学未知(科普知识大博览)

    探索神秘的科学未知(科普知识大博览)

    要想成为一个有科学头脑的现代人,就要对你在这个世界上所见到的事物都问个“为什么”!科学的发展往往就始于那么一点点小小的好奇心。本丛书带你进行一次穿越时空的旅行,通过这次旅行,你将了解这些伟大的发明、发现的诞生过程,以及这些辉煌成果背后科学家刻苦钻研的惊心时刻。
热门推荐
  • 修真神农

    修真神农

    三年前,他因误入石洞,神秘失踪。三年后,他重新归来。洞中机缘,使他获得神农传承,回归田园,打造最美农庄。他种植的蔬菜水果供不应求,千金难得。他养殖的鱼虾螃蟹万人追捧,一斤难求。山清水秀,牵鸡斗狗,门前卧老牛,树下盘金凤。从此,乡村有神农。
  • 王俊凯演绎陌路离殇

    王俊凯演绎陌路离殇

    当年华已逝,我们彼此如陌生人一样,之前的我们留下了空白格,后来发现,我们的爱情到这刚刚好,但请记住,世界是圆的,无论如何我们都会再遇见,等再次遇见时,看你事业这么好,人还是那样精神,真好……
  • 少年探案集

    少年探案集

    平凡的生活之中总有些意想不到的事情。一场场案件的背后也会有一些鲜为人知的东西。像鲨鱼一样,用敏锐的嗅觉,锋利的牙齿,撕开一张张虚伪的面具……
  • 欧夙情缘:99次追妻

    欧夙情缘:99次追妻

    【NEXTIDEA暨2015星创奖征文大赏(现代言情)】他是叱咤商场的王,几乎垄断了亚欧州的所有地产行业。她是小小的夙氏集团的一个不受宠的小孤女。一个高高在上、众星捧月;一个连灰姑娘都比不上。一次交易,她成了他的‘宠物’,怎么办?答案只有一个,逃啊!可是就是这么莫名其妙,他竟然爱上了她,奈何他根本不会宠人啊……“你又跑什么?我还不够宠你吗?”男人危险的眯着眸子,极其不悦的说到。“宠?你确定你不是想杀了我?”女孩还看着桌子上的中药,眉都快拧成个疙瘩了“乖,喝完带你出去玩。”欧冥寒摸了摸小女人的头。“你丫当我是小孩啊?!”几乎是瞬间就炸毛了。“不是吗?”男人挑挑眉,笑得魅惑至极。
  • White Lies

    White Lies

    本书为公版书,为不受著作权法限制的作家、艺术家及其它人士发布的作品,供广大读者阅读交流。
  • 晚明江山

    晚明江山

    在一个皇帝窝在后宫里不再上朝的奇葩朝代里。没有人知道在大陆的另一端,欧洲人正在破浪扬帆,探索新大陆;也没有人关注在极北之地,女真建州部首领努尔哈赤正在磨刀霍霍,觊觎大明的万里江山;当然也无人关注远在一小岛,丰臣秀吉正在统一日本,企图侵占大明王朝。时间依然流逝,大明朝街市依然繁荣太平,普通百姓热衷于谈谐、听曲、游玩、博弈、收藏古玩等等。如此危机四伏的大明朝,现在且看我晚明江山如何叱咤风云,打造一个民富国强的新世纪。
  • 剑御山河

    剑御山河

    一个穿越者的逆天之路......新人作品,不喜勿喷!
  • 丧尸之乱

    丧尸之乱

    第一次写小说,请大家多多包涵,写的不好的地方请多多指导。这篇小说写的是一对情侣察在执行一次丧尸任务的事。
  • 瑾世倾翊:天才绝色丹药师

    瑾世倾翊:天才绝色丹药师

    此书为《瑾世倾翊:绝色天才丹药师》的另一个版本,不喜请点关闭。
  • 安徒生不哀伤

    安徒生不哀伤

    希望用自己的一份虔诚和谦卑的情感去让读到它们的人获得一些温暖和感触