-
第五讲
穷举算法
学习重点:
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
搬完。问需男、女、小儿各若干?
【问题分析】题目要我们找出符合条件的男生、女生和小孩的人数。答案显然是一组
p>
数据。首先分析一下问题所涉及的情况。对于男生来说,至少要有一人;每个男生可以搬
p>
4
块砖,那么
36
块砖最多
9
个男生足够,共有
9
种不同取值。同样,女生有
12
种
不
同取值。两个小孩抬一块砖,至少要有两个小孩,最多
36
个,并且小孩的人数必须是个
偶数,所以小孩的人数可以取
p>
18
种不同的值。最坏情况下,男生、女生和小孩的人数可
p>
以是
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
”,但“
p>
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
)
p>
,
算一算能否凑成
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
处运算符,
每一处运算符
都应该有
“
+
”
、
“
-
”
、
“
*
”
、
p>
“
/
”
四种可能的
情况,因此,可以用三重循环一一列举;每一处运算符确定后,与它相邻的两
个数就有一
个结果,这个结果根据运算符来定,可能是两数的和或差或积或商,我们用
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
)
p>
请一个小朋友(小
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
)
【问题分析】
穷举对象:九头鸟、鸡、兔;
穷举范围:九头鸟:1~100
鸡:1~100
兔:1~100
判定条件:头和脚都等于100;
(程序见
p205 REM
L10-6A
)
这段程序是没有优化
的程序,在教学中,老师要分析最糟糕的情况下(找不到合适的
解)需循环的次数,然后
让同学们上机试一下,体会一下运行时间。
然后按
p206 REM L10-6B
减少循环次数及
REM L10-6C
减少穷举对象来优化程序。
从程序的
优化过程中,学生们能体会到使用穷举算法时,对程序优化的重要性。
书上的三段程序建议让学生都能上机试验,
加深体会。
P207
的程序可以布置数学基础
好的同学自己学习。
5
、巧填数字
【问题描述】
将1~6这六个数字分
别填到下面的圆圈中,使三角形的每边上的三个数的和相等,
一共有多少种方案?编程打
印这些方案。(不需要按题目的格式打印)
【问题分析】
穷举对象:
A,B,C,D,E,F
穷举范围:每一个对象都从
1
~
6 <
/p>
判定条件:(
1
)
A
、
B
、
C
、
D
、
E
p>
、
F
互不相等
(
2
)
A+B+C=C+D+E=A+F+E
6
对于小学生来说,
如何判定
6
个变量的取值分别是
1
~
6
的数,
并且互不相等可能是这
题的难点。在学习了一唯数组后,很容易想到的是:把这
p>
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
、
p>
C
、
E
就可以了;
判定条件只要
6
个数互不相
等。
【问题分析】
根
据已知条件:
A+B+C+D+E+F=21
,
则三条边的和相加为:
(
A+B+C
< br>)
+
(
C+D+E
)
+
(
E+F+A
)
=
(
A+C+E
p>
)
+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 用法大全
下一篇:数控系统代码