穷举算法解题的一般思路

【 tulaoshi.com - 编程语言 】

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