《高中信息技术 全国青少年奥林匹克联赛教案 枚举法二》由会员分享，可在线阅读，更多相关《高中信息技术 全国青少年奥林匹克联赛教案 枚举法二（15页珍藏版）》请在金锄头文库上搜索。
1、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 2 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，
4、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范围内的所有整数解。 分析：要求方程的在一个范围内的解，只要对这个范围内的所有整数点进行枚举，看 这些点是否满足方程即可。参考程序：
5、 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: 图 6 分析：本题目有 9 个格子，要求填数，如果不考虑问题给出的条件，共有 9！=362880 种方 案，在这些方案中符合问题条件的即为解。因此可以采用枚举法。 1 9 2 3 8 4 5 7 6 3 但仔细分析问题，显然第一行的数不会超过 400，实际上只要确定第一行的数就可以根据 条件算出其他两行的数了。这样仅需枚举 400 次。因此设计参考程序： program exam9; var i,j,k,s:integer; function sum(s:integer):integer; begin sum:=s div 100
7、 + 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 Best then Best := Sum; if Sum ScoreJ the
8、n 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.
