高中信息技术 全国青少年奥林匹克联赛教案 枚举法二VIP免费

枚举法课题：枚举法目标：知识目标：枚举算法的本质和应用能力目标：枚举算法的应用！重点：利用枚举算法解决实际问题难点：枚举算法的次数确定板书示意：1）简单枚举（例7、例8、例9）2）利用枚举解决逻辑判断问题（例10、例11）3）枚举解决竞赛问题（例12、例13、例14）授课过程：所谓枚举法,指的是从可能的解集合中一一枚举各元素,用题目给定的检验条件判定哪些是无用的,哪些是有用的.能使命题成立,即为其解。一般思路：对命题建立正确的数学模型；根据命题确定的数学模型中各变量的变化范围（即可能解的范围）；利用循环语句、条件判断语句逐步求解或证明；枚举法的特点是算法简单，但有时运算量大。对于可能确定解的值域又一时找不到其他更好的算法时可以采用枚举法。例7：求满足表达式A+B=C的所有整数解，其中A，B，C为1~3之间的整数。分析：本题非常简单，即枚举所有情况，符合表达式即可。算法如下：forA:=1to3doforB:=1to3doforC:=1to3doifA+B=CthenWriteln(A,‘+’,B,‘=’,C);上例采用的就是枚举法。所谓枚举法，指的是从可能的解的集合中一一枚举各元素，用题目给定的检验条件判定哪些是无用的，哪些是有用的。能使命题成立的，即为解。从枚举法的定义可以看出，枚举法本质上属于搜索。但与隐式图的搜索有所区别，在采用枚举法求解的问题时，必须满足两个条件：①预先确定解的个数n；②对每个解变量A1，A2，……，An的取值，其变化范围需预先确定A1∈{X11，……，X1p}……Ai∈{Xi1，……，Xiq}……An∈{Xn1，……，Xnk}例7中的解变量有3个：A，B，C。其中A解变量值的可能取值范围A∈{1，2，3}B解变量值的可能取值范围B∈{1，2，3}C解变量值的可能取值范围C∈{1，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]范围内的所有整数解。分析：要求方程的在一个范围内的解，只要对这个范围内的所有整数点进行枚举，看这些点是否满足方程即可。参考程序：programexam8;vara,b,c:integer;x,y:integer;beginwrite('Inputa,b,c:');readln(a,b,c);forx:=0to100dofory:=0to100doifa*x+b*y=cthenwriteln(x,'',y);end.从上例可以看出，所谓枚举法,指的是从可能的解集合中一一枚举各元素,用题目给定的检验条件判定哪些是无用的,哪些是有用的.能使命题成立,即为其解。例9巧妙填数将1～9这九个数字填入九个空格中。每一横行的三个数字组成一个三位数。如果要使第二行的三位数是第一行的两倍,第三行的三位数是第一行的三倍,应怎样填数。如图6:图6分析：本题目有9个格子，要求填数，如果不考虑问题给出的条件，共有9！=362880种方案，在这些方案中符合问题条件的即为解。因此可以采用枚举法。但仔细分析问题，显然第一行的数不会超过400，实际上只要确定第一行的数就可以根据条件算出其他两行的数了。这样仅需枚举400次。因此设计参考程序：programexam9;vari,j,k,s:integer;functionsum(s:integer):integer;192384576beginsum:=sdiv100+sdiv10mod10+smod10end;functionmul(s:integer):longint;beginmul:=(sdiv100)*(sdiv10mod10)*(smod10)end;beginfori:=1to3doforj:=1to9doifj<>ithenfork:=1to9doif(k<>j)and(k<>i)thenbegins:=i*100+j*10+k;{求第一行数}if3*s<1000thenif(sum(s)+sum(2*s)+sum(3*s)=45)and(mul(s)*mul(2*s)*mul(3*s)=362880)then{满足条件，并数字都由1~9组成}beginwriteln(s);writeln(2*s);writeln(3*s);writeln;end;end;end.例10在某次数学竞赛中,A、B、C、D、E五名学生被取为前五名。请据下列说法判断出他们的具体名次,即谁是第几名？条件1:你如果认为A...