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*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); 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*SuB11000 Then Continue; If X*SuB21000 Then Continue; If X*(SuB1*10+SuB2) 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.