2019-2020年高中信息技术 全国青少年奥林匹克联赛教案 枚举法二.doc

2019-2020 年高中信息技术 全国青少年奥林匹克联赛教案 枚举法二 课题：枚举法 目标： 知识目标：枚举算法的本质和应用 能力目标：枚举算法的应用！ 重点：利用枚举算法解决实际问题 难点：枚举算法的次数确定 板书示意： 1） 简单枚举（例 7、例 8、例 9） 2） 利用枚举解决逻辑判断问题（例 10、例 11） 3） 枚举解决竞赛问题（例 12、例 13、例 14） 授课过程： 所谓枚举法,指的是从可能的解集合中一一枚举各元素,用题目给定的检验条件判定哪 些是无用的,哪些是有用的.能使命题成立,即为其解。一般思路： 对命题建立正确的数学模型； 根据命题确定的数学模型中各变量的变化范围（即可能解的范围） ； 利用循环语句、条件判断语句逐步求解或证明； 枚举法的特点是算法简单，但有时运算量大。对于可能确定解的值域又一时找不到其他更 好的算法时可以采用枚举法。 例 7：求满足表达式 A+B=C 的所有整数解，其中 A，B，C 为 13 之间的整数。 分析：本题非常简单，即枚举所有情况，符合表达式即可。算法如下： 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); 上例采用的就是枚举法。所谓枚举法，指的是从可能的解的集合中一一枚举各元素， 用题目给定的检验条件判定哪些是无用的，哪些是有用的。能使命题成立的，即为解。 从枚举法的定义可以看出，枚举法本质上属于搜索。但与隐式图的搜索有所区别，在 采用枚举法求解的问题时，必须满足两个条件： 预先确定解的个数 n； 对每个解变量 A1，A2，An 的取值，其变化范围需预先确定 A1X 11，X 1p AiX i1，X iq AnX n1，X nk 例 7 中的解变量有 3 个：A，B，C。其中 A 解变量值的可能取值范围 A1，2，3 B 解变量值的可能取值范围 B1，2，3 C 解变量值的可能取值范围 C1，2，3 则问题的可能解有 27 个 （A，B，C）（1，1，1） ， （1，1，2） ， （1，1，3） ， （1，2，1） ， （1，2，2） ， （1，2，3） ， （3，3，1） ， （3，3，2） ， （3，3，3） 在上述可能解集合中，满足题目给定的检验条件的解元素，即为问题的解。 如果我们无法预先确定解的个数或各解的值域，则不能用枚举，只能采用搜索等算法 求解。由于回溯法在搜索每个可能解的枚举次数一般不止一次，因此，对于同样规模的问 题，回溯算法要比枚举法时间复杂度稍高。 例 8 给定一个二元一次方程 aX+bY=c。从键盘输入 a,b,c 的数值，求 X 在0，100， Y 在0，100范围内的所有整数解。 分析：要求方程的在一个范围内的解，只要对这个范围内的所有整数点进行枚举，看 这些点是否满足方程即可。参考程序： program exam8; var a,b,c:integer; x,y:integer; begin write(Input a,b,c:);readln(a,b,c); for x:=0 to 100 do for y:=0 to 100 do if a*x+b*y=c then writeln(x, ,y); end. 从上例可以看出，所谓枚举法,指的是从可能的解集合中一一枚举各元素,用题目给定 的检验条件判定哪些是无用的,哪些是有用的.能使命题成立,即为其解。 例 9 巧妙填数 将 19 这九个数字填入九个空格中。每一横行的三个数字组成一个三位数。如果要使 第二行的三位数是第一行的两倍, 第三行的三位数是第一行的三倍, 应怎样填数。如图 6: 图 6 分析：本题目有 9 个格子，要求填数，如果不考虑问题给出的条件，共有 9！=362880 种方 案，在这些方案中符合问题条件的即为解。因此可以采用枚举法。 1 9 2 3 8 4 5 7 6 但仔细分析问题，显然第一行的数不会超过 400，实际上只要确定第一行的数就可以根据 条件算出其他两行的数了。这样仅需枚举 400 次。因此设计参考程序： program exam9; var i,j,k,s:integer; function sum(s:integer):integer; begin sum:=s div 100 + s div 10 mod 10 + s mod 10 end; function mul(s:integer):longint; begin mul:=(s div 100) * (s div 10 mod 10) * (s mod 10) end; begin for i:=1 to 3 do for j:=1 to 9 do if ji then for k:=1 to 9 do if (kj) and (ki) then begin s := i*100 + j*10 +k; 求第一行数 if 3*s<1000 then if (sum(s)+sum(2*s)+sum(3*s)=45) and (mul(s)*mul(2*s)*mul(3*s)=362880) then 满足条件，并数字都由 19 组成 begin writeln(s); writeln(2*s); writeln(3*s); writeln; end; end; end. 例 10 在某次数学竞赛中, A、B、C、D、E 五名学生被取为前五名。请据下列说法判断 出他们的具体名次, 即谁是第几名？ 条件 1: 你如果认为 A, B, C, D, E 就是这些人的第一至第五名的名次排列 , 便大错。因 为: 没猜对任何一个优胜者的名次。 也没猜对任何一对名次相邻的学生。 条件 2: 你如果按 D, A , E , C , B 来排列五人名次的话, 其结果是: 说对了其中两个人的名次。 还猜中了两对名次相邻的学生的名次顺序。 分析：本题是一个逻辑判断题，一般的逻辑判断题都采用枚举法进行解决。5 个人的 名次分别可以有 5！=120 种排列可能，因为 120 比较小，因此我们对每种情况进行枚 举，然后根据条件判断哪些符合问题的要求。 根据已知条件，A1,B2,C3,D4,E5,因此排除了一种可能性，只有 4！=24 种 情况了。 参考程序： Program Exam10; Var A,B,C,D,E :Integer; Cr :Array1.5 Of Char; Begin For A:=1 To 5 Do For B:=1 To 5 Do For C:=1 To 5 Do For D:=1 To 5 Do For E:=1 To 5 Do Begin ABCDE 没猜对一个人的名次 If (A=1) Or (B=2) Or (C=3) Or (D=4) Or (E=5) Then Continue; If A,B,C,D,E1,2,3,4,5 Then Continue;他们名次互不重复 DAECB 猜对了两个人的名次 If Ord(A=2)+Ord(B=5)+Ord(C=4)+Ord(D=1)+Ord(E=3)2 Then Continue; ABCDE 没猜对一对相邻名次 If (B=A+1) Or (C=B+1) Or (D=C+1) Or (E=D+1) Then Continue; DAECB 猜对了两对相邻人名次 If Ord(A=D+1)+Ord(E=A+1)+Ord(C=E+1)+Ord(B=C+1)2 Then Continue; CrA:=A;CrB:=B;CrC:=C; CrD:=D;CrE:=E; WRITELN(CR1, ,CR2, ,CR3, ,CR4, ,CR5); End; End. 例 11：来自不同国家的四位留学生 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),( ENG,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 程序如下： program EXAM11; type Language = (CHN,ENG,FRH,JPN); TNoSet= set of Language; const No: array 1 . 5 of TNoSet= (CHN,ENG, CHN,FRH, CHN,JPN, ENG,FRH, ENG,JPN); var A, B, C, D: 1 . 5; Can1, Can2, Can3, Can4: Boolean; function Might(Lang: Language): Boolean; var Bool: Boolean; begin Bool:=false; if NoA * NoA * NoC = Lang then Bool := True; if NoA * NoB * NoD = Lang then Bool := True; if NoA * NoC * NoD = Lang then Bool := True; if NoB * NoC * NoD = Lang then Bool := True; Might := Bool end; procedure Print(A, B, C, D: Integer); procedure Show(P: Integer; Ch: Char); var I: Integer; Lang: Language; begin * * * * * * * * * * * * * * * * * * 图 7 Write(ch,:); for Lang := CHN to JPN do if Lang in NoP then case Lang of CHN: Write(CHN:5); FRH: Write(FRH:5); JPN: Write(JPN:5); ENG: Write(ENG:5); end; Writeln; end; begin Show(A, A); Show(B, B); Show(C, C); Show(D, D); end; begin for A := 3 to 5 do if A 4 then for B := 2 to 3 do for C := 1 to 5 do for D := 1 to 4 do if D 3 then begin A 和 D 能互相交谈 Can1 := NoA * NoD ; A 和 C 交谈时却要 B 当翻译 Can2 := (NoA * NoC = ) and (NoA * NoB ) and (NoB * NoC ); B,C,D 三个想互相交谈,但找不到共同的语言 Can3 := NoB * NoC * NoD = ; 只有一种语言 3 人都会 Can4 := Ord(Might(CHN) + Ord(Might(ENG) + Ord(Might(FRH) + Ord(Might(JPN) = 1; if Can1 and Can2 and Can3 and Can4 then Print(A,B,C,D); end; end. 例 12 古纸残篇 在一位数学家的藏书中夹有一张古旧的纸片。纸片上的字早已模糊不清了, 只留下曾经写 过字的痕迹, 依稀还可以看出它是一个乘法算式, 如图 7 所示。这个算式上原来的数字是 什么呢？夹着这张纸片的书页上,“素数”两个字被醒目的划了出来。难道说, 这个算式与 素数有什么关系吗？有人对此作了深入的研究, 果然发现这个算 式中的每一个数字都是素数, 而且这样的算式是唯一的。请你也 研究一番, 并把这个算式写出来。 分析：实际上，只要知道乘数和被乘数就可以写出乘法算式，所以我们可以枚举乘数与被 乘数的每一位。然后再判断是不是满足条件即可。计算量是 45=1024，对于计算机来说， 计算量非常小。 参考程序： Program Exam12; Const Su : Array1.4 Of Longint=(2,3,5,7); Var A1,A2,A3,B1,B2,X,Y,S :Longint; Function Kx(S:Longint):Boolean;判断一个数 是不是都是由素数组成 Begin Kx:=True; While S0 Do Begin If Not(S Mod 10) In 2,3,5,7) Then Begin Kx:=False; Exit; End; S:=S Div 10; End; End; Begin For A1:=1 To 4 Do For A2:=1 To 4 Do For A3:=1 To 4 Do For B1:=1 To 4 Do For B2:=1 To 4 Do Begin X:=SuA1*100+SuA2*10+SuA3;X 为被乘数 If X*SuB1<1000 Then Continue; If X*SuB2<1000 Then Continue; If X*(SuB1*10+SuB2)<10000 Then Continue; 它们分别是两个四位数，一个五位数 If (Kx(X*SuB1)=False) Or (Kx(X*SuB2)=False) Or (Kx(X*(SuB1*10+SuB2)=False) Then Continue; 满足其他数都是由质数构成 Writeln( ,SuA1,SuA2,SuA3); Writeln(* ,SuB1,SuB2); Writeln(-); Writeln( ,X*SuB2); Writeln( ,X*SuB1); Writeln(-); Writeln( ,X*(SuB1*10+SuB2); End; End. 例 13：时钟问题（IOI94-4） 在图 8 所示的 3*3 矩阵中有 9 个时钟，我们的目标是旋转时钟指针，使所有时钟的指 针都指向 12 点。允许旋转时钟指针的方法有 9 种，每一种移动用一个数字号 （1，2，9）表示。图 2-11 示出 9 个数字号与相应的受控制的时钟，这些时钟在图中 以灰色标出，其指针将顺时针旋转 90 度。 输入数据： 由输入文件 INPUT.TXT 读 9 个数码，这些数码给出了 9 个时钟时针的初始位置。数码 与时刻的对应关系为： 012 点 13 点 26 点 39 点 图 2-11 中的例子对应下列输入数据： 330 222 212 输出数据： 将一个最短的移动序列（数字序列）写入输出文件 OUTPUT.TXT 中，该序列要使所有的 时钟指针指向 12 点，若有等价的多个解，仅需给出其中一个。在我们的例子中，相应的 OUTPUT.TXT 的内容为： 5849 图 8 九种时钟状态 图 9 九种被控制方式 输入输出示例： INPUT.TXT OUTPUT.TXT 330 222 212 5489 具体的移动方案如图 10 所示。 分析： 首先，我们分析一下表示时钟时针初始位置的数码 j（0j3）与时刻的对应关系： 012 点 13 点 26 点 39 点 每移动一次，时针将顺时针旋转 90 度。由此我们可以得出： 对于任意一个时钟 i（1i9）来说，从初始位置 j 出发至少需要 Ci=（4-j） mod 4 次操作，才能使得时针指向 12 点。而对每种移动方法要么不采用，要么采用 1 次、2 次或 3 次，因为操作四次以后，时钟将重复以前状态。因此，9 种旋转方案最多产生 49个状态。 移动方案选取与顺序无关。样例中，最佳移动序列为 5849，同样 4589 序列也可达到目 标。因此，求解过程中可以直接选取序列中从小至大排列的移动序列即可。 设 p i表示第 i 种旋转方法的使用次数（0p i3，1i9） 。 则可能的解的集合为P 1，P 2，P 9，该集合共含 49个状态。从图 2.11 中，我们 可以分析出 9 个时钟分别被哪些方法所控制，见下表： 时钟号 控制时钟方案 检验条件 1 1、2、4 C1=(P1+P2+P4) mod 4 2 1、2、3、5 C2=(P1+P2+P3+P5) mod 4 3 2、3、6 C3=(P2+P3+P6) mod 4 4 1、4、5、7 C4=(P1+P4+P5+P7) mod 4 5 1、3、5、7、9 C5=(P1+P3+P5+P7+P9) mod 4 6 3、5、6、9 C6=(P3+P5+P6+P9) mod 4 7 4、7、8 C7=(P4+P7+P8) mod 4 8 5、7、8、9 C8=(P5+P7+P8+P9) mod 4 9 6、8、9 C9=(P6+P8+P9) mod 4 因此我们可以设计如下枚举算法： for p1:=0 to 3 do for p2:=0 to 3 do 图 10 示例移动方案 . . . for p9:=0 to 3 do if c1 满足时钟 1 and c2 满足时钟 2 and . and c9 满足时钟 9 then 打印解路径； 显然，上述枚举算法枚举了所有 49=262144 个状态，运算量和运行时间颇大。我们可以 采取缩小可能解范围的局部枚举法，仅枚举第 1、2、3 种旋转方法可能取的 43个状态，根 据这三种旋转方法的当前状态值，由下述公式 P4=order(C1-P1-P2); P5=order(C2-P1-P2-P3); P6=order(C3-P2-P3); P7=order(C4-P1-P4-P5); P8=order(C8-P5-PP9); P9=order(C6-P3-P5-P6); 其中 04mod)()cNcorde 得出其余 P4P9的相应状态值。然后将 P1，P 2，P 9代入下述三个检验条件 C5=(P1+P3+P5+P7+P9) mod 4 C7=(P4+P7+P8) mod 4 C9=(P6+P8+P9) mod 4 一一枚举，以求得确切解。 由此可见，上述局部枚举的方法（枚举状态数为 43个）比较全部枚举的方法（枚举状 态数为 49个）来说，由于大幅度削减了枚举量，减少运算次数，因此其时效显著改善，是 一种优化了的算法。 程序如下： program IOI94_4; const Inp = input.txt; Outp = output.txt; var Clock, Map: array 1 . 3, 1 . 3 of Integer; Clock：第(I+2)mod 3)*3+J 个时钟从初始时间到 12 点的最少移动次数 Map:最短移动序列中，数字（I+2）mod 3）*3+J 的次数 procedure Init; var I, J: Integer; begin Assign(Input, Inp); Reset(Input); for I := 1 to 3 do 读入 9 个时钟指针的初始位置，求出每个时钟从初始到 12 点的最少移动次数 for J := 1 to 3 do begin Read(ClockI, J); ClockI, J := (4 - ClockI, J) mod 4; end; Close(Input); end; function Order(K: Integer): Integer; var c: Integer; begin c:=k; while c4 then dec(c,4); Order := k; end; procedure Main; 计算和输出最短移动序列 var I, J, K: Integer; begin 枚举最短移动序列中数字 1、2、3 的个数可能取的 43种状态 Assign(Output, Outp); Rewrite(Output); for Map1, 1 := 0 to 3 do for Map1, 2 := 0 to 3 do for Map1, 3 := 0 to 3 do begin Map2,1:=Order(Clock1,1-Map1,1-Map1,2); Map2,3:=Order(Clock1,3-Map1,2-Map1,3); Map2,2:=Order(Clock1,2-Map1,1-Map1,2-Map1, 3); Map3,1:=Order(Clock2,1-Map1,1-Map2,1-Map2, 2); Map3,3:=Order(Clock2,3-Map1,3-Map2,2-Map2, 3); Map3,2:=Order(Clock3,2-Map3,1-Map3,3-Map2, 2); 根据数字 1、2、3 个数的当前值，得出数字 49 的个数 if (Map2,1+Map3,1+Map3,2)mod 4=Clock3,1) and (Map2,3+Map3,2+Map3,3)mod 4=Clock3, 3)and (Map2,2+Map1,1+Map1,3+Map3,1+Map3, 3) mod 4 = Clock2, 2) then begin 若数字 49 的个数满足检验条件，则输出方案 for I := 1 to 3 do for J := 1 to 3 do for K := 1 to MapI, J do Write(I - 1) * 3 + J); Exit; 找到一个解后退出 end; end; Writeln(No Answer !); Close(Output); end; begin Init; Main; end. 在上例中，由于事先能够排除那些明显不属于解集的元素，使得算法效率非常高。而 减少重复运算、力求提前计算所需数据、使用恰当的数据结构进行算法优化等方法也是优 化枚举算法的常用手段。 例 14：最佳游览线路 （NOI94） 某旅游区的街道成网格状（图 2.13） 。其中东西向的街道都是旅游街，南北向的街道都 是林荫道。由于游客众多，旅游街被规定为单行道，游客在旅游街上只能从西向东走，在 林阴道上则既可从南向北走，也可以从北向南走。 阿龙想到这个旅游区游玩。他的好友阿福给了他一些建议，用分值表示所有旅游街相 邻两个路口之间的街道值得游览的程度，分值时从-100 到 100 的整数，所有林阴道不打分。 所有分值不可能全是负分。 例如图 11 是被打过分的某旅游区的街道图： 阿龙可以从任一个路口开始游览，在任一个路口结束游览。请你写一个程序，帮助阿 龙找一条最佳的游览线路，使得这条线路的所有分值总和最大。 输入数据： 输入文件是 INPUT.TXT。文件的第一行是两个整数 M 和 N，之间用一个空格符隔开，M 表示有多少条旅游街（1M100） ，N 表示有多少条林阴道（1Mxx1） 。接下来的 M 行 依次给出了由北向南每条旅游街的分值信息。每行有 N-1 个整数，依次表示了自西向东旅 游街每一小段的分值。同一行相邻两个数之间用一个空格隔开。 输出数据： 输出文件是 OUTPUT.TXT。文件只有一行，是一个整数，表示你的程序找到的最佳游览 线路的总分值。 输入输出示例： 图 11 某旅游区街道示例图 INPUT.TXT OUTPUT.TXT 3 6 -50 47 36 30 23 17 19 34 13 8 -42 3 43 34 45 84 分析： 设 Lij为第 I 条旅游街上自西向东第 J 段的分值（1 I M，1 J N 1） 。 例如样例中 L12=17，L 23=-34，L 34=34。 我们将网格状的旅游区街道以林荫道为界分为 N 1 个段，每一段由 M 条旅游街的对 应段成，即第 J 段成为L 1J，L 2J，L MJ（1 J N 1） 。由于游览方向规定横向 自西向东，纵向即可沿林阴道由南向北，亦可由北向南，而横行的街段有分值，纵行无分 值，因此最佳游览路现必须具备如下三个特征： 来自若干个连续的段，每一个段中取一个分值； 每一个分值是所在段中最大的； 起点段和终点段任意，但途经段的分值和最大。 设 Li为第 I 个段中的分值最大的段。即 Li=MaxL1I，L 2I，L MI（1IN 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。 我们把将段设为顶点，所在段的最大分值设为顶点的权，各顶点按自西向东的顺序相 连，组成一条游览路线。显然，如果确定西端为起点、东段为终点，则这条游览路线的总 分值最大。 问题是某些段的最大分值可能是负值，而最优游览路线的起点和终点任意，在这种情 况下，上述游览路线就不一定最佳了。因此，我们只能枚举这条游览路线的所有可能的子 路线，从中找出一条子路线 II+1J（1 I Best then Best := Sum; end 显然，这个算法的时间复杂度为 O（N 2） 。而 N 在 1xx1 之间，时间复杂度比较高。于 是，我们必须对这个算法进行优化。 仍然从顶点 1 开始枚举最优路线。若当前子路线延伸至顶点 I 时发现总分值 Sum0， 则应放弃当前子路线。因为无论 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 ScoreJ then ScoreJ := K; end; Close(Input); end; procedure Out; begin Assign(Output, Outp); Rewrite(Output); Writeln(Best); Close(Output); end; procedure Main; var I: Integer; Sum: Longint; 当前游览路线的总分值 begin 最佳游览路线的总分值和当前游览路线的总分值初始化 Best := 0; Sum := 0; for I := 1 to N - 1 do begin 顺序枚举游览路线的总分值 Inc(Sum, ScoreI); 统计当前游览路线的总分值 if Sum > Best then Best := Sum; 若当前最佳，则记下 if Sum < 0 then Sum := 0; 若总分值<0，则考虑一条新路线 end; end; begin Init; 输入数据 Main; 主过程 Out; 输出 end.