haihongyuan.com
海量文库 文档专家
全站搜索:
您现在的位置:首页 > 小学教育 > 学科竞赛学科竞赛

枚举法

发布时间:2013-12-15 16:41:25  

基本算法——枚举法

技术教研组

谷方明

1 示例
求满足表达式A+B=C的所有整数解,其 中A,B,C为1~3之间的整数。

东北师大附中

例题分析
?本题非常简单,即枚举变量A,B,C的所 有可能取值情况,对每种取值情况判 断是否符合表达式即可。 ?算法如下
for(int A=1;A<=3;A++) for(int B=1;B<=3;B++) for(int B=1;B<=3;B++) if(A+B==C) 输出A,B,C;
东北师大附中

枚举法的定义
?所谓枚举法,指的是从可能的解的集 合中一一枚举各元素,用题目给定的 检验条件判定哪些是无用的,哪些是 有用的。能使命题成立的,即为解。

东北师大附中

?示例中的解变量有3个:A,B,C。其中 解变量A的可能取值范围A∈{1, … ,3} 解变量B的可能取值范围B∈{1, … ,3} 解变量C的可能取值范围C∈{1, … ,3} 从而问题的可能解有3*3*3=27个,可能解集: (A,B,C)∈{(1,1,1),(1,1,2),(1, 1,3),…,(3,3,1),(3,3,2),(3, 3,3)} ?在上述可能解集中,满足题目给定的检验条件 (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 A2←A21 to A2k do …………………… for Ai←Ai1 to Aik do …………………… for An←An1 to Ank do if 状态(A1,…,Ai,…,An)满足检验条件 then 输出问题的解;
东北师大附中

枚举算法的特点及优化
?枚举法的特点是算法简单,但有时运 算量大。 ?优化枚举算法(考察重点)
枚举算法的时间复杂度=状态总数*考察单 个状态的耗时 ? 排除明显不属于解集的元素 ? 减少状态总数(即减少枚举变量和枚举 变量的值域) ? 降低单个状态的考察代价
东北师大附中

?示例算法显然可以修改如下:
for(int A=1;A<=3;A++) for(int B=1;B<=3;B++) { C=A+B; if(C>=1)&&(C<=3) 输出A,B,C; } 通过变量的依赖关系减少了解变量的个数(局部 枚举),优化了枚举算法,n^3 -> n^2。
东北师大附中

枚举法解题的一般思路
?对命题建立正确的数学模型; ?根据命题确定的数学模型中各变量的 变化范围(即可能解集); ?利用循环语句、条件判断语句逐步求 解或证明; 每一步都可以考虑优化
东北师大附中

2 例1 巧妙填数
?将1~9这九个数

字填入九个空格中。 每一横行的三个数字组成一个三位数。 如果要使第二行的三位数是第一行的 两倍, 第三行的三位数是第一行的三 倍, 应怎样填数。(一共4组解,一组 如下图)
1
3 5

9
8 7

2
4 6

东北师大附中

?本题目有9个格子,要求填数,如果不考虑 问题给出的条件,共有9!=362880种方案, 在这些方案中符合问题条件的即为解。因 此可以采用枚举法。
?但仔细分析问题,显然第一行的数不会超 过400,实际上只要确定第一行的数就可以 根据条件算出其他两行的数了。这样仅需 枚举400次。(优化:解变量的依赖关系, 也叫局部枚举)
东北师大附中

例2 谁是第几名
?在某次数学竞赛中, A、B、C、D、E五名学生被取 为前五名。请据下列说法判断出他们的具体名次, 即谁是第几名? ?条件1: 你如果认为A, B, C, D, E 就是这些人的 第一至第五名的名次排列, 便大错。因为: 没猜对任何一个优胜者的名次。 也没猜对任何一对名次相邻的学生。 ?条件2: 你如果按D, A , E , C , B 来排列五人 名次的话, 其结果是: 说对了其中两个人的名次。 还猜中了两对名次相邻的学生的名次顺序。
东北师大附中

?分析:本题是一个逻辑判断题,一般的逻 辑判断题或推理题都采用枚举法进行解决。 5个人的名次分别可以有5!=120种排列可 能,因为120比较小,因此我们对每种情况 进行枚举,然后根据条件判断哪些符合问 题的要求。 ?根据已知条件, A<>1,B<>2,C<>3,D<>4,E<>5,因此排除了一 种可能性,只有4!=24种情况了。(优化: 减少了解变量的取值范围)
东北师大附中

例3 古纸残篇
在一位数学家的藏书中夹有一张古旧的纸片。纸片上的字 早已模糊不清了, 只留下曾经写过字的痕迹, 依稀还可以 看出它是一个乘法算式, 如图7所示。这个算式上原来的 数字是什么呢?夹着这张纸片的书页上,“素数”两个字 被醒目的划了出来。难道说, 这个算式与素数有什么关系 吗?有人对此作了深入的研究, 果然发现这个算式中的每 一个数字都是素数, 而且这样的算式是唯一的。请你也研 究一番, 并把这个算式写出来。 * * * × * * ---------* * * * * * * * ---------* * * * *
东北师大附中

?分析:实际上,只要知道乘数和被乘 数就可以写出乘法算式,所以我们可 以枚举乘数与被乘数的每一位。然后 再判断是不是满足条件即可。计算量 是45=1024,对于计算机来说,计算量 非常小。

东北师大附中

例4 时钟问题(IOI94-4)

九种时钟状态

东北师大附中

? 输入数据: 读9个数码,这些数码给出了9个时钟时针的初始位置。数 码与时刻的对应关系为: 0——12点 1——3点 2——6点 3——9点 图中的

例子对应下列输入数据: 330 222 212 ? 输出数据: 输出一个最短的移动序列(数字序列),该序列要使所 有的时钟指针指向12点,若有等价的多个解,仅需给出其 中一个. 东北师大附中

?在我们的例子中,相应的OUTPUT.TXT的内 容为: 5849 ?输入输出示例: INPUT.TXT OUTPUT.TXT 330 5489 222 212 具体的移动方案如图所示。
东北师大附中

? 我们分析一下表示时钟时针初始位置的数码j(0≦j≦3)与时刻的对 应关系:
? ? ? ? 0——12点 1——3点 2——6点 3——9点

? 移动方案选取与顺序无关。样例中,最佳移动序列为5849,同样4589 序列也可达到目标。因此,求解过程中可以直接选取序列中从小至大 排列的移动序列即可。(优化:用顺序减少解集的元素)
? 每移动一次,时针将顺时针旋转90度。由此我们可以得出: 对于任意一个时钟i(1≦i≦9)来说,从初始位置j出发至少需要Ci= (4-j) % 4次操作,才能使得时针指向12点。而对每种移动方法要 么不采用,要么采用1次、2次或3次,因为操作四次以后,时钟将重 复以前状态。因此,9种旋转方案最多产生49个状态。(优化:用次 数减少解集的元素)
东北师大附中

?设 pi表示第i种旋转方法的使用次数 (0≦pi≦3,1≦i≦9)。 则可能的解的集合为{(P1,P2,……, P9)},该集合共含49个状态。从题目 的示意图中,我们可以分析出9个时钟 分别被哪些方法所控制,见下表:

东北师大附中

建立时钟控制表
时钟号 1 2 3 4 5 控制时钟方案 1、2、4 1、2、3、5 2、3、6 1、4、5、7 1、3、5、7、9 检验条件 C1=(P1+P2+P4) % 4 C2=(P1+P2+P3+P5) % 4 C3=(P2+P3+P6) % 4 C4=(P1+P4+P5+P7) % 4 C5=(P1+P3+P5+P7+P9) % 4

6
7 8 9

3、5、6、9
4、7、8 5、7、8、9 6、8、9

C6=(P3+P5+P6+P9) % 4
C7=(P4+P7+P8) % 4 C8=(P5+P7+P8+P9) % 4 C9=(P6+P8+P9) % 4
东北师大附中

设计算法
因此我们可以设计如下枚举算法(伪代码):

for p1 <- 0 for p2 <... ... for p9

to 3 do 0 to 3 do ... <- 0 to 3 do

if c1满足时钟1 and c2满足时钟2 and ... and c9满足时钟9 then 打印解路径; 显然,上述枚举算法枚举了所有49=262144个状态, 运算量和运行时间颇大。
东北师大附中

优化
?P4~P9可直接由P1,P2,P3求出 P4=order(C1-P1-P2); P5=order(C2-P1-P2-P3); P6=order(C3-P2-P3); P7=order(C4-P1-P4-P5); P9=order(C6-P3-P5-P6); P8=order(C8-P5-P7-P9);
order(c) ? ?c mod 4 ?(c ? N ? 4) mod 4 ? c?0 c?0
东北师大附中

结果
?然后将P1,P2,…,P9代入下述三个检验 条件 C5=(P1+P3+P5+P7+P9) mod 4 C7=(P4+P7+P8) mod 4 C9=(P6+P8+P9) mod 4 ?上述局部枚举的方法(枚举状态数为43个) 比较全部枚举的方法(枚举状态数为49个) 来说,由于大幅度削减了枚举量,减少运 算次数,因此其时效显著改善

(优化:依 赖关系)
东北师大附中

例5 最佳游览线路 (NOI94)
?某旅游区的街道成网格状。其中东西向的街道都 是旅游街,南北向的街道都是林荫道。由于游客 众多,旅游街被规定为单行道,游客在旅游街上 只能从西向东走,在林阴道上则既可从南向北走, 也可以从北向南走。 ?阿龙想到这个旅游区游玩。他的好友阿福给了他 一些建议,用分值表示所有旅游街相邻两个路口 之间的街道值得游览的程度,分值时从-100到100 的整数,所有林阴道不打分。所有分值不可能全 是负分。下图是被打过分的某旅游区的街道图。 ?阿龙可以从任一个路口开始游览,在任一个路口 结束游览。请写一个程序,帮助阿龙找一条最佳 的游览线路,使得这条线路的所有分值总和最大。
东北师大附中

图11某旅游区街道示例图

东北师大附中

? 输入数据: 输入文件是INPUT.TXT。文件的第一行是两个整数M和N,之间用一个 空格符隔开,M表示有多少条旅游街(1≦M≦100),N表示有多少条 林阴道(1≦M≦20001)。接下来的M行依次给出了由北向南每条旅游 街的分值信息。每行有N-1个整数,依次表示了自西向东旅游街每一 小段的分值。同一行相邻两个数之间用一个空格隔开。

? 输出数据: 输出文件是OUTPUT.TXT。文件只有一行,是一个整数,表示你的程 序找到的最佳游览线路的总分值。
? 输入输出示例: INPUT.TXT 3 6 -50 –47 36 –30 –23 17 –19 –34 –13 –8 -42 –3 –43 34 –45

OUTPUT.TXT 84

东北师大附中

?INPUT.TXT 3 6 -50 –47 36 –30 –23 17 –19 –34 –13 –8 -42 –3 –43 34 –45

OUTPUT.TXT 84

东北师大附中

? 分析:设Lij为第I条旅游街上自西向东第J段的 分值(1 ≦ I ≦ M,1 ≦ J ≦ N – 1)。例 如样例中L12=17,L23=-34,L34=34。 ? 我们将网格状的旅游区街道以林荫道为界分为N – 1个段,每一段由M条旅游街的对应段成,即 第J段成为{L1J,L2J,……,LMJ}(1≦ J ≦ N – 1)。由于游览方向规定横向自西向东,纵向 即可沿林阴道由南向北,亦可由北向南,而横行 的街段有分值,纵行无分值,因此最佳游览路现 必须具备如下三个特征:
? ? ? 来自若干个连续的段,每一个段中取一个分值; 每一个分值是所在段中最大的; 起点段和终点段任意,但途经段的分值和最大。
东北师大附中

?设Li为第I个段中的分值最大的段。即Li=Max{L1I, L2I,……,LMI}(1≦I≦N – 1)。例如对于样 例数据: L1=Max(-50,17,-42)=17; L2=Max(-47,-19,-3)=-3; L3=Max(36,-34,-43)=36; L4=Max(-30,-13,34)=34; L5=Max(-23,-8,-45)=-8; ?有了以上的基础,我们便可以通过图示描述解题 过程,见求解

过程示例图 ?
东北师大附中

?我们把将段设为顶点,所在段的最大 分值设为顶点的权,各顶点按自西向 东的顺序相连,组成一条游览路线。 显然,如果确定西端为起点、东段为 终点,则这条游览路线的总分值最大。

图12 求解过程示例图
东北师大附中

?我们把将段设为顶点,所在段的最大分值设为顶 点的权,各顶点按自西向东的顺序相连,组成一 条游览路线。显然,如果确定西端为起点、东段 为终点,则这条游览路线的总分值最大。 ?问题是某些段的最大分值可能是负值,而最优游 览路线的起点和终点任意,在这种情况下,上述 游览路线就不一定最佳了。因此,我们只能枚举 这条游览路线的所有可能的子路线,从中找出一 条子路线I?I+1?……?J(1 ≦ I<J ≦ N – 1),使得经过顶点的权和LI+LI+1+……+LJ最大。

东北师大附中

设Best为最佳游览路线的总分值,初始时为0; Sum为当前游览路线的总分值。 ?我们可以得到如下算法(伪代码):

Best <- 0; Sum <- 0; for I <- 1 to N – 2 do for J <- I + 1 to N – 1 do begin Sum <- LI + …… + LJ; if Sum > Best then Best := Sum; end
东北师大附中

优化
?显然,这个算法的时间复杂度为O(N2)。 而N在1~20001之间,时间复杂度比较高。 于是,我们必须对这个算法进行优化。 ?仍然从顶点1开始枚举最优路线。若当前子 路线延伸至顶点I时发现总分值Sum≦0,则 应放弃当前子路线。因为无论LI+1为何值, 当前子路线延伸至顶点I+1后的总分值不会 大于LI+1。因此应该从顶点I+1开始重新考 虑新的一条子路线。通过这种优化,可以 使得算法的时间复杂度降到了O(N)。
东北师大附中

?优化后的算法描述如下:

Best <- 0; Sum <- 0; for I <- 1 to N – 1 do begin Sum <- Sum + LI; if Sum > Best then Best <- Sum; if Sum < 0 then Sum <- 0; end
东北师大附中

3 小结
?枚举方法是最简单的一种解题策略,也是 最容易想到的一种方法。利用枚举法解题 需要枚举出问题的解的所有可能状态,其 致命的弱点便在于枚举量太大,从而导致 算法效率十分低下。 ?因此,在利用枚举法解题时,尽可能地减 少枚举量,提高枚举效率。通过对问题的 分析,挖掘出问题的隐含条件,尽可能排 除那些明显不可能属于问题的解的状态, 就是一个行之有效的办法。
东北师大附中

4 二进制数的分类(课后练习)
?若将一个正整数转化为二进制数后,1的个 数多于0的个数的这类数称为A类数,否则 称为B类数。例如: (13)10=(1101)2, 13为A类数; (10)10=(1010)2 10为B类数; (24)10=(11000)2 24为B类数; ?程序要求:求出1~1000之中(包括1与 1000),全部A、B两类数的个数。

北师大附中

?分析:此题是一道统计类题目。解决 统计问题的一个常用方法是枚举法: 逐一枚举所有情况,同时进行统计, 枚举结束时,统计也完成,得到结果。 ?具体对本题而言,采用枚举法的正确 性与可行性是显然的,而本题的数据 规模又仅为1~1000,所以采用逐一枚 举方法进行统计的时间复杂度是完全 可以接受的。
东北师大附中

?实数矩阵由m行n列组成(1<=m,n<=100), 现给定实数矩阵,求其中心,若有多个 “中心”,给出任意一个“中心”即可。 中心(i,j)是使第i行上边元素(不包括第i 行)的总和与第i行下边元素(不包括第i行) 的总和之差的绝对值最小,而且第j列左边 元素(不包括第j列)的总和与第j列右边元 素(不包括第j列)的总和之差的绝对值最小。

模式识别的“中心”问题(课后练 习)

东北师大附中

?分析:求矩阵的中心,即确定矩阵中 心的行和列坐标,考虑到矩阵的对性, 行坐标和列坐标的求法是类同的。下 面是求矩阵中心行坐标的算法。 ?求行坐标采用枚举法,枚举出所有可 能的行坐标line,计算出line行上边 元素和与下边元素和之差的绝对值 difference,difference最小的行即 为中心所在行。
东北师大附中

枚举过程可以描述为(伪代码): min <- +∞; for line <- 1 to m do begin 求出line行上、下元素绝对值之差difference; if min>difference then begin min <- difference; 保存line作为矩阵中心所在行; end; end;

东北师大附中

留学生(课后练习)
?来自不同国家的四位留学生A,B,C,D在 一起交谈,他们只会中、英、法、日四 种语言中的2种,情况是, 没有人既会 日语又会法语;A会日语,但D不会,A和D 能互相交谈,B不会英语,但A和C交谈时 却要B当翻译,B,C,D三个想互相交谈, 但找不到共同的语言,只有一种语言3 人都会,编程确定A,B,C,D四位留学生 各会哪两种语言。
东北师大附中

?分析:将中、法、日、英四种语言分别定 义为CHN、FRH、JPN、ENG,则四种语言中取 两种共有(CHN,ENG), (CHN,FRH),(CHN,JPN),( ENG,FRH),( EN G,JPN),(FRH,JPN)六种组合,分别定义为1、 2、3、4、5、6。据已知,没有人既会日语 又会法语;因此,组合6不会出现;A 会日 语,所以A只可能等于3、5;D不会日语, 所以D只可能等于1、2、4;B不会英语,所 以B只可能等于2、3;见下表。如果我们对 A、B、C、D分别进行枚举,根据判定条件, 即可找到答案。
东北师大附中

(CHN,ENG) (CHN,FRH) (CHN,JPN) ( ENG,FRH) ( ENG,JPN) A B C D × × × × × × × ×

东北师大附中

爱因斯坦谜题 (课后练习)
? 一条街上有5栋房子,刷不同的漆,住不同国的人,他们喝不同的饮料,抽 不同的烟,养不同的宠物。 1、英国人住红

房子。 2、瑞典人养狗。 3、丹麦人喝茶。 4、绿房子在白房子左面隔壁。 5、绿房子主人喝咖啡。 6、抽PALL MALL烟的人养鸟。 7、黄房子主人抽DUNHILL烟。 8、中间的人喝牛奶。 9、挪威人住第一个。 10、抽BLENDS烟的人在养猫的隔壁。 11、养马的住抽DUNHILL烟的人隔壁。 12、抽BLUE MASTER的人喝啤酒。 13、德国人抽PRINCE烟。 14.挪威人住在蓝房子旁边 15、抽BLENDS烟的人的邻居喝水。 ? 问: 养鱼的是谁
东北师大附中


网站首页网站地图 站长统计
All rights reserved Powered by 海文库
copyright ©right 2010-2011。
文档资料库内容来自网络,如有侵犯请联系客服。zhit326@126.com