简单枚举算法教案

简单枚举算法教案朱全民

简单枚举法 枚举法 所谓枚举法,指的是从可能的解集合中一一枚举各元素,用 题目给定的检验条件判定哪些是无用的,哪些是有用的.能 使命题成立,即为其解。一般思路： 对命题建立正确的数学模型； 根据命题确定的数学模型中各变量的变化范围(即可能解 的范围); 利用循环语句、条件判断语句逐步求解或证明； 枚举法的特点是算法简单，但有时运算量大。对于可能确 定解的值域又一时找不到其他更好的算法时可以采用枚举 法。

虽然枚举法本质上属于搜索策略，但是它与回溯法有所不同。因为适用枚 举法求解的问题必须满足两个条件： ⑴可预先确定每个状态的元素个数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 dofo a2←a21 to a2k do for ai←ai1 to aik do …………………… ……………………

for an←an1 to ank doif 状态(a1,…,ai,…,an)满足检验条件 then 输出问题的解；

枚举法优缺点枚举法的优点： ⑴由于枚举算法一般是现实生活中问题的“直译”,因此比较直观，易于 理解； ⑵由于枚举算法建立在考察大量状态、甚至是穷举所有状态的基础上，所 以算法的正确性比较容易证明。

枚举法的缺点：枚举算法的效率取决于枚举状态的数量以及单个状态枚举的代价，因此 效率比较低。

示例求满足表达式A+B=C的所有整数解，其中A,B,C为1~100之间的整数。 分析：本题非常简单，即枚举所有情况，符合表达式即可。 算法如下： 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);显然可以修改如下: for A := 1 to 3 do for B := 1 to 3 do C := A+B if (C<=100) AND (C>=1)then Writeln(A, ‘+’, B, ‘=’, C);

巧妙填数 将1~9这九个数字填入九个空格中。每一横行的 三个数字组成一个三位数。如果要使第二行的三 位数是第一行的两倍, 第三行的三位数是第一行 的三倍, 应怎样填数。如图1 9 2

3 5

8 7

4 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.

跳远在水平面上整齐的放着n个正三角形，相邻两个三角形的底边之间无空隙， 如左图所示。一个小孩子想站在某个三角形i的顶端，跳到三角形j的顶端上(i<j)。 他总是朝着斜向45度的方向起跳，且初始水平速度v不超过一个给定值v0。在跳跃过 程中，由于受到重力作用(忽略空气阻力),小孩子将沿着抛物线行进，水平运动方 程为x = x0 + vt,竖直运动方程为y = y0 + vt – 0.5gt2,运动轨迹是一条上凸的抛 物线。取g=10.0,(x0, y0)是起跳点坐标。 请编程求出他从每个位置起跳能到达的最远三角形的编号。注意：跳跃过程中不许碰 到非起点和终点的其他三角形。

输入 第一行为两个正整数n,v0(3≤n≤10, 1≤v0≤100),表示三角形的个数和最大水平 初速度。 第二行有n个正整数li(1≤li≤20),表示从左到右各个三角形的边长。 输出 输出仅一行，包括n-1个数，表示从三角形1,2,3…n-1的顶点出发能到达的最右的 三角形编号。如果从某三角形出发无法达到任何三角形，相应的数为0。

状态：起 跳点 i和 i 点后的点 j 。每个状 态元素的 取值范围 ： 1≤i≤n-1,i+1≤j≤n 约束条件的分析：判断小孩能否从i点跳到j点的方法如下： 设起点和终点间的水平距离为l、垂直距离为h。则由物理知识 (已在题目中给出)有： t = l / v l 2 2 = l – 5* ( )。 h = vt – 5t v 因此，v = sqrt(5*l*l/ (l - h))。当然，这个v不一定符合 要求，它需要满足两个条件。 ⑴它不能大于极限速度v0,即必须有v ≤ v0 ⑵跳跃过程中不得碰到其他三角形。如何判断顶点k是否在抛物线下呢？我们可以算出到达时间t0 = dx / v(其 中dx为起点到顶点k的水平坐标增量),然后算出该时刻的竖直坐标增量 vt0 – 0.5t02。如果此增量大于起点到顶点k的竖直坐标增量，则抛物线在 上方。只有起点和终点之间任何一个三角形的顶点不在抛物线下方，则跳 远不能完成。 我们在枚举过程中不断将小孩所能跳到的点j调整为best。 枚举结束后， best即为试题要求的最远点。

var

len : array[1 .. 20] of longint;x, y : array[1 .. 20] of double;{三角形顶端顶点的坐标序列} l, h, t, v, v0 : double; ok : boolean;{跳跃成功标志} i, j

, k, n, best : integer; begin read(n, v0);{输入三角形的个数和最大水平初速度} for i ← 1 to n do read(len[i]);入从左到右各个三角形的边长} x[1] ← len[1] / 2;{计算每一个三角形顶端顶点的坐标} y[1] ← len[1] * sqrt(3) / 2;

for i ← 2 to n dobegin x[i] ← x[i - 1] + len[i - 1] / 2 + len[i] / 2; y[i] ← len[i] * sqrt(3) / 2; end;{for}

for i ← 1 to n - 1 do{依次计算每一个三角形所能到达的最远点}

beginbest ← 0;{从三角形i出发能到达的最右的三角形编号初始化} for j ← i + 1 to n do{依次枚举右方的每一个三角形}

beginl← x[j] - x[i];{计算三角形i与三角形j的两个顶端顶点的水平距离和垂直 距离} h ← y[j] - y[i]; if l < h then break;{若起跳角度超过45度，则无法从三角形i起跳} v ← sqrt(5 * l * l / (l - h));{计算即时速度v} if v > v0 then break;{若大于极限速度v0,则无法从三角形i起跳}

ok ← true;for k ← i + 1 to j - 1 do{判断跳跃过程中是否碰到其他三角形} begin t ← (x[k] - x[i]) / v;{计算到达三角形k的时间}

if (v * t - 5 * t * t) - (y[k] - y[i]) < 1e-6 then begin{如果该时刻的竖直坐标增量大于起点到顶点k的竖直坐标增量，则 抛物线在上方}ok ← false; break; end;{then} end;{for} if ok then best ← j {若跳远成功，则三角形j为目前三角形i所能到达的最远点，否则跳 远不能完成} else break; end;{for} write(best,' ');{输出从三角形i的顶点出发所能到达的最右的三角形编号)

end;{for}writeln; end.{main}

二、枚举算法的优化枚举算法的时间复杂度可以用状态总数*考察单个状态的耗时 来表示，因此优化主要是 ⑴减少状态总数(即减少枚举变量和枚举变量的值域) ⑵降低单个状态的考察代价

优化过程从几个方面考虑。具体讲 ⑴提取有效信息

⑵减少重复计算⑶将原问题化为更小的问题 ⑷根据问题的性质进行截枝 ⑸引进其他算法

立方体问题现有一个棱长为n的立方体，可以分成n3个1*1*1的单位立方体。每个单位立方体都有 一个整数值。n3个单位立方体的数和不会超过longint范围。现在要求在这个立方体找 到一个包含完整单位立方体的长方体，使得该长方体内所有单位立方体的数和最大。 输入： n(1≤n≤20);n个n*n的数字矩阵，每个数字矩阵代表一层，每个数字代表一 个单位立方体的整数值，-999≤单位立方体的整数值≤999 输出：长方体的数和

1、“直译”枚举过程for x1←1 to n do for x2←1 to n do {枚举所有可能的平面}

for y1←1 to n dofor y2←1 to n do for z1←1 to n do for z2←1 to n do 考察状态(x1,y1,z1,x2,y2,z2); {枚举所有可能的上平面和下底面}

考察状态(x1,y1,z1,x2,y2,z2)的任务是计算长方体的体

积，并调整最优解。设 map为立方体对应的三维矩阵；sum为当前长方体的体积；best为最优解。考察过程如 下 sum←0; for x←x1 to x2 do for y←y1 to y2 do for z←z1 to z2 do sum←sum+map[x,y,z]; {调整最优解} if sum>best then best←sum; {计算长方体的体积}

这个算法相当粗糙，枚举状态的费用为O(n9)

2、从减少重复计算入手记录先前考察的结果。在统计长方体2时，只要将长方体1的统计结果加上长方体3就可以了，而 不必按上述算法那样重新进行计算。

for x1←1 to n do

{枚举所有可能的水平面}

for x2←1 to n dofor y1←1 to n do for y2←1 to n do for z1←1 to n do begin sum←0; for z2←1 to n do end;{for} 考察过程改为 {长方体的体积初始化} {枚举下底面的z轴坐标} {枚举上平面的z轴坐标}

考察状态(x1,y1,z1,x2,y2,z2);

for x←x1 to x2 dofor y←y1 to y2 do sum←sum+map[x,y,z2]; if sum>best then best←sum;

{计算长方体的体积}

{调整最优解}

由于利用了计算出的结果，整个算法的时间复杂度降为O(n8)。

3、提取恰当的信息上述考察实际上求出z轴坐标为z2的平面中矩形(x1, y1,x2,y2)的数和。我们将这个数和记为value(a) value(A)=value(ABCD)+value(B)-value(BC)value(BD)

这就启发我们用另一种方法表示立方体的信息：设 rec[x,y,z]表示z轴坐标为z的水平面中矩形(1, 1,x,y)的数和。

z轴坐标为z的水平面中左上角为(x1,y1)、右下角 为 ( x2 , y2 ) 的 矩 阵 的 数 和 为 rec[x2 , y2 , z]+ rec[x1,y1,z]-rec[x2,y1,z]-rec[x1,y2,z]

Rec数组可以在输入数据的同时计算 fillchar(rec,size(rec),0);{rec数组初始化} for z←1 to n do for x←1 to n do begin for y←1 to n do begin read(map[x,y,z]); {输入z平面上(x,y)中的数} {逐列输入z平面上x行的信息} {逐层输入信息} {逐行输入z平面的信息}

if (x=1)and(y=1) {计算z平面上以(1,1)为左上角、(x,y)为右下角的矩形的数和}

then rec[1,1,z]←map[1,1,z]else if y=1 then rec[x,y,z]←rec[x-1,n,z]+map[x,y,z] else rec[x,y,z]←rec[x,y-1,z]+map[x,y,z]; end;{for} readln; end;{for} 这样，考察过程就可以改为 sum←sum+rec[x2,y2,z2]+rec[x1,y1,z2]-rec[x2,y1,z2]-rec[x1,y2,z2]; if sum>best then best←sum; 时间复杂度降为O(n6)。

如果长方体a的数和是负数，则长方体a的计算结果废弃，考察长方 体b-a。因为长方体b的数和=长方体b-a的数和+长方体a的数和，由 于长方体a的数和为负，长方体b-a的数和一定大于等于长方体b的 数和。由此可见，在累计长方体数和的时候，只要由上而下地枚举 长方体下底面的z轴坐标即可。设 total(z)——以z轴坐标为z的平面为下底面的长方体的最大数和0 total(z

)= max(0, total( z 1)) rec[ x2 , y2 , z] rec[ x1 1, y1 1, z] rec[ x2 , y1 1, z] rec[ x1 1, y2 , z] z 0 z 0

for x1←1 to n do for x2←1 to n do for y1←1 to n do for y2←1 to n do

{枚举所有可能的子平面}

begintotal←0;{长方体b(该长方体的平面以(x1,y1)为左上角、(x2,y2)为右下上角)的最大数和初始化} for z←1 to n do begin total←max{total,0}+ rec[x2,y2,z]+ rec[x1-1,y1-1,z]-rec[x2,y1-1,z]-rec[x-1-1,y2,z];{计算以z为下底 面的长方体b的最大数和} if total> best then best←total; end;{for} end;{for} {调整最优解} {枚举长方体b下底面的z轴坐标}

这一改进使得考察的状态整数降为n5,

时钟问题

九种时钟状态

本文来源：https://www.bwwdw.com/article/41xe.html