文档介绍：
简单枚举算法教案
欢喜的画笔
简单枚举法
枚举法
所谓枚举法,指的是从可能的解集合中一一枚举各元素,用题目给定的检验条件判定哪些是无用的,哪些是有用的.能使命题成立,即为其解。一般思路:
对命题建立正确的数学模型;
根据命题确定的数学模型中各变量的变化范围(即可能解的范围);
利用循环语句、条件判断语句逐步求解或证明;
枚举法的特点是算法简单,但有时运算量大。对于可能确定解的值域又一时找不到其他更好的算法时可以采用枚举法。
虽然枚举法本质上属于搜索策略,但是它与回溯法有所不同。因为适用枚举法求解的问题必须满足两个条件: ⑴可预先确定每个状态的元素个数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 输出问题的解;
枚举法的优点:
⑴由于枚举算法一般是现实生活中问题的“直译”,因此比较直观,易于理解;
⑵由于枚举算法建立在考察大量状态、甚至是穷举所有状态的基础上,所以算法的正确性比较容易证明。
枚举法的缺点:
枚举算法的效率取决于枚举状态的数量以及单个状态枚举的代价,因此效率比较低。
枚举法优缺点
示例
求满足表达式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);
巧妙填数
将1~9这九个数字填入九个空格中。每一横行的三个数字组成一个三位数。如果要使第二行的三位数是第一行的两倍, 第三行的三位数是第一行的三倍, 应怎样填数。如图
1
9
2
3
8
4
5
7
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;
程序
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.
逻辑判断问题
在某次数学竞赛中, A、B、C、D、E五名学生被取为前五名。请据下列说法判断出他们的具体名次, 即谁是第几名?
条件1: 你如果认为A, B, C, D, E 就是这些人的第一至第五名的名次排列, 便大错。因为:
没猜对任何一个优胜者的名次。
也没猜对任何一对名次相邻的学生。
条件2: 你如果按D, A , E , C , B 来排列五人名次
内容来自淘豆网www.taodocs.com转载请标明出处.