简单枚举算法教案省公开课一等奖全国示范课微课金奖PPT课件.pptx

该【简单枚举算法教案省公开课一等奖全国示范课微课金奖PPT课件 】是由【rongfunian】上传分享，文档一共【34】页，该文档可以免费在线阅读，需要了解更多关于【简单枚举算法教案省公开课一等奖全国示范课微课金奖PPT课件 】的内容，可以使用淘豆网的站内搜索功能，选择自己适合的文档，以下文字是截取该文章内的部分文字，如需要获得完整电子版，请下载此文档到您的设备，方便您编辑和打印。简单枚举算法教案
朱全民
第1页
简单枚举法
枚举法
所谓枚举法,指是从可能解集合中一一枚举各元素,用题目给定检验条件判定哪些是无用,,即为其解。普通思绪：
对命题建立正确数学模型；
依据命题确定数学模型中各变量改变范围（即可能解范围）；
利用循环语句、条件判断语句逐步求解或证实；
枚举法特点是算法简单，但有时运算量大。对于可能确定解值域又一时找不到其它更加好算法时能够采取枚举法。
第2页
即使枚举法本质上属于搜索策略，不过它与回溯法有所不一样。因为适用枚举法求解问题必须满足两个条件：       ⑴可预先确定每个状态元素个数n；
⑵状态元素a1，a2，…，an可能值为一个连续值域。
设
ai1—状态元素ai最小值；aik—状态元素ai最大值(1≤i≤n)，即a11≤a1≤a1k，a21≤a2≤a2k， ai1≤ai≤aik，……，an1≤an≤ank
for a1←a11 to a1k do
fo a2←a21 to a2k do ……………………
for ai←ai1 to aik do ……………………
for an←an1 to ank do
if 状态(a1，…，ai，…，an)满足检验条件
then 输出问题解；
第3页
枚举法优点：
⑴因为枚举算法普通是现实生活中问题“直译”，所以比较直观，易于了解；
⑵因为枚举算法建立在考查大量状态、甚至是穷举全部状态基础上，所以算法正确性比较轻易证实。
枚举法缺点：
枚举算法效率取决于枚举状态数量以及单个状态枚举代价，所以效率比较低。
枚举法优缺点
第4页
示例
求满足表示式A+B=C全部整数解，其中A，B，C为1~100之间整数。
分析：本题非常简单，即枚举全部情况，符合表示式即可。
算法以下：
for A := 1 to 100 do
for B := 1 to 100 do
for C := 1 to 100 do
if A + B = C then
Writeln(A, ‘+’, B, ‘=’, C);
显然能够修改以下:
for A := 1 to 100 do
for B := 1 to 100 do
C := A+B
if (C<=100) AND (C>=1)then
Writeln(A, ‘+’, B, ‘=’, C);
第5页
巧妙填数
将1～9这九个数字填入九个空格中。每一横行三个数字组成一个三位数。假如要使第二行三位数是第一行两倍, 第三行三位数是第一行三倍, 应怎样填数。如图
1
9
2
3
8
4
5
7
6
第6页
分析
本题目有9个格子，要求填数，假如不考虑问题给出条件，共有9！=362880种方案，在这些方案中符合问题条件即为解。所以能够采取枚举法。
但仔细分析问题，显然第一行数不会超出400，实际上只要确定第一行数就能够依据条件算出其它两行数了。这么仅需枚举400次。所以设计参考程序：
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;
第7页
程序
begin
for i:=1 to 3 do
for j:=1 to 9 do
if j<>i then for k:=1 to 9 do
if (k<>j) and (k<>i) then begin
s := i*100 + j*10 +k; {求第一行数}
if 3*s<1000 then
if (sum(s)+sum(2*s)+sum(3*s)=45) and(mul(s)*mul(2*s)*mul(3*s)=362880) then {满足条件，并数字都由1~9组成}
begin
writeln(s);
writeln(2*s);
writeln(3*s);
writeln;
end;
end;
end.
第8页
逻辑判断问题
在某次数学竞赛中, A、B、C、D、E五名学生被取为前五名。请据以下说法判断出他们详细名次, 即谁是第几名？
条件1: 你假如认为A, B, C, D, E 就是这些人第一至第五名名次排列, 便大错。因为:
没猜对任何一个优胜者名次。
也没猜对任何一对名次相邻学生。
条件2: 你假如按D, A , E , C , B 来排列五人名次话, 其结果是:
说对了其中两个人名次。
还猜中了两对名次相邻学生名次次序。
分析：本题是一个逻辑判断题，普通逻辑判断题都采取枚举法进行处理。5个人名次分别能够有5！=120种排列可能，因为120比较小，所以我们对每种情况进行枚举，然后依据条件判断哪些符合问题要求。
分析:
依据已知条件，A<>1,B<>2,C<>3,D<>4,E<>5,所以排除了一个可能性，只有4！=24种情况了。
第9页
Program Exam;
Var
A,B,C,D,E :Integer;
Cr :Array[1..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
If (A=1) Or (B=2) Or (C=3) Or (D=4) Or (E=5)
Then Continue; {ABCDE没猜对一个人名次}
If [A,B,C,D,E]<>[1,2,3,4,5] Then Continue;{他们名次互不重复}
If Ord(A=2)+Ord(B=5)+Ord(C=4)+Ord(D=1)+Ord(E=3)<>2
Then Continue; {DAECB猜对了两个人名次}
If (B=A+1) Or (C=B+1) Or (D=C+1) Or (E=D+1)
Then Continue; {ABCDE没猜对一对相邻名次}
If Ord(A=D+1)+Ord(E=A+1)+Ord(C=E+1)+Ord(B=C+1)<>2
Then Continue; {DAECB猜对了两对相邻人名次}
Cr[A]:='A';Cr[B]:='B';Cr[C]:='C';
Cr[D]:='D';Cr[E]:='E';
WRITELN(CR[1],' ',CR[2],' ',CR[3],' ',CR[4],' ',CR[5]);
End;
End.
第10页