穷举算法是程序设计中使用得最为普遍、大家必须熟练把握和正确运用的一种算法。它利用计算机运算速度快、精确度高的特点,对要解决问题的所有可能情况,一个不漏地进行检查,从中找出符合要求的答案。
用穷举算法解决问题,通常可以从两个方面进行分析:
一、问题所涉及的情况:问题所涉及的情况有哪些,情况的种数可不可以确定。把它描述出来。
二、答案需要满足的条件:分析出来的这些情况,需要满足什么条件,才成为问题的答案。把这些条件描述出来。
只要把这两个方面分析好了,问题自然会迎刃而解。
例 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