穷举算法解题的一般思路

文章类别：C语言程序设计 | 发表日期:2008-9-24 14:46:25

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

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

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

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

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

例 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

上一篇：{应用}贪婪算法解题的一般思路 人气:6336
下一篇：{应用}递归算法解题的一般思路 人气:6358

C语言程序设计视频教程