tceic.com
学霸学习网 这下你爽了
相关标签
当前位置:首页 >> 高一数学 >>

穷举法详细


第三讲 穷举法
一、穷举法的基本概念 穷举方法是基于计算机特点而进行解题的思维方法。 一般是在一时找不出解决问题的更 好途径(即从数学上找不到求解的公式或规则)时,可以根据问题中的的部分条件(约束条 件)将所有可能解的情况列举出来,然后通过一 一验证是否符合整个问题的求解要求,而 得到问题的解。这样解决问题的方法我们称之为穷举算法。穷举算法特点是算法简单,但运 行时所花费的时间量大。 有些问题所列举出来的情况数目会大得惊人, 就是用高速的电子计 算机运行, 其等待运行结果的时间也将使人无法忍受。 因此, 我们在用穷举方法解决问题时, 应尽可能将明显的不符合条件的情况排除在外,以尽快取得问题的解。 二、穷举算法模式 穷举算法模式: (1) 问题解的可能搜索的范围: 用循环或循环嵌套结构实现 (2) 写出符合问题解的条件。 (3) 能使程序优化的语句,以便缩小搜索范围,减少程序运行时间。 三、使用穷举法设计算法 穷举法应用很多,比如一些密码破译软件通常就是用的穷举算法。如在 QQ 上, OicqPassOver 这个工具穷举你的口令,它根据机器性能最高可以每秒测试 20000 个口令, 如果口令简单,一分钟内,密码就会遭到破译。下面我们来以三个例子说明穷举法的具体应 用。 实例一: 古希腊人认为因子的和等于它本身的数是一个完全数(自身因子除外),例 如28的因子是1、2、4、7、14,且1+2+4+7+14=28,则28是一个完全数,编写一个程序求2~ 1000内的所有完全数。 分析: (1) 本题是一个搜索问题,搜索范围 2~1000,找出该范围内的完全数; (2) 完全数必须满足的条件:因子的和等于该数据的本身。 (3) 问题关键在于将该数的因子一一寻找出来,并求出因子的和。 程序如下: Program Begin For a:=2 to 1000 do Begin S:=0 ; For b:=1 to a -1 do If a mod b =0 then s:=s+b ; { 分解因子并求和 } p3_1 ; Var a , b,s :integer ;

If

a=s

then begin Write( a, ‘=’ ,1, ); For b:=2 to a -1 If End; Writeln ; do a mod b=0 then write( ’+’, b );

End; End. 当程序运行后,输出结果: 6 = 1 + 2 + 3 28 = 1 + 2 + 4 + 7 + 14 496 =1 + 2 + 4 + 8 + 16 + 31 + 62 + 124 + 248 实例二:(第七届全国青少年信息学(计算机)奥林匹克分区联赛初赛试题) 在 A,B 两个城市之间设有 N 个路站(如下图中的 S1,且 N<100),城市与路站之间、路 站和路站之间各有若干条路段(各路段数≤20,且每条路段上的距离均为一个整数)。A,B 的 一条通路是指:从 A 出发,可经过任一路段到达 S1,再从 S1 出发经过任一路段,…最后到 达 B。通路上路段距离之和称为通路距离(最大距离≤1000)。当所有的路段距离给出之后, 求出所有不同距离的通路个数(相同距离仅记一次)。例如:下图所示是当 N=1 时的情况:

从 A 到 B 的通路条数为 6,但因其中通路 5+5=4+6,所以满足条件的不同距离的通路条数为 5。 算法说明:本题采用穷举算法。 数据结构:N:记录 A,B 间路站的个数 数组 D(I,0)记录第 I-1 到第 I 路站间路段的个数 D(I,1),D(I,2),…记录每个路段距离 数组 G 记录可取到的距离 PROGRAM CHU7_6; VAR I,J,N,S:INTEGER; B:ARRAY[0..100]OF INTEGER; D:ARRAY[0..100,0..20]OF INTEGER; G :ARRAY[0..1000]OF 0..1; BEGIN

READLN(N); FOR I:=1 TO N+1 DO BEGIN READLN(D[I,0]); FOR J:=1 TO D[I,0]DO READLN(D[I,J]); END; D[0,0]:=1; FOR I:=1 TO N+1 DO B[I]:=1; B[0]:=0; FOR I:=0 TO 1000 DO G[I]:=0; WHILE ① DO BEGIN S:=0; FOR I:=1 TO N+1 DO S:= ② G[S]:=1;J:=N+1; WHILE ③ DO J:=J-1; B[J]:=B[J]+1; FOR I:=J+1 TO N+1 DO B[I]:=1; END; S:=0; FOR I:=1 TO 1000 DO ④ ; WRITELN(S);READLN; END. 答案: ① B[0]=0 ② S+D[I,B[I]]; ③ B[J]=D[J,0]
④ S:=S+G[I]

实例三(第八届全国青少年信息学奥林匹克联赛(NOIP2002)试题)
将 n 个整数分成 k 组(k≤n,要求每组不能为空),显然这 k 个部分均可得到一个各自的和 s1,s2,……sk, 定义整数 P 为:P=(S1-S2)2+(S1 一 S3)2+……+(S1-Sk)2+(s2-s3)2+……+(Sk-1-Sk)2 问题求解:求出一种分法,使 P 为最小(若有多种方案仅记一种) 程序说明: 数组:a[1],a[2],...A[N]存放原数 s[1],s[2],...,s[K]存放每个部分的和 b[1],b[2],...,b[N]穷举用临时空间 d[1],d[2],...,d[N]存放最佳方案 程序: program exp4; Var i,j,n,k : integer; a :array [1..100] of integer; b,d:array [0..100] of integer;

s :array[1..30] of integer; begin readln(n,k); for I:=1 to n do read(a[I]); for I:=0 to n do b[I]:=1; cmin:=1000000; while (b[0]=1) do begin for I:=1 to k do for I:=1 to n do ② sum:=0; for I:=1 to k-1 do for j:= if begin cmin:=sum; for I:=1 to n do d[I]:=b[I]; end; j:=n; while ⑤ do j:=j-1; ⑥ b[j]:=b[j]+1; for I:=j+1 to n do end; writeln(cmin); for I:=1 to n do write(d[I]:40); writeln; end. ④ ③ sum:=sum+(s[I]-s[j])*(s[I]-s[j]); then ①

四、穷举算法的深入应用 实例一:一根29厘米长的尺子, 只允许在上面刻七个刻度, 要能用它量出 1~29 厘 米的各种长度。试问这根尺的刻度应该怎样选择? 分析: (1) 从 1~29 厘米中选择七个刻度的所有可能情况数是: C29
7

=

29·28·26·25·24·23 = 29·9·26·5·2·23= 29·26·23·90= 1560780 1·2·3·4·5·6·7

(2) 对于每一组刻度的选择都需要判断是否能将 1~29 厘米的各种刻度量出来, 例如选择的刻度为: a1,a2,a3,a4,a5a,6,a7 那么能量出的刻度为: a1, 29-a1; a2, a2-a1, 29-a2; a3, a3-a1 ,a3-a2, 29-a3 ; 2 3 4

a4, a4-a1, a4-a2, a4-a3, 29-a4; a5, a5-a1, a5-a2, a5-a3, a5-a4, 29-a5; a6, a6-a1, a6-a2, a6-a3, a6-a4, a6-a5, 29-a6; a7-a1, a7-a2, a7-a2, a7-a3, a7-a4, a7-a5, a7-a6, 29-a7;

5 6 7 8

共可量出 2+3+4+5+6+7+8 种刻度, 即 35 种刻度, 事实上其中有许多刻度是重复 的, 不可能复盖 1~29。例如: 取 a1, a2, a3, a4, a5, a6, a7 为 1, 3, 6, 10, 15, 21, 28 能量出的刻度为: 1, 3, 6, 10, 15, 21, 28, 28 2, 5, 9, 14, 20, 27, 26 3, 7, 12, 18, 25, 23 4, 9, 15, 22, 19 5, 11, 18, 14 6, 13, 8 7, 1

缺 16,17,24 ( 29 即尺子长度 ) 如 果 找 出 了 刻 度 a1, a2, a3, a4, a5, a6, a7 那 么 我 们 可 以 利 用 其 对 称 性 29-a1,29-a2,29-a3,29-a4,29-a5,29-a6,29-a7, 也 是 一 组 解 , 所 以 求 解 过 程 中 可 仅 考 虑 a1<a2<a3<a4<a5<a6<a7 的情况。 很显然要使 1,28 两种刻度能量出来, 则在七个刻度就必须有 1 或 28; 这样就可 设 a1=1 ( 或 a1=28 )。本题就变成了只要在 2~27 中选取六个刻度问题了。其刻度选 择的数目为 C26
6

= 26·25·24·23·22·21 1·2·3·4·5·6

= 26·5·23·11·7 = 230230

这样解的范围就从百万变成了十万的数量级, 大大减少运行次数。因此,我们在用 穷举法求问题解时,应注意程序的优化,尽可能减少搜索时间。 { 程序优化 } (3) 为了判定七个刻度是否能够度量 1~29 的所有长度, 可以用集合的方法, 也可 以用数组的 0,1 数据判断。下面的程序使用了数组的 0,1 方法。 Program Const Var p12_2 ; n=29 ; m=1; of of integer; 0..1 ; { 记录能量的刻度 }

a:array [1..7] b:array [1..n] f:Boolean ; I , j : integer ;

BEGIN a[1]:=m; for for for for a[2]:=2 to n-7 do to to to n-6 n-5 n-4 do do do

a[3]:=a[2]+1 a[4]:=a[3]+1

a[5]:=a[4]+1

for for

a[6]:=a[5]+1

to to

n-3 n-2

do do

a[7]:=a[6]+1

begin for for i:=1 i:=1 begin b[a[i]]:=1; for end; j: =0; for if i;=1 j=n for to n do j:=j + b[i]; begin to 7 do write (a[i]:4); j:=i+1 b[n-a[i]]:=1; TO 7 do b[n]:=1 ; { 初始化 } to TO 29 7 do do b[i]:=0;

b[abs(a[j]-a[i])]:=1

then i:=1 writeln ;

end ; end; end. 运行程序的结果: 当 m=1 时得出两组刻度 1 1 2 4 14 10 18 17 21 22 24 24 27 27

m=28 时也可获得两组刻度 28 28 2 2 5 5 7 8 13 11 19 15 25 27

这两组刻度实际上是 m=1 的对称情况, 所以问题的解实质上为两组结果。如果调 整n=30 可以发现在这样的情况下程序无解, 这说明取 30cm 长的尺子, 若仍取七个刻 度, 要能量出 1~30cm 的各种长度, 是不可能的。 实例二: 邮局发行一套票面有四种不同值的邮票, 如果每封信所贴邮票张数不超过三枚, 存在整数R,使得用不超过三枚的邮票,可以贴出连续的整数1、2、3,…,R来,找出 这四种面值数,使得R值最大。 分析: 本题知道每封信邮票数的范围(<=3 ),邮票有四种类型,编程找出能使面值最大邮票。 其算法是: (1) 面值不同的四种邮票,每封信所贴邮票不超过 3 张。 (2) 用这四种邮票贴出连序的整数,并且使R值最大。 (3) 用穷举法,找出所有符合条件的解。 (4) 本题用集合的方法统计邮票的面值,提高判重的速度。 设四种邮票的面值分别为: A , B , C , D ,根据题意设:

A < B < C < D,因此 A=1 ,用循环语句完成搜索。 Program p12_3 ; x, x0, x1 , x2 , x3, x4 : integer ; st1 : set of 1 . .100 ; Function number( a, b, c, d : integer ) : integer ; var a, b , c , d : integer ;

var n1, n2, n3 ,n4 , sum :integer ; begin st1:=[ ] ; for n1:= 0 to for n2:= 0 for n3:= 0 for 3 do to 3-n1 do do do { 每种邮票所取的张数 }

to 3-n1- n2

n4:= 0 to

3-n1-n2-n3

begin if n1+n2+n3+n4 <= 3 then begin sum:= n1*a+n2*b+n3*c+n4*d ; { 计算信封的邮票面值 } st1:=st1+[sum] end; end; sum:=1 ; while sum in sum:=sum+1; number:= sum-1; end ; BEGIN { { 函数结束 } main } st1 do

a:=1 ; x0:=0 ; for b:= a+1 to 3*a+1 do for c:= b+1 to 3*b+1 do do { 调用函数求每封信的邮票总面值 } { 每种邮票的可取值的范围 }

for d:= c+1 to 3*c+1 begin x:= number (a, b, c, d ); if x > x0 then begin

x0:=x; x1:=a ; x2:=b ; x3:=c ; x4:=d { 保存最大面值邮票 } write( x1:5, x2:5, x3:5, x4:5 );

writeln( ‘ ‘:10, 'x0=', x0 ); end; end; end. 程序运行后,其输出结果是:{ 解答结果有11 组} 1 2 3 4 5 x0=12 x0=13

1 2 3 ……. 1 3 6

10

x0=23

1 4 7 8 x0=24 【例题 3】如图所示的 8 个格子中放入 1~8 八个数字,使得相邻的 和对角线的数字之差不为 1。编程找出所有放法。我们先不考虑后一条 件,只考虑第一个条件,即把 1~8 八个数字放入 8 个格子中。这是容 易做到的,就是 8 个数字的全排列,共有 8!=40320 种放法。然后对这 8!个可行解用后一个条件加以检验,输出符合条件的解。对于后一个条 件中“相邻”的判断,可以建立一个邻接表来解决: i│ 1 2 3 4 5 6 7 8 9 10 11 12 13 14 ──┼────────────────────── j 1│ 1 1 1 2 2 2 3 3 3 4 5 5 6 7 2│ 2 3 4 3 5 6 4 6 7 7 6 8 7 8 表中表示哪两个格子是相邻的,link[i,1]和 link[i,2]是相邻的格子的编号。全排列的产 生,可以用八重循环,也可以用专门的算法,程序留给同学们自己去完成。利用穷举策略编 制的程序,其运算量一般是很大的,因此如何提高算法效率是穷举算法一个很重要的问题。 一般应尽量减少可行解的个数,使得第二步的检验运算量尽可能地少。例如对于例 5-1,如 何来优化算法呢?如果注意到 b3 和 b6 两个格子,与它们“相邻”的格子有 6 个,也就是说, 放入这两个格子中的数,必须和 6 个数不连续,仅可以和一个数是连续的,这样的数只有 2 个,即 1 和 8。这样,b1,b3,b6,b8;4 个格子中数的放法仅有两种可能:2、8、1、7 和 7、1、8、2。而 b2、b4、b5、b7 四个格子中的数仅需在 3~6 四个数中选择。经过上述优化, 可行解仅有:2×4!=48 个,大大减少了计算量。并且检验是否符合要求,也只需检查(1, 2),(1,4),(2,5),(4,7),(5,8),(7,8)这 6 对数之差就可以了。按改进的算法编制的 PASCAL 程序如下: program exampleb; uses Crt: const link:array[1..6,1..2] of integer= ((1,2),(1,4),(2,5),(4,7),(5,8),(7,8)); var b:array[1..8] of integer; procedure print; begin writeln(' ',b[1]:2); writeln(b[2]:2,b[3]:2,b[4]:2); writeln(b[5]:2,b[6]:2,b[7]:2); writeln('',b[8]) end;

function choose:boolean; var i: integer; begin choose:= false; fori:=1 to 6 do if abs(b[link[i, 1]] - b[link[i ,2]]) = 1 then exit; choose := true end; procedure try; begin for b[2]:=3 to 6 do for b[4]:= 3 to 6 do if b[2]&lt;&gt;b[4] then for b[5]:= 3 to 6 do if (b[5]&lt;&gt;b[2]) and (b[5]&lt;&gt;b[4]) then begin b[7]:= 18 - b[2] - b[4] - b[5]; if choose then print; end; end; { main program } begin clrscr; b[1]:=2;b[3]:=8;b[6]:= 1;b[8]:=7; try; b[1]:=7;b[3]:=1 ;b[6]:=8;b[8]:=2; try; readln end. 上面优化算法的方法是尽可能减少可行解的数目,也称为“剪枝” ,即把明显不符合条 件的可行解尽可能地剪去,减少穷举的计算量。

本次作业: 一、问题描述: Farmer John 的奶牛们喜欢看书,并且 Farmer John 发现在他的奶牛们稍微看了些有 关于自然科学的书时,会产出更多的牛奶。他决定更新牛棚里的图书馆,把原廉价的小说换 成算术和数学的课本。不幸的是,有些新书掉到了泥浆里面,现在它们的 ISBN 号码很难分 辨出来了。 ISBN(国际标准图书编号)是由十个阿拉伯数字组成的编码,用来唯一地标识一本书。

前九个阿拉伯数字描述这本书的一些信息,最后一个数字用来验证 ISBN 码是否正确。要验 证 ISBN 码的正确性,你要把第一个数字乘以十,你要把第二个数字乘以九,你要把第三个 数字乘以八……直到最后一个数字乘上一,再把这些积累加起来。如果所得的和可以被 11 整除的话,那么这就是一个合法的 ISBN 码。 比如说 0201103311 是一个合法的 ISBN,因为 10*0+9*2+8*0+7*1+6*1+5*0+4*3+3*3+2*1+1*1=55 前九个数字都在 0 到 9 之间。有时候,最后一个数字需要取到 10,那么我们就把最后 一个数字写成大写 X(这时就不叫数字了,呵呵) 。比如 156881111X 也是一个合法的 ISBN 码。 你的任务就是在给你丢失了一个数字的 ISBN 码之后,确定那个丢失的数字。丢失数字 的地方用?表示。 输入格式: 总共 1 行,一个十个数字组成的 ISBN 码,其中包含用?表示的一个丢失的数字。 输出格式: 总共 1 行:就是那个丢失的数码(0..9 或大写 X) 。如果标有的?的位置上没有数字可以 使之成为一个合法的 ISBN 码的话,就输出-1。 二、求数组元素[问题描述] 求数组元素[问题描述] 求数组元素 给出任意一个自然数 N (N≤100),输出满足下列条件的数组元素及不同方案数,条件 是: <1> 数组元素由各不相同自然数组成; <2> 数组元素的最后一个元素必为 N; <3> 每一个数组元素都不小于它前面一个元素的平方 (第一个元素除外); <4> 数组中包含的元素个数可不相同,但至少要有一个元素。 例如: N=1 输入: N (不用判错) 数组 (1) 输出: 一个 (不同方案数) K=1 (以 K 记录不同的方案数) 又如: N=5 数组 (5) (1,5) (1,2,5) (2,5) K=4


推荐相关:

用穷举法设计程序

3 4 提出任务:让学生自己动手实践,编程实现“百钱百 鸡”问题的求解 穷举法的优化:将两组程序代码演示给学生, (详细 代码请见附录:代码一、二, ) 教师巡视,...


《用穷举法解决问题》教学设计

其次,在课本第三章,我的教学方法借鉴了数学课的教法:从简单问题详细剖析,推出...2.过程与方法 ⑴经历用穷举法求解问题的基本过程。 ⑵在学习过程中,发现穷举法...


10 用穷举法解决问题

10 用穷举法解决问题_数学_自然科学_专业资料。用穷举法解决问题【教学目标】 1.了解什么是穷举法及其特点 2.用穷举法设计算法的基本过程 3.能够根据具体问题的...


穷举法

穷举法_学科竞赛_小学教育_教育专区。计数法导学案 课题:穷举法 审核: 课型:新授 使用时间: 执笔: 一、学习目标 1、 字典排列法 2、 累加法 二、重点难点 ...


穷举法(排列组合)

穷举法(排列组合) 1、四人分书 把 23 本书分给甲、乙、丙、丁 4 人,要求这四人得到的书的数量分别不得超过 9 本、8 本、 7 本、6 本,问有多少种不...


穷举法练习(含源程序)

穷举法练习(含源程序)_学科竞赛_初中教育_教育专区。穷举法练习,pascal语言信息学竞赛练习十八(穷举法) 1、 字母排列。在前 5 个大写英文字母(A、B、C、D、E...


穷举法

= =sum(a(7:9).*[100 10 1] ) disp(a); end for i1=9:-1:2 %此循环用于实现穷举算法,详细见本章 改编程序 1’ if all(a(i1)-a(i1-1)>...


穷举法

穷举法_学科竞赛_小学教育_教育专区。循环结构的嵌套应用举例 —穷举法(VB)教材...穷举法详细 10页 1下载券 用穷举法解决问题 10页 免费 如何用穷举法解决问题...


《用穷举法解决问题》

《用穷举法解决问题》_其它课程_高中教育_教育专区。“用穷举法解决问题”教学设计 《用穷举法解决问题》导学案章节与课题 主备人 使用人 《用穷举法解决问题》 ...


穷举法研究

穷举法研究_数学_自然科学_专业资料。穷举算法探究报告一、 穷举算法原理介绍 穷举法的基本思想是根据题目的部分条件确定答案的大致范围, 并在此范围内对所有可能的...

网站首页 | 网站地图
All rights reserved Powered by 学霸学习网 www.tceic.com
copyright ©right 2010-2021。
文档资料库内容来自网络,如有侵犯请联系客服。zhit325@126.com