第五讲 穷举算法

1、第五讲 穷举算法学习重点：1、了解穷举法的基本概念及用穷举法设计算法的基本过程。2、能够根据具体问题的要求，使用穷举法设计算法，编写程序求解问题。 3、能对穷举法编写的程序进行优化学习过程：穷举算法是学生在学完了QB基本语句后最早接触到的算法。一些简单的穷举算法题目如求水仙花数、找出缺失的数字等和小学生的数学学习紧密结合，程序也比较容易实现，因此学生的学习兴趣还是很高的。近几年的省小学生程序设计竞赛中也常出现穷举算法的题目，如：2001年题四算24；2002年题三求素数个数与素数个数最多的排列；2005年回文数个数等题目，有些题虽然说用穷举算法实现比较勉强（如2002年题三的后半题求出素数个数

2、最多的排列），但在考试时，如果一时想不出更好的办法，用穷举算法也不失为一种明智的选择。穷举法，常常称之为枚举法，是指从可能的集合中一一穷举各个元素，用题目给定的约束条件判定哪些是无用的，哪些是有用的。能使命题成立者，即为问题的解。穷举是最简单，最基础，也是通常被认为非常没效率的算法，但是。穷举拥有很多优点，它在算法中占有一席之地。首先，穷举具有准确性，只要时间足够，正确的穷举得出的结论是绝对正确的；其次，穷举拥有全面性，因为它是对所有方案的全面搜索，所以，它能够得出所有的解。采用穷举算法解题的基本思路：（1）确定穷举对象、穷举范围和判定条件；（2）一一列举可能的解，验证是否是问题的解一、穷举算

3、法的实现在前面基础语句（for语句）的学习中，其实我们就用到了穷举。比如培训教材p77【例5-7】打印九九乘法表中，被乘数A和乘数B都从1-9一一列举。这样，九九乘法表中就不会遗失任何一句乘法口诀；在p79【例5-9】的数学灯谜题中，我们也是用了一一列举的方法，找出了A、B、C、D的取值范围。下面我们再看两道例题：1、搬运砖头【问题描述】36 块砖， 36 人搬。男搬 4 ，女搬 3 ，两个小儿抬一砖。要求一次全搬完。问需男、女、小儿各若干？【问题分析】题目要我们找出符合条件的男生、女生和小孩的人数。答案显然是一组数据。首先分析一下问题所涉及的情况。对于男生来说，至少要有一人；每个男生可以搬4

4、 块砖，那么 36 块砖最多 9 个男生足够，共有 9 种不同取值。同样，女生有 12 种不同取值。两个小孩抬一块砖，至少要有两个小孩，最多 36 个，并且小孩的人数必须是个偶数，所以小孩的人数可以取 18 种不同的值。最坏情况下，男生、女生和小孩的人数可以是 9 × 12 × 18 1944 种不同组合。假设男生人数为 x ，女生人数为 y ，小孩人数为 z 。可以构建一个三重循环求出最终结果。【程序清单】 rem 5_1.basfor x=1 to 9 for y=1 to 12 for z=2 to 36 step 2 if x*4+y*3+z/2=36 then p

5、rint x,y,znext z next y next xend2、方格内填字符【问题描述】在5个连成一串的方格内填入“a”和“b”，但“b”不能填在相邻两格内。打印出所有填法和总方案数。【问题分析】(1)用五重循环列举；（2）由于QB中FOR语句不能直接列举字符，所以用“A”和“B”的ASCII码作为循环的初值和终值；（3）需排除含“BB”、“AAAAA”的各种情况。【程序清单】REM 5_2.bass = 0bb = 132: aaaaa = 325 连续填“BB”的ASCII和为132，“AAAAA”为325；FOR a = 65 TO 66 FOR b = 65 TO 66 FOR

6、c = 65 TO 66 FOR d = 65 TO 66 FOR e = 65 TO 66 x = a + b + c + d + e: ab = a + b: bc = b + c: cd = c + d: de = d + e IF x <> 325 AND ab <> bb AND bc <> bb AND cd <> bb AND de <> bb THEN PRINT CHR$(a); CHR$(b); CHR$(c); CHR$(d); CHR$(e): s = s + 1NEXT e, d, c, b, aPRINT

7、s3、简单的24点【问题描述】从键盘输入4个整数（每个数均大于等于1），算一算能否凑成24点。（说明：数字的顺序不能改变，并按从左到右的次序运算，不考虑运算符的优先级别）例如：输入2，2，6，1则输出为：2+2*6*12+2*6/12*2*6*12*2*6/1输入：4，8，10，2则输出：4+8+10+2 4*8-10+2【问题分析】4个数中需填入3处运算符，每一处运算符都应该有“+”、“-”、“*”、“/”四种可能的情况，因此，可以用三重循环一一列举；每一处运算符确定后，与它相邻的两个数就有一个结果，这个结果根据运算符来定，可能是两数的和或差或积或商，我们用SELECT CASE语句来处理；

8、最后打印结果时，为了能打印出运算符，还是需要SELECT CASE语句。【程序清单】Rem 5_3.basINPUT a, b, c, d FOR i = 1 TO 4列举第一处的运算符 SELECT CASE i CASE 1: x = a + b CASE 2: x = a - b CASE 3: x = a * b CASE 4: x = a / b END SELECT FOR j = 1 TO 4列举第二处的运算符 SELECT CASE j CASE 1: y = x + c CASE 2: y = x - c CASE 3: y = x * c CASE 4: y = x / c

9、 END SELECT FOR k = 1 TO 4列举第三处的运算符 SELECT CASE k CASE 1: z = y + d CASE 2: z = y - d CASE 3: z = y * d CASE 4: z = y / d END SELECT IF z = 24 THEN PRINT a; SELECT CASE i CASE 1: PRINT "+" CASE 2: PRINT "-" CASE 3: PRINT "*" CASE 4: PRINT "/" END SELECT PRINT

10、b; SELECT CASE j CASE 1: PRINT "+" CASE 2: PRINT "-" CASE 3: PRINT "*" CASE 4: PRINT "/" END SELECT PRINT c; SELECT CASE k CASE 1: PRINT "+" CASE 2: PRINT "-" CASE 3: PRINT "*" CASE 4: PRINT "/" END SELECT PRINT d END IF

11、 NEXT k NEXT j NEXT iEND【想一想】能不能简化打印语句，去掉里面的三个SELECT CASE语句？ 【教法指导】在本单元的学习中，对我们的教学对象小学生进行该算法教学的时候，我们首先应该让他们了解什么是穷举法？教学的设计可以从游戏入手：（1） 请一个小朋友（小X）任意想一个4位数，写在纸上；（2） 请全体同学猜，这个数是几？（3） 每次说出一个数，裁判（老师）回答“对或错”在所有同学猜过一遍后（可能会有同学猜出这个数，可以多次重复玩这个游戏），老师可以请同学们思考，怎样才能百发百中地猜中这个数呢？（老师可以将他们的回答引导到从1000-9999，一个数不漏地猜这样的结论上

12、来）。游戏结束，老师布置作业，请同学们编一个程序，使用随机函数，模拟刚才的游戏过程。程序清单： Randomize timer X=int(rnd*9000)+1000 I=1000Do while I<>xI=I+1loop print “zhe ge shu shi :”;i End老师可以根据这个程序说明什么叫“穷举算法”。二、穷举算法的优化4、九头鸟问题（培训教材P205例1061）【问题分析】穷举对象：九头鸟、鸡、兔；穷举范围：九头鸟：鸡：兔：判定条件：头和脚都等于；（程序见p205 REM L10-6A）这段程序是没有优化的程序，在教学中，老师要分析最糟糕的情况下（找不

13、到合适的解）需循环的次数，然后让同学们上机试一下，体会一下运行时间。然后按p206 REM L10-6B 减少循环次数及REM L10-6C减少穷举对象来优化程序。从程序的优化过程中，学生们能体会到使用穷举算法时，对程序优化的重要性。书上的三段程序建议让学生都能上机试验，加深体会。P207的程序可以布置数学基础好的同学自己学习。5、巧填数字【问题描述】将这六个数字分别填到下面的圆圈中，使三角形的每边上的三个数的和相等，一共有多少种方案？编程打印这些方案。（不需要按题目的格式打印）【问题分析】穷举对象：A,B,C,D,E,F穷举范围：每一个对象都从16判定条件：（1）A、B、C、D、E、F互不相

14、等 （2）A+B+C=C+D+E=A+F+E对于小学生来说，如何判定6个变量的取值分别是16的数，并且互不相等可能是这题的难点。在学习了一唯数组后，很容易想到的是：把这6个简单变量分别赋值给X(1)X(6)，然后用一个二重循环来判断有没有重复的值：Flag=0 (标记)For i=1 to 5 For j=i+1 to 6If a(i)=a(j) then flag=1Next j,i这段小程序的适用范围很广，它可以用来判断出任意六个数是否互不相等。但在本题，由于已知的数是16的连续整数，因此可用更少的语句来实现。只要满足：A+B+C+D+E+F=21且A*B*C*D*E*F=720 就能判别

15、出AF一定是互不相等的数。【程序清单】Rem 5_5.basS = 0FOR A = 1 TO 6 FOR B = 1 TO 6 FOR C = 1 TO 6 FOR D = 1 TO 6 FOR E = 1 TO 6 FOR F = 1 TO 6 X = A + B + C + D + E + F Y = A * B * C * D * E * F IF (X = 21) AND (Y = 720) AND (A + B + C = C + D + E) AND (A + B + C = A + F + E) THEN PRINT A; B; C; D; E; F : S = S + 1NE

16、XT F, E, D, C, B, APRINT "S=" SEND程序的优化：在小学数学的范围内，学生们可以做的改进是：减少一个循环语句，从而使效率提高6倍。程序留给老师们自己编写。三、穷举对象的选择在上题中，如果数学知识扩充的话，只要3重循环就能解决问题。这就涉及到穷举对象的选择问题。上题中，穷举对象分别取A、C、E就可以了；判定条件只要6个数互不相等。【问题分析】根据已知条件：A+B+C+D+E+F=21，则三条边的和相加为：（A+B+C）+（C+D+E）+（E+F+A）=（A+C+E）+21。每一条边的和为：1/3*（A+C+E）+7，这样就有下面三组等式：A+B+

17、C=1/3*（A+C+E）+7C+D+E=1/3*（A+C+E）+7E+F+A=1/3*（A+C+E）+7上述三个式子化简后，就得到了：b = e / 3 - a / 3 * 2 - c / 3 * 2 + 7 d = a / 3 - c / 3 * 2 - e / 3 * 2 + 7 f = c / 3 - a / 3 * 2 - e / 3 * 2 + 7【程序清单】REM 5_5_2.basFOR a = 1 TO 6 FOR c = 1 TO 6 FOR e = 1 TO 6 b = e / 3 - a / 3 * 2 - c / 3 * 2 + 7 d = a / 3 - c / 3

18、 * 2 - e / 3 * 2 + 7 f = c / 3 - a / 3 * 2 - e / 3 * 2 + 7 p = a * b * c * d * e * f: s = a + b + c + d + e + f IF b = INT(b) AND d = INT(d) AND f = INT(f) AND s = 21 AND p = 720 THEN PRINT a; b; c; d; e; f: q = q + 1 NEXT e NEXT cNEXT aPRINT q从例2中我们可以看到，在穷举算法中，穷举对象的选择也是非常重要的，它直接影响着算法的时间复杂度，选择适当的穷举对

19、象可以获得更高的效率。我们再举一个例子：6、成比例的三位数【问题描述】将1,2.9共9个数分成三组,分别组成三个三位数,且使这三个三位数构成1:2:3的比例,试求出所有满足条件的三个三位数.例如:三个三位数192,384,576满足以上条件.【问题分析】这是1998年全国分区联赛普及组试题。此题数据规模不大，可以进行穷举，如果我们不假思索地以每一个数位为穷举对象，一位一位地去穷举：for a =1 to 9 for b=1 to 9 for i=1 to 9 这样下去，穷举次数就有99次。如果我们分别设三个数为x,2x,3x，以x为穷举对象，穷举的范围就减少为9*9*9，在细节上再进一步优化，

20、穷举范围就更少了。程序如下：【程序清单】FOR x = 123 TO 321 穷举所有可能的解 y = 2 * x z = 3 * x GOSUB 1000 分解数字 GOSUB 2000 判断数字是否为1-9的互不重复的数 IF flag = 0 THEN PRINT x, y, zNEXT xEND1000 : a(1) = x 100: a(2) = (x - a(1) * 100) 10: a(3) = x MOD 10 a(4) = y 100: a(5) = (y - a(4) * 100) 10: a(6) = y MOD 10 a(7) = z 100: a(8) = (z -

21、 a(7) * 100) 10: a(9) = z MOD 10RETURN2000 : flag = 0 FOR i = 1 TO 9: b(i) = 0: NEXT i FOR i = 1 TO 9 b(a(i) = b(a(i) + 1 NEXT i FOR i = 1 TO 9 IF b(i) <> 1 THEN flag = 1 NEXT iRETURN在本程序中，判断不重复的数字用的是子程序2000，当然，用前面讲过的方法都是可以的，在此只是多提供一种方法给学生。优化以后的程序循环不到200次，运行时间大大缩短了。四、判定条件的确定在穷举法解题中，判定条件的确定也是很重

22、要的，如果约束条件不对或者不全面，就穷举不出正确的结果。有些时候，我们编写的程序，从理论上来说，完全是正确的，但就是得不到正确的结果，或者会漏掉一些结果，这和判定条件是有一定关系的。我们再看看下面的例子。7、 一元三次方程求解（作为阅读材料）【问题描述】 有形如：ax3+bx2+cx+d=0 这样的一个一元三次方程。给出该方程中各项的系数(a，b，c，d 均为实数)，并约定该方程存在三个不同实根(根的范围在-100至100之间)，且根与根之差的绝对值>=1。要求由小到大依次在同一行输出这三个实根(根与根之间留有空格)，并精确到小数点后2位。提示：记方程f(x)=0，若存在2个数x1和x2

23、，且x1<x2，f(x1)* f (x2)<0，则在(x1，x2)之间一定有一个根。样例输入：1 -5 -4 20输出：-2.00 2.00 5.00【问题分析】由题目的提示很符合二分法求解的原理，所以此题可以用二分法。用二分法解题相对于穷举法来说很要复杂很多。此题是否能用穷举法求解呢？再分析一下题目，根的范围在-100到100之间，结果只要保留两位小数，我们不妨将根的值域扩大100倍（-10000<=x<=10000），再以根为穷举对象，穷举范围是-10000到10000，用原方程式进行一一验证，找出方程的解。有的同学在比赛中是这样做Input a,b,c,dfor

24、i=-10000 to 10000 x=i/100 if a*x*x*x+b*x*x+c*x+d=0 then ?xnext iend用这种方法，很快就可以把程序编出来，再将样例数据代入测试也是对的，等成绩下来才发现这题没有全对，只得了一半的分。这种解法为什么是错的呢？错在哪里？前面的分析好像也没错啊，难道这题不能用穷举法做吗？ 看到这里大家可能有点迷惑了。在上面的解法中，穷举范围和穷举对象都没有错，而是在验证穷举结果时，判定条件用错了。因为要保留二位小数，所以求出来的解不一定是方程的精确根，再代入ax3+bx2+cx+d中，所得的结果也就不一定等于0，因此用原方程ax3+bx2+cx+d=0

25、作为判断条件是不准确的。我们换一个角度来思考问题，设f(x)=ax3+bx2+cx+d，若x为方程的根，则根据提示可知，必有f(x-0.005)*f(x+0.005)<0，如果我们以此为穷举判定条件，问题就逆刃而解。为了阅读程序的方便，我们先计算当x1=x-0.005,x2=x+0.005时函数的值。只要(f(x-0.005)*f(x+0.005)<0),我们就认为在(x-0.005)到（x+0.005）中存在一个值，这个值就是我们需要的根。（我们用数字来举例说明问题：假设在50-0.005到50+0.005之间满足f(x-0.005)*f(x+0.005)<0，那么说明在4

26、9.99550.005之间必定有一个根，这个根可能是49.995，49.996，49.99750.004，50.005，根据题意，这些根中的任意一个经四舍五入后都是50 ，因此我们把50作为要求的一个根；另外，如果f(x-0.005)=0，那么说明x-0.005是方程的根，这时根据四舍5入，方程的根也为x。所以我们用(f(x-0.005)*f(x+0.005)<0)和 (f(x-0.005)=0)作为判定条件。程序如下：【程序清单】INPUT a, b, c, dFOR i = -10000 TO 10000 x = i / 100 x1 = x - .005 x2 = x + .005

27、f1 = (a * x1 + b) * x1 + c) * x1 + df2 = (a * x2 + b) * x2 + c) * x2 + dIF f1 = 0 OR f1 * f2 < 0 THEN PRINT xNEXT iEND用穷举法解题的最大的缺点是运算量比较大，解题效率不高，如果穷举范围太大（一般以不超过两百万次为限），在时间上就难以承受。但穷举算法的思路简单，程序编写和调试方便，比赛时也容易想到，在竞赛中，时间是有限的，我们竞赛的最终目标就是求出问题解，因此，如果题目的规模不是很大，在规定的时间与空间限制内能够求出解，那么我们最好是采用穷举法，而不需太在意是否还有更快的算

28、法，这样可以使你有更多的时间去解答其他难题。8、分鱼问题【问题描述】A 、 B 、 C 、 D 、 E 五人夜间合伙捕鱼，凌晨时都疲倦不堪，各自在河边的树丛中找地方睡着了。日上三竿， A 第一个醒来，他将鱼分作五份，把多余的一条扔回河中，拿自己的一份回家去了； B 第二个醒来，也将鱼分作五份，扔掉多余的一条，拿走自己的一份；接着 C 、 D 、 E 依次醒来，也都按同样的办法分鱼，问五人至少合伙捕了多少条鱼？试编程序算出。 【问题分析】还记得我们书上p72例5-3 小猴吃桃那个题目吗？和这题很类似是吧？书上的题我们用的算法是迭代法，需要推出迭代公式。但这题，由于没有告诉我们最后一个人取走了几条

29、鱼或最后剩下几条鱼，因此无法推出迭代公式。我们用穷举算法来做这道分鱼的题目。穷举对象：鱼穷举范围：初始值为6（至少6条鱼），终值需求出判定条件：（1）分了5次 （2）剩下的鱼丢掉1条后是否能正好分成5份（题目隐含）我们用自顶向下，逐步求精的办法编写程序：先确定大的结构：鱼初值=6Repeat 分鱼，判断条件（剩下的鱼丢掉1条后是否能正好分成5份）(1) Until 分满5次再将(1) 细化:If (鱼-1) mod 5=0 then 算出剩下的鱼；次数+1 else 现在的鱼数=原来的鱼数+5；次数=0这样，我们可以编出程序：【程序清单】yu = 6s = 0DO IF (yu - 1) MO

30、D 5 = 0 THEN s = s + 1 yu = (yu - 1) / 5 * 4 ELSE yu = yu + 5 s = 0 END IFLOOP UNTIL s = 5PRINT yuEnd经过上机调试，结果不对。问题出在哪里呢？在重新经过步进运行（按F8）后，我们发现，问题出在yu这个变量上。拿初始状态yu = 6来跟踪，在经过了第一次分鱼后，剩下的yu=4,继续循环，由于不满足(yu - 1) MOD 5 = 0 这个判定条件而执行else语句中的yu = yu + 5，使yu=9，这和我们的初衷-不能分鱼时，在原来yu的基础上+5（即yu=11）的设计思想是有出入的。为改变这

31、个现象，我们引入变量yu1，参与循环中的运算，而将变量yu作为一旦分鱼不满足条件，yu = yu + 5，重新进入新的分鱼行动。经修改后的程序：yu = 6yu1 = yus = 0DOIF (yu1 - 1) MOD 5 = 0 THEN s = s + 1 yu1 = (yu1 - 1) / 5 * 4 ELSE yu = yu + 5 yu1 = yu s = 0 END IFLOOP UNTIL s = 5PRINT yuEnd从上面的例子中我们也能看出，穷举算法一般都是用for语句来实现的，但有时在无法确定终值的情况下，就用条件循环解决问题。9、 背包问题【问题描述】小明有一个最多只

32、能装10斤重的网袋。现有白菜5斤、猪肉2斤、鱼3斤、酱油连瓶重1.7斤、白糖1斤、土豆5.1斤。设计一个程序使小明的网袋里装的物品总重量最大（每件物品要么装进袋子，要么不装），打印出这种方案。【问题分析】穷举对象： 白菜（A）、猪肉（B）、鱼（C）、酱油（D）、白糖（E）、土豆（F）穷举范围：0（不装）-1（装入） 判定条件：（1）A*5+B*2+C*3+D*1.7+E*1+F*5.1是否<=10 （2）若（1）成立，这种装法是否为最大【程序清单】m$(1) = "baicai 5 jin": m$(2) = "zhurou 2 jin": m$(

33、3) = "yu 3.5 jin"m$(4) = "jiangyou 1.7 jin": m$(5) = "baitang 1 jin": m$(6) = "tudou 5.1 jin"max = 0FOR a = 0 TO 1 FOR b = 0 TO 1 FOR c = 0 TO 1 FOR d = 0 TO 1 FOR e = 0 TO 1 FOR f = 0 TO 1 x = a * 5 + b * 2 + c * 3.5 + d * 1.7 + e * 1 + f * 5.1 IF x <= 10

34、AND x > max THEN max = x x(1) = a x(2) = b x(3) = c x(4) = d x(5) = e x(6) = f END IFNEXT f, e, d, c, b, aPRINT "zhong zhong liang zui da wei :" max; "jin"FOR i = 1 TO 6 IF x(i) <> 0 THEN PRINT m$(i)NEXT iEND程序优化：分析过程：本题考虑到最轻的5种物品的总重量为：5+2+3.5+1.7+1=13.2>10，因此，网袋中最多只能

35、装下4件物品。这样，就可以考虑从所有物品的总重量中减去任意两种物品的重量，从而求得题目要求的结果。循环从6重变为2重，大大提高了效率。s = 0FOR i = 1 TO 6: READ a(i): s = s + a(i): NEXT I FOR i = 1 TO 6: READ m$(i): NEXT I 为打印作准备max = 0FOR i = 1 TO 5 FOR j = i + 1 TO 6 s1 = s 这个语句不能少 s1 = s1 - a(i) - a(j) IF s1 <= 10 AND s1 > max THEN b = i: c = j: max = s1 满足

36、条件要将数据纪录下来 NEXT jNEXT iPRINT "zongzhongliang wei:" max; " jin"FOR i = 1 TO 6 IF i <> b AND i <> c THEN PRINT m$(i) 不是去掉的两个物品就打印NEXT iDATA 5,2,3.5,1.7,1,5.1DATA"baicai 5 jin","zhurou 2 jin","yu 3.5 jin","jiangyou 1.7 jin"DATA&quo

37、t;baitang 1 jin","tudou 5.1 jin"10、 n种物品的背包问题（阅读材料）【问题描述】有不同价值、不同重量的物品n件，求从这n件物品中选取一部分物品的选择方案，使选中物品的总重量不超过指定的限制重量，但选中物品的价值之和最大。 【问题分析】这种背包问题事先不知道物品的总件数，因此，用上面的解法是根本行不通的。设n个物品的重量和价值分别存储于数组w（）和v（）中，限制重量为tw。考虑一个n元组（x0，x1，xn-1），其中xi=0 表示第i个物品没有选取，而xi=1则表示第i个物品被选取。显然这个n元组等价于一个选择方案。用穷举法解决背包问题，需要穷举所有的选取方案，而根据上述方法，我们只要穷举所有的n元组，就可以得到问题的解。显然，每个分量取值为0或1的n元组的个数共为2n个。而每个n元组其实对应了一个长度为n的二进制数，且这些二进制数的取值范围为02n-1。 根据上面的分析，如果把02n-1分别转化为相应的二进制数，则可以得到我们所需要的2n个n元组。我们以此作为穷举的范围。【程序清单】DIM a(100), b(100), x(100), w(100), v(100)