分享
 
 
 

穷举算法解题的一般思路

王朝other·作者佚名  2008-06-01
窄屏简体版  字體: |||超大  

穷举算法是程序设计中使用得最为普遍、大家必须熟练把握和正确运用的一种算法。它利用计算机运算速度快、精确度高的特点,对要解决问题的所有可能情况,一个不漏地进行检查,从中找出符合要求的答案。

用穷举算法解决问题,通常可以从两个方面进行分析:

一、问题所涉及的情况:问题所涉及的情况有哪些,情况的种数可不可以确定。把它描述出来。

二、答案需要满足的条件:分析出来的这些情况,需要满足什么条件,才成为问题的答案。把这些条件描述出来。

只要把这两个方面分析好了,问题自然会迎刃而解。

例 1 : 36 块砖, 36 人搬。男搬 4 ,女搬 3 ,两个小儿抬一砖。要求一次全搬完。问需男、女、小儿各若干?

分析 :题目要我们找出符合条件的男生、女生和小孩的人数。答案显然是一组数据。首先分析一下问题所涉及的情况。对于男生来说,至少要有一人;每个男生可以搬 4 块砖,那么 36 块砖最多 9 个男生足够,共有 9 种不同取值。同样,女生有 12 种不同取值。两个小孩抬一块砖,至少要有两个小孩,最多 36 个,并且小孩的人数必须是个偶数,所以小孩的人数可以取 18 种不同的值。最坏情况下,男生、女生和小孩的人数可以是 9 × 12 × 18 = 1944 种不同组合。

知道了问题所涉及的情况有 1944 种,是个确定的数。接下来就要把它描述出来。描述的时候用什么计算机程序设计语言都可以,我这里就以 QBASIC 语言为例:假设男生人数为 x ,女生人数为 y ,小孩人数为 z 。可以构建这样一个三重循环

for x=1 to 9

for y=1 to 12

for z=2 to 36 step 2

循环体

next z

next y

next x

理论上这个循环的循环体将执行 1944 次,我们可以用它来对问题所涉及的 1944 种不同情况逐个进行检查。

分析完问题所涉及的情况后,第二步就要看看答案需要满足什么条件。仔细阅读一下题目,我们就会发现,答案 x 、 y 、 z 的值必须要同时满足两个条件:①总的工作量是 36 块砖,即: 4x+3y+z/2=36 ;②需要的总人数是 36 人,即: x+y+z=36 。把它描述出来就是: 4x+3y+z/2=36 and x+y+z=36 。满足这个条件的 x 、 y 、 z 的值就是问题的答案。我们可以在循环体里面对这个条件进行判定,看它是否满足,若满足,就把答案输出来。源程序如下:

for x=1 to 9

for y=1 to 12

for z=2 to 36 step 2

if 4*x+3*y+z/2=36 and x+y+z=36 then print x,y,z

next z

next y

next x

end

例 2 : A 、 B 、 C 、 D 、 E 五人夜间合伙捕鱼,凌晨时都倦怠不堪,各安闲河边的树丛中找地方睡着了。日上三竿, A 第一个醒来,他将鱼分作五份,把多余的一条扔回河中,拿自己的一份回家去了。 B 第二个醒来,也将鱼分作五份,扔掉多余的一条,拿走自己的一份,接着 C 、 D 、 E 依次醒来,也都按同样的办法分鱼,问五人至少合伙捕了多少条鱼?试编程序算出。

分析: 假设五人合伙捕了 x 条鱼,则“ A 第一个醒来,他将鱼分作五份,把多余的一条扔回河中,拿自己的一份回家”以后,河边应该还剩 4(x-1)/5 条鱼。在这里,题目为我们提供了一个隐含条件: (x-1)/5 必须是个正整数,否则,就不符合实际情况 , 即: (x-1) mod 5 = 0 必须成立。同样, B 、 C 、 D 、 E 在分鱼的时候也都必须要满足它。我们不妨取 x 的最小值为 6 ,让 x 逐渐增加,直到找到一个符合问题要求的答案;根据 (x-1) mod 5 = 0 这个条件, x 的每一次取值,都增加 5 个单位。可以构建一个不定次数的循环

do until < 找到答案 >

判定 x 是否为答案

loop

通过这个循环,我们就可以对每一个 x 的可能情况进行检查。源程序如下:

rem 初始化

cls

x=6

zd=0

i=0

do until zd=1

rem 判定 (x-1) mod 5 = 0 这个条件是否在五次分鱼中都满足,若都满足,则置找到答案标志 (zd) 为 1 ;否则,取下一个 x 的值,并置统计变量 i 为 0

if i=5 then

zd=1

else

x = x+5

i=0

endif

rem 初始化标志 wtg (用来标识条件是否被测试通过)

wtg=0

k=x

rem 在每一次分鱼中对条件进行判定,并置相应的标志

do until wtg=1 or i=5

if (k-1) mod 5=0 then

k=4*(k-1)/5

i=i+1

else

wtg=1

endif

loop

loop

rem 输出答案

print x

end

 
 
 
免责声明:本文为网络用户发布,其观点仅代表作者个人观点,与本站无关,本站仅提供信息存储服务。文中陈述内容未经本站证实,其真实性、完整性、及时性本站不作任何保证或承诺,请读者仅作参考,并请自行核实相关内容。
2023年上半年GDP全球前十五强
 百态   2023-10-24
美众议院议长启动对拜登的弹劾调查
 百态   2023-09-13
上海、济南、武汉等多地出现不明坠落物
 探索   2023-09-06
印度或要将国名改为“巴拉特”
 百态   2023-09-06
男子为女友送行,买票不登机被捕
 百态   2023-08-20
手机地震预警功能怎么开?
 干货   2023-08-06
女子4年卖2套房花700多万做美容:不但没变美脸,面部还出现变形
 百态   2023-08-04
住户一楼被水淹 还冲来8头猪
 百态   2023-07-31
女子体内爬出大量瓜子状活虫
 百态   2023-07-25
地球连续35年收到神秘规律性信号,网友:不要回答!
 探索   2023-07-21
全球镓价格本周大涨27%
 探索   2023-07-09
钱都流向了那些不缺钱的人,苦都留给了能吃苦的人
 探索   2023-07-02
倩女手游刀客魅者强控制(强混乱强眩晕强睡眠)和对应控制抗性的关系
 百态   2020-08-20
美国5月9日最新疫情:美国确诊人数突破131万
 百态   2020-05-09
荷兰政府宣布将集体辞职
 干货   2020-04-30
倩女幽魂手游师徒任务情义春秋猜成语答案逍遥观:鹏程万里
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案神机营:射石饮羽
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案昆仑山:拔刀相助
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案天工阁:鬼斧神工
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案丝路古道:单枪匹马
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案镇郊荒野:与虎谋皮
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案镇郊荒野:李代桃僵
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案镇郊荒野:指鹿为马
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案金陵:小鸟依人
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案金陵:千金买邻
 干货   2019-11-12
 
推荐阅读
 
 
 
>>返回首頁<<
 
靜靜地坐在廢墟上,四周的荒凉一望無際,忽然覺得,淒涼也很美
© 2005- 王朝網路 版權所有