1、高中信息技术 全国青少年奥林匹克联赛教案 枚举法二枚举法课题：枚举法目标：知识目标：枚举算法的本质和应用能力目标：枚举算法的应用！重点：利用枚举算法解决实际问题难点：枚举算法的次数确定板书示意：1） 简单枚举（例7、例8、例9）2） 利用枚举解决逻辑判断问题（例10、例11）3） 枚举解决竞赛问题（例12、例13、例14）授课过程：所谓枚举法,指的是从可能的解集合中一一枚举各元素,用题目给定的检验条件判定哪些是无用的,哪些是有用的.能使命题成立,即为其解。一般思路： 对命题建立正确的数学模型； 根据命题确定的数学模型中各变量的变化范围（即可能解的范围）； 利用循环语句、条件判断语句逐步求解或证
2、明；枚举法的特点是算法简单，但有时运算量大。对于可能确定解的值域又一时找不到其他更好的算法时可以采用枚举法。例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);上例采用的就是枚举法。所谓枚举法，指的是从可能的解的集合中一一枚举各元素，用题目给定的检验条件判定哪些是无用的，哪些是有用的。能使命题成立的，即为解。从枚举法的
3、定义可以看出，枚举法本质上属于搜索。但与隐式图的搜索有所区别，在采用枚举法求解的问题时，必须满足两个条件：1 预先确定解的个数n；2 对每个解变量A1，A2，An的取值，其变化范围需预先确定A1X11，X1pAiXi1，XiqAnXn1，Xnk例7中的解变量有3个：A，B，C。其中A解变量值的可能取值范围A1，2，3B解变量值的可能取值范围B1，2，3C解变量值的可能取值范围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）在上述可能解集合中，满足题目
4、给定的检验条件的解元素，即为问题的解。如果我们无法预先确定解的个数或各解的值域，则不能用枚举，只能采用搜索等算法求解。由于回溯法在搜索每个可能解的枚举次数一般不止一次，因此，对于同样规模的问题，回溯算法要比枚举法时间复杂度稍高。例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:)
5、;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 巧妙填数 1 9 2 3 8 4 5 7 6 将19这九个数字填入九个空格中。每一横行的三个数字组成一个三位数。如果要使第二行的三位数是第一行的两倍, 第三行的三位数是第一行的三倍, 应怎样填数。如图6: 图6分析：本题目有9个格子，要求填数，如果不考虑问题给出的条件，
6、共有9！=362880种方案，在这些方案中符合问题条件的即为解。因此可以采用枚举法。但仔细分析问题，显然第一行的数不会超过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 10end;function mul(s:integer):longint;begin mul:=(s div 100) * (s div 10
7、 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*s1000 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)
8、; 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比较小
9、，因此我们对每种情况进行枚举，然后根据条件判断哪些符合问题的要求。根据已知条件，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 BeginABCDE没猜对一个人的名次 If (A=1) Or (B=2) Or (C=3) Or (D=4) Or (E=5) T
10、hen 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;
11、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）,(
12、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)ABCD程序如下：program EXAM11; type Language = (CHN,ENG,FRH,JPN); TNoSet= se
13、t 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
14、 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 Write(ch,:); for Lang := CHN to JPN do if Lang in NoP the
15、n 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 := No
16、A * 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 古纸残篇在一位数学
17、家的藏书中夹有一张古旧的纸片。纸片上的字早已模糊不清了, 只留下曾经写过字的痕迹, 依稀还可以看出它是一个乘法算式, 如图7所示。这个算式上原来的数字是什么呢？夹着这张纸片的书页上,“素数”两个字被醒目的划了出来。难道说, 这个算式与素数有什么关系吗？有人对此作了深入的研究, 果然发现这个算式中的每一个数字都是* * * * * * * * * * * * * * * *图7素数, 而且这样的算式是唯一的。请你也研究一番, 并把这个算式写出来。分析：实际上，只要知道乘数和被乘数就可以写出乘法算式，所以我们可以枚举乘数与被乘数的每一位。然后再判断是不是满足条件即可。计算量是45=1024，对于计
18、算机来说，计算量非常小。参考程序：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
19、:=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*SuB11000 Then Continue; If X*SuB21000 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 Con
20、tinue;满足其他数都是由质数构成 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个数字号与相应的受控制的时钟，这些时钟在图中以灰色标
21、出，其指针将顺时针旋转90度。输入数据：由输入文件INPUT.TXT读9个数码，这些数码给出了9个时钟时针的初始位置。数码与时刻的对应关系为：012点13点26点39点图2-11中的例子对应下列输入数据：330222212输出数据：将一个最短的移动序列（数字序列）写入输出文件OUTPUT.TXT中，该序列要使所有的时钟指针指向12点，若有等价的多个解，仅需给出其中一个。在我们的例子中，相应的OUTPUT.TXT的内容为：5849输入输出示例：INPUT.TXTOUTPUT.TXT3302222125489具体的移动方案如图10所示。图10 示例移动方案分析：首先，我们分析一下表示时钟时针初始位
22、置的数码j（0j3）与时刻的对应关系：012点13点26点39点每移动一次，时针将顺时针旋转90度。由此我们可以得出：对于任意一个时钟i（1i9）来说，从初始位置j出发至少需要Ci=（4-j） mod 4次操作，才能使得时针指向12点。而对每种移动方法要么不采用，要么采用1次、2次或3次，因为操作四次以后，时钟将重复以前状态。因此，9种旋转方案最多产生49个状态。移动方案选取与顺序无关。样例中，最佳移动序列为5849，同样4589序列也可达到目标。因此，求解过程中可以直接选取序列中从小至大排列的移动序列即可。设 pi表示第i种旋转方法的使用次数（0pi3，1i9）。则可能的解的集合为P1，P2
23、，P9，该集合共含49个状态。从图2.11中，我们可以分析出9个时钟分别被哪些方法所控制，见下表： 时钟号控制时钟方案检验条件11、2、4C1=(P1+P2+P4) mod 421、2、3、5C2=(P1+P2+P3+P5) mod 432、3、6C3=(P2+P3+P6) mod 441、4、5、7C4=(P1+P4+P5+P7) mod 451、3、5、7、9C5=(P1+P3+P5+P7+P9) mod 463、5、6、9C6=(P3+P5+P6+P9) mod 474、7、8C7=(P4+P7+P8) mod 485、7、8、9C8=(P5+P7+P8+P9) mod 496、8、9C
24、9=(P6+P8+P9) mod 4因此我们可以设计如下枚举算法：for p1:=0 to 3 do for p2:=0 to 3 do . . . 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
25、-P2-P3);P7=order(C4-P1-P4-P5);P8=order(C8-P5-PP9);P9=order(C6-P3-P5-P6);其中得出其余P4P9的相应状态值。然后将P1，P2，P9代入下述三个检验条件C5=(P1+P3+P5+P7+P9) mod 4C7=(P4+P7+P8) mod 4C9=(P6+P8+P9) mod 4一一枚举，以求得确切解。由此可见，上述局部枚举的方法（枚举状态数为43个）比较全部枚举的方法（枚举状态数为49个）来说，由于大幅度削减了枚举量，减少运算次数，因此其时效显著改善，是一种优化了的算法。程序如下：program IOI94_4; const
26、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
27、 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);
28、 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 (
