穷举算法
第五讲穷举算法
学习重点：
1、了解穷举法的基本概念及用穷举法设计算法的基本过程。
2、能够根据具体问题的要求，使用穷举法设计算法，编写程序求解问题。
3、能对穷举法编写的程序进行优化
学习过程：
穷举算法是学生在学完了QB基本语句后最早接触到的算法。一些简单的穷举算法题目如求水仙花数、找出缺失的数字等和小学生的数学学习紧密结合，程序也比较容易实现，因此学生的学习兴趣还是很高的。近几年的省小学生程序设计竞赛中也常出现穷举算法的题目，如：2001年题四算24；2002年题三求素数个数与素数个数最多的排列；2005年回文数个数等题目，有些题虽然说用穷举算法实现比较勉强（如2002年题三的后半题求出素数个数最多的排列），但在考试时，如果一时想不出更好的办法，用穷举算法也不失为一种明智的选择。
穷举法，常常称之为枚举法，是指从可能的集合中一一穷举各个元素，用题目给定的约束条件判定哪些是无用的，哪些是有用的。能使命题成立者，即为问题的解。
穷举是最简单，最基础，也是通常被认为非常没效率的算法，但是。穷举拥有很多优点，它在算法中占有一席之地。首先，穷举具有准确性，只要时间足够，正确的穷举得出的结论是绝对正确的；其次，穷举拥有全面性，因为它是对所有方案的全面搜索，所以，它能够得出所有的解。
采用穷举算法解题的基本思路：
（1）确定穷举对象、穷举范围和判定条件；
（2）一一列举可能的解，验证是否是问题的解
一、穷举算法的实现
在前面基础语句（for语句）的学习中，其实我们就用到了穷举。比如培训教材p77【例5-7】打印九九乘法表中，被乘数A和乘数B都从1-9一一列举。这样，九九乘法表中就不会遗失任何一句乘法口诀；在p79【例5-9】的数学灯谜题中，我们也是用了一一列举的方法，找出了A、B、C、D的取值范围。
下面我们再看两道例题：
1、搬运砖头
【问题描述】36 块砖，36 人搬。男搬4 ，女搬3 ，两个小儿抬一砖。要求一次全搬完。问需男、女、小儿各若干？
【问题分析】题目要我们找出符合条件的男生、女生和小孩的人数。答案显然是一组数据。首先分析一下问题所涉及的情况。对于男生来说，至少要有一人；每个男生可以搬4 块砖，那么36 块砖最多9 个男生足够，共有9 种不同取值。同样，女生有12 种不同取值。两个小孩抬一块砖，至少要有两个小孩，最多36 个，并且小孩的人数必须是个偶数，所以小孩的人数可以取18 种不同的值。最坏情况下，男生、
女生和小孩的人数可以是9 × 12 × 18 ＝1944 种不同组合。假设男生人数为x ，女生人数为y ，小孩人数为z 。可以构建一个三重循环求出最终结果。
【程序清单】rem 5_1.bas
for 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 print x,y,z
next z
next y
next x
end
2、方格内填字符
【问题描述】在5个连成一串的方格内填入“a”和“b”，但“b”不能填在相邻两格内。打印出所有填法和总方案数。
【问题分析】(1)用五重循环列举；（2）由于QB中FOR语句不能直接列举字符，所以用“A”和“B”的ASCII码作为循环的初值和终值；（3）需排除含“BB”、“AAAAA”的各种情况。
【程序清单】
REM 5_2.bas
s = 0
bb = 132: aaaaa = 325 ?连续填“BB”的ASCII和为132，“AAAAA”为325；
FOR a = 65 TO 66
FOR b = 65 TO 66
FOR 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 + 1
NEXT e, d, c, b, a
PRINT s
3、简单的24点
【问题描述】从键盘输入4个整数（每个数均大于等于1），算一算能否凑成24点。（说明：数字的顺序不能改变，并按从左到右的次序运算，不考虑运算符的优先级别）
例如：输入2，2，6，1
则输出为：
2+2*6*1
2+2*6/1
2*2*6*1
2*2*6/1
输入：4，8，10，2
则输出：4+8+10+2
4*8-10+2
【问题分析】4个数中需填入3处运算符，每一处运算符都应该有“+”、“-”、“*”、“/”四种可能的情况，因此，可以用三重循环一一列举；每一处运算符确定后，与它相邻的两个数就有一个结果，这个结果根据运算符来定，可能是两数的和或差或积或商，我们用SELECT CASE语句来处理；最后打印结果时，为了能打印出运算符，还是需要SELECT CASE语句。
【程序清单】
Rem 5_3.bas
INPUT 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
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 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
NEXT k
NEXT j
NEXT i
END
【想一想】能不能简化打印语句，去掉里面的三个SELECT CASE语句？
【教法指导】在本单元的学习中，对我们的教学对象——小学生进行该算法教学的时候，我们首先应该让他们了解什么是穷举法？
教学的设计可以从游戏入手：
（1）请一个小朋友（小X）任意想一个4位数，写在纸上；
（2）请全体同学猜，这个数是几？
（3）每次说出一个数，裁判（老师）回答“对或错”
在所有同学猜过一遍后（可能会有同学猜出这个数，可以多次重复玩这个游戏），老师可以请同学们思考，怎样才能百发百中地猜中这个数呢？（老师可以将他们的回答引导到从1000-9999，一个数不漏地猜这样的结论上来）。游戏结束，老师布置作业，请同学们编一个程序，使用随机函数，模拟刚才的游戏过程。
程序清单：
Randomize timer
X=int(rnd*9000)+1000
I=1000
Do while I<>x
I=I+1
loop
print “zhe ge shu shi :”;i
End
老师可以根据这个程序说明什么叫“穷举算法”。
二、穷举算法的优化
4、九头鸟问题（培训教材P205例10－61）
【问题分析】
穷举对象：九头鸟、鸡、兔；
穷举范围：九头鸟：１～１００
鸡：１～１００
兔：１～１００
判定条件：头和脚都等于１００；
（程序见p205 REM L10-6A）
这段程序是没有优化的程序，在教学中，老师要分析最糟糕的情况下（找不到合适的解）需循环的次数，然后让同学们上机试一下，体会一下运行时间。
然后按p206 REM L10-6B 减少循环次数及REM L10-6C减少穷举对象来优化程序。
从程序的优化过程中，学生们能体会到使用穷举算法时，对程序优化的重要性。
书上的三段程序建议让学生都能上机试验，加深体会。P207的程序可以布置数学基础好的同学自己学习。
5、巧填数字
【问题描述】
将１～６这六个数字分别填到下面的圆圈中，使三角形的每边上的三个数的和相等，一共有多少种方案？编程打印这些方案。（不需要按题目的格式打印）
【问题分析】
穷举对象：A,B,C,D,E,F
穷举范围：每一个对象都从1～6
判定条件：（1）A、B、C、D、E、F互不相等
（2）A+B+C=C+D+E=A+F+E
对于小学生来说，如何判定6个变量的取值分别是1～6的数，并且互不相等可能是这题的难点。在学习了一唯数组后，很容易想到的是：把这6个简单变量分别赋值给X(1)～X(6)，然后用一个二重循环来判断有没有重复的值：
Flag=0 (标记)
For i=1 to 5
For j=i+1 to 6
If a(i)=a(j) then flag=1
Next j,i
这段小程序的适用范围很广，它可以用来判断出任意六个数是否互不相等。但在本题，由于已知的数是1～6的连续整数，因此可用更少的语句来实现。只要满足：
A+B+C+D+E+F=21且A*B*C*D*E*F=720 就能判别出A～F一定是互不相等的数。
【程序清单】
Rem 5_5.bas
S = 0
FOR 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 + 1
NEXT F, E, D, C, B, A
PRINT "S="; S
END
程序的优化：在小学数学的范围内，学生们可以做的改进是：减少一个循环语句，从而使效率提高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+C=1/3*（A+C+E）+7
C+D+E=1/3*（A+C+E）+7
E+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.bas
FOR 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 * 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 c
NEXT a
PRINT q
从例2中我们可以看到，在穷举算法中，穷举对象的选择也是非常重要的，它直接影响着算法的时间复杂度，选择适当的穷举对象可以获得更高的效率。我们再举一个例子：
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，在细节上再进一步优化，穷举范围就更少了。程序如下：【程序清单】
FOR x = 123 TO 321 ?穷举所有可能的解
y = 2 * x
z = 3 * x
GOSUB 1000 ?分解数字
GOSUB 2000 ?判断数字是否为1-9的互不重复的数
IF flag = 0 THEN PRINT x, y, z
NEXT x
END
1000 :
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 - a(7) * 100) \ 10: a(9) = z MOD 10
RETURN
2000 :
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 i
RETURN
在本程序中，判断不重复的数字用的是子程序2000，当然，用前面讲过的方法都是可以的，在此只是多提供一种方法给学生。优化以后的程序循环不到200次，运行时间大大缩短了。
四、判定条件的确定
在穷举法解题中，判定条件的确定也是很重要的，如果约束条件不对或者不全面，就穷举不出正确的结果。有些时候，我们编写的程序，从理论上来说，完全是正确的，但就是得不到正确的结果，或者会漏掉一些结果，这和判定条件是有一定关系的。我们再看看下面的例子。
7、一元三次方程求解（作为阅读材料）
【问题描述】
有形如：ax3+bx2+cx+d=0 这样的一个一元三次方程。给出该方程中各项的系数(a，b，c，d 均为实数)，并约定该方程存在三个不同实根(根的范围在-100至100之间)，且根与根之差的绝对值>=1。
要求由小到大依次在同一行输出这三个实根(根与根之间留有空格)，并精确到小数点后2位。
提示：记方程f(x)=0，若存在2个数x1和x2，且x1 样例 输入：1 -5 -4 20 输出：-2.00 2.00 5.00 【问题分析】 由题目的提示很符合二分法求解的原理，所以此题可以用二分法。用二分法解题相对于穷举法来说很要复杂很多。此题是否能用穷举法求解呢？再分析一下题目，根的范围在-100到100之间，结果只要保留两位小数，我们不妨将根的值域扩大100倍 （-10000<=x<=10000），再以根为穷举对象，穷举范围是-10000到10000，用原方程式进行一一验证，找出方程的解。 有的同学在比赛中是这样做 Input a,b,c,d for i=-10000 to 10000 x=i/100 if a*x*x*x+b*x*x+c*x+d=0 then ?x next i end 用这种方法，很快就可以把程序编出来，再将样例数据代入测试也是对的，等成绩下来才发现这题没有全对，只得了一半的分。 这种解法为什么是错的呢？错在哪里？前面的分析好像也没错啊，难道这题不能用穷举法做吗？看到这里大家可能有点迷惑了。 在上面的解法中，穷举范围和穷举对象都没有错，而是在验证穷举结果时，判定条件用错了。因为要保留二位小数，所以求出来的解不一定是方程的精确根，再代入ax3+bx2+cx+d 中，所得的结果也就不一定等于0，因此用原方程ax3+bx2+cx+d=0作为判断条件是不准确的。 我们换一个角度来思考问题，设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，那么说明在49.995～50.005之间必定有一个根，这个根可能是49.995，49.996，49.997……50.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, d FOR i = -10000 TO 10000 x = i / 100 x1 = x - .005 x2 = x + .005 f1 = ((a * x1 + b) * x1 + c) * x1 + d f2 = ((a * x2 + b) * x2 + c) * x2 + d IF f1 = 0 OR f1 * f2 < 0 THEN PRINT x NEXT i END 用穷举法解题的最大的缺点是运算量比较大，解题效率不高，如果穷举范围太大（一般以不超过两百万次为限），在时间上就难以承受。但穷举算法的思路简单，程序编写和调试方便，比赛时也容易想到，在竞赛中，时间是有限的，我们竞赛的最终目标就是求出问题解，因此，如果题目的规模不是很大，在规定的时间与空间限制内能够求出解，那么我们最好是采用穷举法，而不需太在意是否还有更快的算法，这样可以使你有更多的时间去解答其他难题。 8、分鱼问题 【问题描述】 A 、 B 、 C 、 D 、 E 五人夜间合伙捕鱼，凌晨时都疲倦不堪，各自在河边的树丛中找地方睡着了。日上三竿，A 第一个醒来，他将鱼分作五份，把多余的一条扔回河中，拿自己的一份回家去了；B 第二个醒来，也将鱼分作五份，扔掉多余的一条，拿走自己的一份；接着C 、D 、E 依次醒来，也都按同样的办法分鱼，问五人至少合伙捕了多少条鱼？试编程序算出。 【问题分析】 还记得我们书上p72[例5-3] 小猴吃桃那个题目吗？和这题很类似是吧？书上的题我们用的算法是迭代法，需要推出迭代公式。但这题，由于没有告诉我们最后一个人取走了几条鱼或最后剩下几条鱼，因此无法推出迭代公式。我们用穷举算法来做这道分鱼的题目。 穷举对象：鱼 穷举范围：初始值为6（至少6条鱼），终值需求出 判定条件：（1）分了5次 （2）剩下的鱼丢掉1条后是否能正好分成5份（题目隐含） 我们用自顶向下，逐步求精的办法编写程序： 先确定大的结构： 鱼初值=6 Repeat 分鱼，判断条件（剩下的鱼丢掉1条后是否能正好分成5份） (1) Until 分满5次 再将(1) 细化: If (鱼-1) mod 5=0 then 算出剩下的鱼；次数+1 else 现在的鱼数=原来的鱼数+5；次数=0 这样，我们可以编出程序： 【程序清单】 yu = 6 s = 0 DO IF (yu - 1) MOD 5 = 0 THEN s = s + 1 yu = (yu - 1) / 5 * 4 ELSE yu = yu + 5 s = 0 END IF LOOP UNTIL s = 5 PRINT yu End 经过上机调试，结果不对。问题出在哪里呢？ 在重新经过步进运行（按F8）后，我们发现，问题出在yu这个变量上。拿初始状态yu = 6来跟踪，在经过了第一次分鱼后，剩下的yu=4,继续循环，由于不满足(yu - 1) MOD 5 = 0 这个判定条件而执行else语句中的yu = yu + 5，使yu=9，这和我们的初衷—--不能分鱼时，在原来yu的基础上+5（即yu=11）的设计思想是有出入的。为改变这个现象，我们引入变量yu1，参与循环中的运算，而将变量yu作为一旦分鱼不满足条件，yu = yu + 5，重新进入新的分鱼行动。 经修改后的程序： yu = 6 yu1 = yu s = 0 DO IF (yu1 - 1) MOD 5 = 0 THEN s = s + 1 yu1 = (yu1 - 1) / 5 * 4 ELSE yu = yu + 5 yu1 = yu s = 0 END IF LOOP UNTIL s = 5 PRINT yu End 从上面的例子中我们也能看出，穷举算法一般都是用for语句来实现的，但有时在无法确定终值的情况下，就用条件循环解决问题。 9、背包问题 【问题描述】 小明有一个最多只能装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$(3) = "yu 3.5 jin" m$(4) = "jiangyou 1.7 jin": m$(5) = "baitang 1 jin": m$(6) = "tudou 5.1 jin" max = 0 FOR 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 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 IF NEXT f, e, d, c, b, a PRINT "zhong zhong liang zui da wei :"; max; "jin" FOR i = 1 TO 6 IF x(i) <> 0 THEN PRINT m$(i) NEXT i END 程序优化： 分析过程：本题考虑到最轻的5种物品的总重量为：5+2+3.5+1.7+1=13.2>10，因此，网袋中最多只能装下4件物品。这样，就可以考虑从所有物品的总重量中减去任意两种物品的重量，从而求得题目要求的结果。循环从6重变为2重，大大提高了效率。 s = 0 FOR i = 1 TO 6: READ a(i): s = s + a(i): NEXT I FOR i = 1 TO 6: READ m$(i): NEXT I {为打印作准备} max = 0 FOR 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 {满足条件要将数据纪录下来} NEXT j NEXT i PRINT "zongzhongliang wei:"; max; " jin" FOR i = 1 TO 6 IF i <> b AND i <> c THEN PRINT m$(i) {不是去掉的两个物品就打印} NEXT i DATA 5,2,3.5,1.7,1,5.1 DATA"baicai 5 jin","zhurou 2 jin","yu 3.5 jin","jiangyou 1.7 jin" DATA"baitang 1 jin","tudou 5.1 jin" 10、n种物品的背包问题（阅读材料） 【问题描述】 有不同价值、不同重量的物品n件，求从这n件物品中选取一部分物品的选择方案，使选中物品的总重量不超过指定的限制重量，但选中物品的价值之和最大。 【问题分析】 这种背包问题事先不知道物品的总件数，因此，用上面的解法是根本行不通的。设n个物品的重量和价值分别存储于数组w（）和v（）中，限制重量为tw。考虑一个n元组（x0，x1，…，x n-1），其中x i=0 表示第i个物品没有选取，而x i=1则表示第i个物品被选取。显然这个n元组等价于一个选择方案。用穷举法解决背包问题，需要穷举所有的选取方案，而根据上述方法，我们只要穷举所有的n元组，就可以得到问题的解。 显然，每个分量取值为0或1的n元组的个数共为2n个。而每个n元组其实对应了一个长度为n的二进制数，且这些二进制数的取值范围为0～2n-1。 根据上面的分析，如果把0～2n-1分别转化为相应的二进制数，则可以得到我们所需要的2n个n元组。我们以此作为穷举的范围。 【程序清单】 DIM a(100), b(100), x(100), w(100), v(100) INPUT n, tw FOR i = 1 TO n: INPUT w(i), v(i): NEXT i p = 1 FOR i = 1 TO n: p = p * 2: NEXT max = 0 FOR i = 0 TO p - 1 x = i: w = 0: v = 0 FOR j = 1 TO n: x(j) = 0: NEXT j j = 0 DO {转化为二进制数} j = j + 1 x(j) = x MOD 2 x = x \ 2 LOOP UNTIL x = 0 FOR k = 1 TO n w = w + w(k) * x(k) v = v + v(k) * x(k) NEXT k IF (w <= tw) AND (v > max) THEN max = v {纪录最大价值的数据值} FOR k = 1 TO n b(k) = x(k) NEXT k w1 = w END IF NEXT i FOR k = 1 TO n {输出最大价值的方案} IF b(k) <> 0 THEN PRINT w(k), v(k) NEXT k PRINT "zong zhongliang:"; w1 PRINT "zong jiazhi:"; max 例11 见小学培训教程p208 [例10-8] 例12 见小学培训教程p209 [例10-9] 小结： 穷举算法是一种比较“笨”的方法，它通过列举所有情况然后逐一判断来得到结果。 穷举的思想很简单，但是可以引发我们很多的思考： 穷举什么？怎样穷举？能算出穷举方案的总数吗？运行速度够快吗？如果速度太慢，有什么优化方法吗？ 希望大家在学完这一章节后，对这一算法能熟练掌握。 本讲作业 1、从3，5，7，9，11，13，15七个数中任取两个组成最简真分数，共有几个？都是什么数？ 2、算24（2001年省小学组竞赛题四）。给出4个1-1000之间的整数，用这四个整数，通过+、-、*的运算而得到24，运算规则如下： （1）每个数必须使用一次，只能使用一次。 （2）运算符无优先级之分，自左向右计算。 例如：输入4个数为2，9，3，1 则计算方法为3+9*2*1=24 3、求素数个数（2002年省小学组竞赛题三前半题）将1，2，…，n个数（n<=7）按顺时针方向排成一圈，然后从任意位置开始按顺时针方向连续取k个数字组成一个k位数。 （k 例如：n=3 k=2按顺时针方向排成如下一圈： 1 3 2 此时可组成：12，23，31。其中的素数有23，31。 问题一：当给出n、k后，求出在n个k位数种有多少个素数？ 问题二：将这n个数重新排列，找出能产生k位数中的素数最多的一种排列，并统计出可能产生的素数个数。 输入：n,k 输出：x1 …问题一的解 X2 …问题二的解（仅需个数，不用输出排列） 4、将2n个0和2n个1，排成一圈。从任一个位置开始，每次按逆时针的方向以长度为n+1的单位进行数二进制数。要求给出一种排法，用上面的方法产生出来的2n+1个二进制数都不相同。 第五讲穷举算法 学习重点： 1、了解穷举法的基本概念及用穷举法设计算法的基本过程。 2、能够根据具体问题的要求，使用穷举法设计算法，编写程序求解问题。 3、能对穷举法编写的程序进行优化 学习过程： 穷举算法是学生在学完了QB基本语句后最早接触到的算法。一些简单的穷举算法题目如求水仙花数、找出缺失的数字等和小学生的数学学习紧密结合，程序也比较容易实现，因此学生的学习兴趣还是很高的。近几年的省小学生程序设计竞赛中也常出现穷举算法的题目，如：2001年题四算24；2002年题三求素数个数与素数个数最多的排列；2005年回文数个数等题目，有些题虽然说用穷举算法实现比较勉强（如2002年题三的后半题求出素数个数最多的排列），但在考试时，如果一时想不出更好的办法，用穷举算法也不失为一种明智的选择。 穷举法，常常称之为枚举法，是指从可能的集合中一一穷举各个元素，用题目给定的约束条件判定哪些是无用的，哪些是有用的。能使命题成立者，即为问题的解。 穷举是最简单，最基础，也是通常被认为非常没效率的算法，但是。穷举拥有很多优点，它在算法中占有一席之地。首先，穷举具有准确性，只要时间足够，正确的穷举得出的结论是绝对正确的；其次，穷举拥有全面性，因为它是对所有方案的全面搜索，所以，它能够得出所有的解。 采用穷举算法解题的基本思路： （1）确定穷举对象、穷举范围和判定条件； （2）一一列举可能的解，验证是否是问题的解 一、穷举算法的实现 在前面基础语句（for语句）的学习中，其实我们就用到了穷举。比如培训教材p77【例5-7】打印九九乘法表中，被乘数A和乘数B都从1-9一一列举。这样，九九乘法表中就不会遗失任何一句乘法口诀；在p79【例5-9】的数学灯谜题中，我们也是用了一一列举的方法，找出了A、B、C、D的取值范围。 下面我们再看两道例题： 1、搬运砖头 【问题描述】36 块砖， 36 人搬。男搬 4 ，女搬 3 ，两个小儿抬一砖。要求一次全 用穷举法解决问题教学设计 【教材分析】 本节课选自教科版《算法与程序设计》选修第三章的第二节。本节课讲的是现实生活中解决问题的一种算法——穷举法，实际上是使用for－next循环语句来解决实际问题。本节要求学生初步了解穷举算法的思想，总结出穷举法解决问题的一般步骤，总结出哪一类的、具有什么特征的问题适合用穷举法来解决。本课内容是对算法学习的引入，为高中阶段算法的学习打下了基础。 【学情分析】 本节内容的教学对象是高二年级学生，他们已经具备了一定的逻辑思维、分析问题、表达思想等能力。同时，通过前两个章节的学习与实践，学生已经历了用计算机解决问题的过程与步骤，学会了对计算机程序进行调试，并掌握了顺序、选择、循环三种程序结构，为本节内容的学习提供了良好的基础。前一节的学习，学生掌握了如何用解析法解决问题，但现实生活中也有很多问题往往无法用解析法找到答案，这时候我们可以尝试采用另外一种方法“穷举法”，从而引出本课内容。因此对此类问题的归纳求解，学生应该掌握。 【教学目标】 知识与技能： 1、巩固for…next循环语句的格式和运用。 2、了解什么是穷举法以及用穷举法解决问题的一般步骤。 3、了解穷举法具有一定的适用范围。 4、能够根据具体问题的要求，使用穷举法设计算法。 过程与方法： 本节以“百钱买百鸡问题”入手，由浅入深讲解了穷举算法的思路。通过讨论、对比、总结，熟练掌握穷举算法求解问题的方法。在编程实践之后，对各种方案进行对比试验，加深穷举算法的理解。 情感态度与价值观： 了解算法和程序设计在计算机解决问题过程中的重要性；体验将算法转变为程序的过程，享受计算机解决问题的快乐；培养学生发现、探索和创新的能力。 【教学重、难点】 重点：用穷举法解决问题的一般步骤；能根据具体问题的要求，提高运用穷举法解决问题的能力。 难点：哪一类问题适合穷举法，确定穷举的范围以及评价穷举效率的高低。 【教学方法】 本节内容理论性和实践性都比较强，所以用演示、实践、讨论、任务驱动等多种形式的教学活动让枯燥的内容和生动有趣的任务结合起来。 【教学课时】 1课时 【教学环境】 硬件：机房一间，多媒体教学系统一套 软件：Visual Basic软件、自制的课件 【教学过程】 一、导入 上节课我们学习用解析法解决问题，用解析法解决问题的过程是：分析问题→抽取数学模型→导出解析表达式→设计算法→编写代码→调试运行程序。用解析法解决问题具有高效、快捷的特点，但是解析法也有“束手无策”的时候，有些问题即使可以用解析法，但求解过程和 数学建模竞赛中应当掌握的十类算法 排名如下： 1、蒙特卡罗算法（该算法又称随机性模拟算法，是通过计算机仿真来解决问题的算法，同时可以通过模拟可以来检验自己模型的正确性，是比赛时必用的方法） 2、数据拟合、参数估计、插值等数据处理算法（比赛中通常会遇到大量的数据需要处理，而处理数据的关键就在于这些算法，通常使用Matlab作为工具） 3、线性规划、整数规划、多元规划、二次规划等规划类问题（建模竞赛大多数问题属于最优化问题，很多时候这些问题可以用数学规划算法来描述，通常使用Lindo、Lingo软件实现） 4、图论算法（这类算法可以分为很多种，包括最短路、网络流、二分图等算法，涉及到图论的问题可以用这些方法解决，需要认真准备） 5、动态规划、回溯搜索、分治算法、分支定界等计算机算法（这些算法是算法设计中比较常用的方法，很多场合可以用到竞赛中） 6、最优化理论的三大非经典算法：模拟退火法、神经网络、遗传算法（这些问题是用来解决一些较困难的最优化问题的算法，对于有些问题非常有帮助，但是算法的实现比较困难，需慎重使用） 7、网格算法和穷举法（网格算法和穷举法都是暴力搜索最优点的算法，在很多竞赛题中有应用，当重点讨论模型本身而轻视算法的时候，可以使用这种暴力方案，最好使用一些高级语言作为编程工具） 8、一些连续离散化方法（很多问题都是实际来的，数据可以是连续的，而计算机只认的是离散的数据，因此将其离散化后进行差分代替微分、求和代替积分等思想是非常重要的） 9、数值分析算法（如果在比赛中采用高级语言进行编程的话，那一些数值分析中常用的算法比如方程组求解、矩阵运算、函数积分等算法就需要额外编写库函数进行调用） 10、图象处理算法（赛题中有一类问题与图形有关，即使与图形无关，论文中也应该要不乏图片的，这些图形如何展示以及如何处理就是需要解决的问题，通常使用Matlab进行处理） 8.1 遗传算法的概念 是建立在自然选择和自然遗传学机理基础上的迭代自适应概率性搜索算法，在1975年由Holland教授提出。 生物的进化是一个奇妙的优化过程，它通过选择淘汰，突然变异，基因遗传等规律产生适应环境变化的优良物种。遗传算法是根据生物进化思想而启发得出的一种全局优化算法。 遗传算法的概念最早是由Bagley J.D在1967年提出的；而开始遗传算法的理论和方法的系统性研究的是1975年，这一开创性工作是由Michigan大学的 J.H.Holland所实行。当时，其主要目的是说明自然和人工系统的自适应过程。 常用算法——穷举搜索法 二、穷举搜索法 穷举搜索法是对可能是解的众多候选解按某种顺序进行逐一枚举和检验，并从众找出那些符合要求的候选解作为问题的解。 【问题】将A、B、C、D、E、F这六个变量排成如图所示的三角形，这六个变量分别取[1，6]上的整数，且均不相同。求使三角形三条边上的变量之和相等的全部解。如图就是一个解。 程序引入变量a、b、c、d、e、f，并让它们分别顺序取1至6的证书，在它们互不相同的条件下，测试由它们排成的如图所示的三角形三条边上的变量之和是否相等，如相等即为一种满足要求的排列，把它们输出。当这些变量取尽所有的组合后，程序就可得到全部可能的解。细节见下面的程序。 【程序1】 # include 穷举算法及解题 穷举算法及解题 例12-1古希腊人认为因子的和等于它本身的数是一个完全数（自身因子除外），例如28的因子是1、 2、4、7、14，且1+2+4+7+14=28，则28是一个完全数，编写一个程序求2~1000内的所有完全数。问题分析 （1）本题是一个搜索问题，搜索范围2~1000，找出该范围内的完全数；（2）完全数必须满足的条件：因子的和等于该数的本身； （3）问题关键在于将该数的因子一一寻找出来，并求出因子的和：分解因子的方法比较简单，采用循环完成分解因子和求因子的和。 程序如下： program p12_1; var a,b,s:integer; begin for a:=2to1000do begin s:=0; for b:=1to a-1do if a mod b=0then s:=s+b; if a=s then begin write(a,'=',1,); for b:=2to a-1do if a mod b=0then write('+',b); writeln; end; end; end. 当程序运行后,输出结果: 6=1+2+3 28=1+2+4+7+14 496=1+2+4+8+16+31+62+124+248 例12-3 邮局发行一套票面有四种不同值的邮票,如果每封信所帖邮票张数不超过三枚,存在整数r,使得用不超过三枚的邮票,可以贴出连续的整数1、2、3、……、r来，找出这四种面值数，使得r值最大。 问题分析：本题则是 知道每封信邮票数的范围(<=3),邮票有四种类型，编程找出能使面值最 第16章 穷举算法与实验 穷举方法是基于计算机特点而进行解题的思维方法。一般是在一时找不出解决问题的更好途径（即从数学上找不到求解的公式或规则）时，可以根据问题中的的部分条件（约束条件）将所有可能解的情况列举出来，然后通过一一验证是否符合整个问题的求解要求，而得到问题的解。这样解决问题的方法我们称之为穷举算法。穷举算法特点是算法简单，但运行时所花费的时间量大。因此，我们在用穷举方法解决问题时，应尽可能将明显的不符合条件的情况排除在外，以尽快取得问题的解。虽然穷举法效率并不高，但是适应一些没有明显规律可循的问题的解决。 因为穷举算法就是从所有可能的情况中搜索正确的答案，所以一般可按如下步骤： 第1步: 对于一种可能的情况，列举出来并计算其结果； 第2步：判断结果是否满足要求，如果不满足则执行第1步来搜索下一个可能的情况，如果满足要求，则表示寻找到一个正确的答案，执行下一步操作，如寻找其他正确（合适）的答案或者中断循环。 16.1三角形数问题 16.1.1 问题描述 将 ,F ,E ,D ,C ,B ,A 这六个变量排成如图所示的三角形，这六个变量分别取[1，6]上的 整数，且均不相同。求使三角形三条边上的变量之和相等的全部解。如图就是一个解。 A 6 B C 3 1 D F 2 4 E 5 16.1.2 问题分析 程序引入变量123456,,,,,i i i i i i ，代表,F ,E ,D ,C ,B ,A 并让它们分别顺序取1至6的正整数，在它们互不相同的前提条件下，测试由它们排成的如图所示的三角形三条边上的变量之和是否相等，如相等即为一种满足要求的排列，把它们输出。当这些变量取尽所有的组合后，程序就可得到全部可能的解。细节见下面的程序。 【程序1】 %穷举法解三角形数 for i1=1:6 for i2=1:6 if i1==i2 continue; 算法的程序实现——解析法、穷举法 一、目标导学: 1、 认识并学会使用解析法、穷举法分析问题、解决问题； 2、 尝试编程实现解析法、穷举法实例。 二、自主探究: 1、解析法： 就是在分析具体问题的基础上，抽取出一个数学模型，这个数学模型能用若干解析表达式表示出来，解决了这些表达式，问题也就得以解决。 用解析法解决问题的关键是寻找________________。 ☆实例：画钻石图案(如右图，教师机展示) 分析：钻石图案是由一个圆周上的各个点的连线组成的，要首先建立一个坐标系，并求出各个点的坐标，然后画线（line 方法）。如右图：可以得出第一个点的坐标是（r*cos(θ)，r*sin(θ)）,第二个点的坐标是（r*cos(2*θ)，r*sin(2*θ)）,……依次类推，可得出所有点的坐标。 实现：（1）设置界面。在form1上添加picture1和command1。设置picture1的height 和width 属性相等，command1的caption 属性为“绘制钻石”。 （2）双击command1按钮，打开其代码窗口，输入相关代码。运行验证。 2、穷举法：（枚举法、列举法） 将求解对象一一列举出来，然后逐一加以分析、处理，并验证结果是否满足给定的条件，穷举完所有对象，问题最终得以解决。 ☆实例： 输出100～200间不能被3整除的数。 分析：验证100到200间所有的数，如果满足条件则输出。 实现：在窗体上添加command1按钮，在其代码窗口中输入代码，如右所示。 说明： （1）10个数打印一行，a 为计数变量。i 为要验证的数。 （2）“Print ”为打印一回车，光标跳至下一行；“Print i;” 为在当前位置打印，光标向后移动。 三、交流点拨: 思考：1、我们前面解决的以下问题用的是解析法还是穷举法？ “韩信点兵”_________ “圆的周长、面积”__________“水仙花数”__________ 2、穷举法的适用问题的范围？ 求解对象是________(有限/无限) 的，________（可/不可）按规则列举。 一元二次方程求根________(可/不可)用穷举法列举? 四、建构拓展： 五、效果评价: 穷举法 穷举法是程序设计中使用最为普遍的一种基础算法。计算机的特点之一就是运算速度快、善于重复做一件事情，“穷举法”正是基于这一特点的最古老算法。它一般是在一时半会找不到解决问题的更好途径，即从数学上找不到求解的公式或规律时，根据问题中的“约束条件”，将求解的所有可能情况一一列举出来，然后再逐一验证它否符合整个问题的求解要求，从而得到问题的所有解。 示例1：求满足表达式A+B=C的所有整数解，其中A,B,C为1~3之间的整数。 【分析】本题非常简单，即枚举变量A，B，C的所有可能取值情况，对每种取值情况判断是否符合表达式即可。 【算法】算法用伪代码描述如下： for A:=1 to 3 do for B:=1 to 3 do for C:=1 to 3 do if(A+B=C) then writeln(A,’’,B,’’C); 【流程图】 所谓穷举法，指的是从可能的解的集合中一一枚举各元素，用题目给定的检验条件判定那些是无用的，哪些是有用的。能使命题成立的，即为解。 在本案例中解变量有3个：A，B，C。其中： 解变量A的可能取值范围A∈｛1,2,3｝ 解变量B的可能取值范围B∈｛1,2,3｝ 解变量C的可能取值范围C∈｛1,2,3｝ 从而问题的可能解有3*3*3=27个，可能解集 在上述可能解集中，满足题目给定的检验条件（A+B==C）的解元素，即为问题的解。 穷举法的适用范围：其一，能确定解变量（枚举变量）的个数n，其二，每个解变量Ai（1<=i<=n）的可能值能确定范围且能连续取得。 设解变量的个数是n，Ai1----解变量Ai的最小值；Aik----解变量Ai的最大值（1≤i≤n）；即A11≤A1≤A1k，Ai1≤Ai≤Aik，……，An1≤An≤Ank 算法框架如下（伪代码）： for A1←A11 to A1k do …… for Ai←Ai1 to Aik do …… for An←An1 to Ank do if状态（A1,…,Ai,…,An）满足检验条件 then 输出问题的解 穷举法（枚举法）的特点是算法简单，但是有时运算量大。为了提高效率必须优化枚举算法。 枚举算法的时间复杂度=状态总数*考查单个状态的耗时 要优化算法，可以从以下方面着手： （1）排除明显不属于解集的元素 （2）减少状态总数（即减少枚举变量和枚举变量的值域） （3）减低单个状态的考察代价 用穷举测试是较现实的测试方法 穷举测试（exhaustive testing）：亦称完全测试，即程序运行的各个可能分支都应该调试到。穷举法，可视为最简单的搜索。即是在一个可能存在可行状态的状态全集中依次遍历所有的元素，并判断是否为可行状态。 噢，好，我们现在已经抽取了两个基本概念，迫不及待要开始穷举了，但……怎么做呢？穷举的关键是“依次遍历”，即做到不重、不漏。呃，我们可以让听话的苹果们排成一行，放在“苹果数组”中，然后呢，我们就可以按照0号苹果、1号苹果、2号苹果、...、n号苹果这样的顺序成功遍历。好，我们解决了遍历苹果的问题……慢，我们现在是设计一个算法的抽象模型，如果一切待穷举的对象都已经活生生地摆在那里，当然有可能把它们全部收集起来并排队，但如果开始的时候我们并不知道所有要穷举的对象，比如我们或许要通过一台安装在探测飞船内的计算机在全宇宙范围内穷举出除地球以外有生命的星球，那么我们的计算机可能是随着飞船的前行方能不断地得到新星球的信息，而不是停在地球的时候就获得全宇宙的星球信息（就算可能，内存或许也装不下如此大的数据量——哪怕宇宙真的是有限“大”的）。所以我们不应当要求穷举进行之前就能获得状态全集中的所有状态，这样一来，我们的“苹果数组”计划就宣告流产了。现在再看看我们激动人心的星球搜索计划：它并没有把所有星球收罗排队，那么它成功的关键在哪里？在于飞船能否以适当的路径“光顾” 完所有的星球；我们把这个条件加强一下：飞船每次到达一个星球，都会看到星球上立着一个方向标，标示下一个星球的方位；而假定这样的标示保证飞船能够不重不漏地飞临宇宙中的所有星球。啊喔……你是不是觉得我这是在异想天开？哦，没关系，大不了我们不搜索星球了，而除此之外的很多现实穷举问题都可以满足这个加强条件。嗯，我承认本文讨论的是满足这个加强条件的稍稍狭义的穷举：它必须保证在知道一个状态的前提下能获得一个新状态，并且这样的“状态链”刚好能遍历整个状态全集。我们称从当前状态获得并转到下一个状态的过程为“状态跳转”（我是想用“状态转移”的，嗨，可惜它会与动态规划算法的术语相混淆）： 一、迭代法 迭代法是用于求方程或方程组近似根的一种常用的算法设计方法。设方程为f(x)=0，用某种数学方法导出等价的形式x=g(x)，然后按以下步骤执行： （1）选一个方程的近似根，赋给变量x0； （2）将x0的值保存于变量x1，然后计算g(x1)，并将结果存于变量x0； （3）当x0与x1的差的绝对值还小于指定的精度要求时，重复步骤（2）的计算。 若方程有根，并且用上述方法计算出来的近似根序列收敛，则按上述方法求得的x0就认为是方程的根。上述算法用C程序的形式表示为： 【算法】迭代法求方程的根 { x0=初始近似根； do { x1=x0； x0=g(x1)；/*按特定的方程计算新的近似根*/ } while ( fabs(x0-x1)>Epsilon)； printf(“方程的近似根是%f\n”，x0)； } 迭代算法也常用于求方程组的根，令 X=（x0，x1，…，x n-1） 设方程组为： x i=g i(X) (I=0，1，…，n-1) 则求方程组根的迭代算法可描述如下： 【算法】迭代法求方程组的根 { for (i=0;i第五讲 穷举算法
(完整word版)穷举法
数学建模应该掌握的十大算法(汇编)
常用算法(二)——穷举搜索法
穷举算法及解题
穷举法
算法的程序实现——解析法、穷举法
计算机算法：穷举法
用穷举测试是较现实的测试方法
最全最常用算法设计方法(C语言)