资源描述：
《简单枚举算法教案》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、简单枚举算法教案朱全民简单枚举法枚举法所谓枚举法,指的是从可能的解集合中一一枚举各元素,用题目给定的检验条件判定哪些是无用的,哪些是有用的.能使命题成立,即为其解。一般思路：对命题建立正确的数学模型；根据命题确定的数学模型中各变量的变化范围（即可能解的范围）；利用循环语句、条件判断语句逐步求解或证明；枚举法的特点是算法简单，但有时运算量大。对于可能确定解的值域又一时找不到其他更好的算法时可以采用枚举法。虽然枚举法本质上属于搜索策略，但是它与回溯法有所不同。因为适用枚举法求解的问题必须满足两个条件：⑴可预先确定每个状
2、态的元素个数n；⑵状态元素a1，a2，…，an的可能值为一个连续的值域。设ai1—状态元素ai的最小值；aik—状态元素ai的最大值(1≤i≤n)，即a11≤a1≤a1k，a21≤a2≤a2k，ai1≤ai≤aik，……，an1≤an≤ankfora1←a11toa1kdofoa2←a21toa2kdo……………………forai←ai1toaikdo……………………foran←an1toankdoif状态(a1，…，ai，…，an)满足检验条件then输出问题的解；枚举法的优点：⑴由于枚举算法一般是现实生活中问题的
3、“直译”，因此比较直观，易于理解；⑵由于枚举算法建立在考察大量状态、甚至是穷举所有状态的基础上，所以算法的正确性比较容易证明。枚举法的缺点：枚举算法的效率取决于枚举状态的数量以及单个状态枚举的代价，因此效率比较低。枚举法优缺点示例求满足表达式A+B=C的所有整数解，其中A，B，C为1~100之间的整数。分析：本题非常简单，即枚举所有情况，符合表达式即可。算法如下：forA:=1to100doforB:=1to100doforC:=1to100doifA+B=CthenWriteln(A,‘+’,B,‘=’,C);显
4、然可以修改如下:forA:=1to100doforB:=1to100doC:=A+Bif(C<=100)AND(C>=1)thenWriteln(A,‘+’,B,‘=’,C);巧妙填数将1～9这九个数字填入九个空格中。每一横行的三个数字组成一个三位数。如果要使第二行的三位数是第一行的两倍,第三行的三位数是第一行的三倍,应怎样填数。如图192384576分析本题目有9个格子，要求填数，如果不考虑问题给出的条件，共有9！=362880种方案，在这些方案中符合问题条件的即为解。因此可以采用枚举法。但仔细分析问题，显然第一
5、行的数不会超过400，实际上只要确定第一行的数就可以根据条件算出其他两行的数了。这样仅需枚举400次。因此设计参考程序：vari,j,k,s:integer;functionsum(s:integer):integer;beginsum:=sdiv100+sdiv10mod10+smod10end;functionmul(s:integer):longint;beginmul:=(sdiv100)*(sdiv10mod10)*(smod10)end;程序beginfori:=1to3doforj:=1to9doif
6、j<>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.逻辑判断问题在某次数学竞赛中,A、B、C、D、E五名学
7、生被取为前五名。请据下列说法判断出他们的具体名次,即谁是第几名？条件1:你如果认为A,B,C,D,E就是这些人的第一至第五名的名次排列,便大错。因为:没猜对任何一个优胜者的名次。也没猜对任何一对名次相邻的学生。条件2:你如果按D,A,E,C,B来排列五人名次的话,其结果是:说对了其中两个人的名次。还猜中了两对名次相邻的学生的名次顺序。分析：本题是一个逻辑判断题，一般的逻辑判断题都采用枚举法进行解决。5个人的名次分别可以有5！=120种排列可能，因为120比较小，因此我们对每种情况进行枚举，然后根据条件判断哪些符合问
8、题的要求。分析:根据已知条件，A<>1,B<>2,C<>3,D<>4,E<>5,因此排除了一种可能性，只有4！=24种情况了。ProgramExam;VarA,B,C,D,E:Integer;Cr:Array[1..5]OfChar;BeginForA:=1To5DoForB:=1To5DoForC:=1To5DoForD:=1To5DoForE:=1To5
