《高中信息技术全国青少年奥林匹克联赛教案枚举法二》由会员分享，可在线阅读，更多相关《高中信息技术全国青少年奥林匹克联赛教案枚举法二（15页珍藏版）》请在金锄头文库上搜索。
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、以看出，枚举法本质上属于搜索。但与隐式图的搜索有所区别，在采用枚举法求解的问题时，必须满足两个条件：预先确定解的个数n；对每个解变量A1，A2， An 的取值，其变化范围需预先确定A1X11， X1p AiXi1， Xiq 学习必备欢迎下载AnXn1， Xnk 例 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，
4、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
5、: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: 图 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
7、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*s1000 then if (sum(s)+sum(2*s)+sum(3*s)=45) and (mul(s)*mul(2*s)*
8、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 来排列五人名次的话, 其结果是 : 说对了
9、其中两个人的名次。还猜中了两对名次相邻的学生的名次顺序。分析：本题是一个逻辑判断题，一般的逻辑判断题都采用枚举法进行解决。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
10、 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 (
11、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交
12、谈时却要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；见下
13、表。如果我们对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, C
14、an3, 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; pr
15、ocedure Print(A, B, C, D: Integer); procedure Show(P: Integer; Ch: Char); var I: Integer; Lang: Language; begin Write(ch,:); 学习必备欢迎下载* * * * * * * * * * * * * * * * * *图 7 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(E
16、NG: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); en
