-
第五讲
穷举算法
学习重点：
1
、了解穷举法的基本概念及用穷举法设计算法的基本过程。
2
、能够根据具体问题的要求，使用穷举法设计算法，编写程序求解问题。
3
、能对穷举法编写的程序进行优化
学习过程：
穷举算法是学生在学完了
QB
基本语句后最早接触到的算法。
一
些简单的穷举算法题目
如求水仙花数、找出缺失的数字等和小学生的数学学习紧密结合，
程序也比较容易实现，
因此学生的学习兴趣还是很高的。近几年的省小学生程序设计竞赛
中也常出现穷举算法的
题目，如：
2001
年题四算
24
；
2002
年题三求素数个数与素数个数最多的排列；
2005
年回
文数个数等题目，
有些题虽然说用穷举算法实现比较勉
强
（如
2002
年题三的后半题求出素
数个数最多的排列）
，
但在考试时，<
/p>
如果一时想不出更好的办法，
用穷举算法也不失为一种
明智的选择。
穷举法
，常常称之为枚举法，是指从可能的集合中一一穷举各个元素，用题目给定的
约束条件判
定哪些是无用的，哪些是有用的。能使命题成立者，即为问题的解。
< br>穷举是最简单，最基础，也是通常被认为非常没效率的算法，但是。穷举拥有很多优
点，它在算法中占有一席之地。首先，穷举具有准确性，只要时间足够，正确的穷举得出
的结论是绝对正确的；其次，穷举拥有全面性，因为它是对所有方案的全面搜索，所以，
它能够得出所有的解。
采用穷举算法解题的基本思路：
（<
/p>
1
）确定穷举对象、穷举范围和判定条件；
（
2
）一一列举可能的解，验证是
否是问题的解
一、穷举算法的实现
在前面基础语句
（
for
语句）的学习中，其实我们就用到了穷举。比如培训教
材
p77
【例
5-7
< br>】打印九九乘法表中，被乘数
A
和乘数
< br>B
都从
1-9
一一列举。这样，
九九乘法表
中就不会遗失任何一句乘法口诀；
在
p79
【例
5-9
】
的数学灯谜题中，
我们也是用了一一列
举的方法
，找出了
A
、
B
、
C
、
D
的
取值范围。
下面我们再看两道例题：
1
、搬运砖头
【问题描述】
36
块砖，
36
人搬。男搬
4
，女搬
3
，两个小儿抬一砖。要求一次全
1
搬完。问需男、女、小儿各若干？
【问题分析】题目要我们找出符合条件的男生、女生和小孩的人数。答案显然是一组
数据。首先分析一下问题所涉及的情况。对于男生来说，至少要有一人；每个男生可以搬
4
块砖，那么
36
块砖最多
9
个男生足够，共有
9
种不同取值。同样，女生有
12
种
不
同取值。两个小孩抬一块砖，至少要有两个小孩，最多
36
个，并且小孩的人数必须是个
偶数，所以小孩的人数可以取
18
种不同的值。最坏情况下，男生、女生和小孩的人数可
以是
9
×
12
×
18
＝
1944
种不同组合。假设男生人数为
x
，女生人数为
y
，小孩人
数为
z
。可以构建一个三重循环求出最终结果。
【程序清单】
rem 5_
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
、方格内填字符
< br>【问题描述】在
5
个连成一串的方格内填入“
a
”和“
b
”，但“
b
”不能填在相邻两格
内。打印出所有填法
和总方案数。
【问题分析】
(1)<
/p>
用五重循环列举；
（
2
< br>）由于
QB
中
FOR
语句不能直接列举字符，所以
用“
A
”和“
B
”的
ASCII<
/p>
码作为循环的初值和终值；
（
3
）需排除含“
BB
”
、
“
AAAAA
”的各种
情况。
【程序清单】
REM 5_
s = 0
bb =
132: aaaaa = 325
’连续填“
BB
”的
ASCII
和为
132
，
“
AAAAA<
/p>
”为
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
2
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
点。
（说
明：数字的顺序不能改变，并按从左到右的次序运
算，不考虑运算符的优先级别）
例如：输入
< br>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_
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
’列举第二处的运算符
’列举第一处的运算符
3
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
4
END SELECT
PRINT d
END IF
NEXT k
NEXT
j
NEXT i
END
【想一想】能不能简化打印语句，去掉里面的三个
SELECT
CASE
语句？
【
教法指导
】在本单元的学习中，对我们的教学对象——小学生进行该算法教学的时候，
我们首先应
该让他们了解什么是穷举法？
教学的设计可以从游戏入手：
（
1
）
请一个小朋友（小
X
）任意想一个
4
位数，写在纸上；
（
2
）
请全体同学猜，这个数是几？
（
3
）
每次说出一个数，裁判（老师）回答“对或错”
在所有同学猜过一遍后（可能会有同学猜出这个数，可以多次重复玩这个游戏），老
< br>师可以请同学们思考，怎样才能百发百中地猜中这个数呢？（老师可以将他们的回答引导
< br>到从
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
老师可以根据这个程序说明什么叫“穷举算法”。
二、穷举算法的优化
5
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 <
/p>
判定条件：（
1
）
A
、
B
、
C
、
D
、
E
、
F
互不相等
（
2
）
A+B+C=C+D+E=A+F+E
6
对于小学生来说，
如何判定
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
这段小程序的适用范围很广，
它可以用来判断出任意六个数是否互不相等。<
/p>
但在本题，
由于已知的数是
1
～
6
的连续整数，
因此可
用更少的语句来实现。
只要满足：
A+B+C+D+E+F=2
1
且
A*B*C*D*E*F=720
就能判别出
A
～
F
< br>一定是互不相等的数。
【程序清单】
Rem 5_
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
END
程序的优化：在小学数学的范围内，学生们可以做的改进是：减少一个循环语句，从
< br>而使效率提高
6
倍。程序留给老师们自己编写。
三、穷举对象的选择
7
在上题中，如果数学知识扩充的
话，只要
3
重循环就能解决问题。这就涉及到穷举对
象的选择问题。上题中，穷举对象分别取
A
、
C
、
E
就可以了；
判定条件只要
6
个数互不相
等。
【问题分析】
根
据已知条件：
A+B+C+D+E+F=21
，
则三条边的和相加为：
（
A+B+C
< br>）
+
（
C+D+E
）
+
（
E+F+A
）
=
（
A+C+E
）
+21
。每一条边的和为：
1/3*
（
A+C+E
）<
/p>
+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_
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
、成比例的三位数
【问题描述】
8
将
1,
2...9
共
9
个数分成三组
,
分别组成三个三位数
,
且使这三个三位数构成
1:2:3
的
比例
,
试求出所有满足条件的三个三位数
.
例如
:
三个三位数
192,384,576
满足以上条件
.
【问题分析】
这是
< br>1998
年全国分区联赛普及组试题。
此题数据规模不大
，
可以进行穷举，
如果我们
不假思索地
以每一个数位为穷举对象，一位一位地去穷举：
for a
=1 to 9
for b=1 to 9
???
for i=1 to 9
这样下去，
穷举次数就有
9
9
次。
如果我们分别设三个数为
< br>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
9
-
-
-
-
-
-
-
-
-
上一篇：#define 用法大全
下一篇：数控系统代码