枚举及优化分析解析.ppt

1、枚举及优化,枚举法,枚举法的基本思想是根据提出的问题枚举所有可能状态，并用问题给定的条件检验哪些是需要的，哪些是不需要的。能使命题成立，即为其解。虽然枚举法本质上属于搜索策略，但是它与后面讲的回溯法有所不同。因为适用枚举法求解的问题必须满足两个条件： 可预先确定每个状态的元素个数n； 状态元素a1，a2，an的可能值为一个 连续的值域。,设ai1状态元素ai的最小值；aik状态元素ai的最大值(1in)，即a11a1a1k，a21a2a2k， ai1aiaik，an1anank for a1a11 to a1k do fo a2a21 to a2k do for aiai1 to aik do

2、 for anan1 to ank do if 状态(a1，ai，an)满足检验条件 then 输出问题的解；,陶陶摘苹果(apple.pas/c/cpp)【问题描述】陶陶家的院子里有一棵苹果树，每到秋天树上就会结出10个苹果。苹果成熟的时候，陶陶就会跑去摘苹果。陶陶有个30厘米高的板凳，当她不能直接用手摘到苹果的时候，就会踩到板凳上再试试。现在已知10个苹果到地面的高度，以及陶陶把手伸直的时候能够达到的最大高度，请帮陶陶算一下她能够摘到的苹果的数目。假设她碰到苹果，苹果就会掉下来。,【输入文件】输入文件apple.in包括两行数据。第一行包含10个100到200之间（包括100和200）的整

3、数（以厘米为单位）分别表示10个苹果到地面的高度，两个相邻的整数之间用一个空格隔开。第二行只包括一个100到120之间（包含100和120）的整数（以厘米为单位），表示陶陶把手伸直的时候能够达到的最大高度。【输出文件】输出文件apple.out包括一行，这一行只包含一个整数，表示陶陶能够摘到的苹果的数目。【样例输入】100 200 150 140 129 134 167 198 200 111110【样例输出】5,program apple; var a:array1.10 of integer; n,i,total:integer; begin assign(input,apple.in);

4、 reset(input); for i:=1 to 10 do read(ai); readln(n); close(input); n:=n+30; for I:=1 to 10 do if n=ai then inc(total); assign(output,apple.out); rewrite(output); writeln(total); close(output); End.,丑数（ugly） 【问题描述】所谓丑数，就是指那些因子只含2，3，5的数。1，2，3，4，5，6，8，9，10，12，15是最前面的11个丑数。为了方便起见，把1也看作是丑数。请你编写一个程序，输入n，

5、寻找并打印第n个丑数。 【输入数据】 输入文件仅包含一个整数n（0n3000）。 【输出数据】 输出文件仅包含一个整数，表示所求的第n个丑数。 【样例】 ugly.in 11 ugly.out 15,program ugly; var i,n,h1,h2,h3:longint; min:qword; f:array1.3000 of qword; begin assign(input,ugly.in); reset(input); assign(output,ugly.out); rewrite(output); readln(n); f1:=1; h1:=1;h2:=1;h3:=1; for

6、 i:=2 to n do begin min:=fh1*2; if 3*fh2min then min:=3*fh2; if 5*fh3min then min:=5*fh3; if min=2*fh1 then inc(h1); if min=3*fh2 then inc(h2); if min=5*fh3 then inc(h3); fi:=min; end; write(fn); close(input); close(output); end.,班级人数,【问题描叙】 班会评选一级学生，（做出10题以上的有机会参加评选）。最后评选结果班上有超过P%但不足Q%的人被评上了（学生一：听起

7、来像是URAL上的1011。）。现在给你P和Q，你要算出班上最少有多少人。（数据弱了一点，所以好通过）。 【输入格式】 两个实数P，Q。用空格隔开。每个数最多有两位小数。0.00=pq=99.99 【输出格式】 班上最少的人数。 【样例输入】 13 14.1 【样例输出】 15 【时间限制】 每个测试点1s,人数从小到大枚举 枚举 本题的解不存在连续性（如15人对，16人就错），不能二分，所以只能枚举。 注意：精度问题,program classes; var a,b,total1,total2:real; i,j,k,n:longint; f:boolean; begin assign(in

8、put,classes.in); reset(input); assign(output,classes.out); rewrite(output); readln(a,b); f:=false;,repeat i:=i+1; total1:=i*a/100; total2:=i*b/100; j:=0; repeat j:=j+1; if (jtotal1) and (jtotal2; until f=true; close(input); close(output); end.,核弹危机,【问题描叙】 安安和庆庆正在玩红警,可不料安安造出了核弹正要发射.（庆庆 _） 已知核弹的攻击范围是边

9、长n的正方形，庆庆的基地是边长m的正方形 基地样例： .#.# .#.# #.# . .# .#. #表示房屋，.表示平地，求核弹最多能摧毁多少房屋（被核弹攻击的房屋都会消失，好强啊）。,【输入格式】 第一行基地边长m（10000m0) 第二行核弹攻击边长n(10000n-1) 接下来m行输入基地 【输出格式】 摧毁最多房屋数 【样例输入】 6 3 .#.# # . . #. .# 【样例输出】 5 【时间限制】 每个测试点1s,var m,n:longint; a:array1.10002,1.10002 of char; procedure process; var i,j,s,k,l,m

10、ax:longint; begin max:=0; for i:=1 to m+1-n do for j:=1 to m+1-n do begin s:=0; for k:=0 to n-1 do for l:=0 to n-1 do if ai+k,j+l=# then inc(s); if smax then max:=s; end; writeln(max); end;,procedure init; var i,j:longint; begin readln(m); readln(n); for i:=1 to m do begin for j:=1 to m do read(ai,j

11、); readln; end; end;,begin assign(input,nuclear.in);reset(input); assign(output,nuclear.out);rewrite(output); init; process; close(input); close(output); end.,数独验证,【背景描叙】 合肥五十中中风靡一款智力游戏，也就是数独（九宫格），先给你一个数独，并需要你验证是否符合规则。 【问题描叙】 具体规则如下: 每一行都用到1,2,3,4,5,6,7,8,9，位置不限， 每一列都用到1,2,3,4,5,6,7,8,9，位置不限， 每33的格子

12、（共九个这样的格子）都用到1,2,3,4,5,6,7,8,9，位置不限， 游戏的过程就是用1,2,3,4,5,6,7,8,9填充空白，并要求满足每行、每列、每个九宫格都用到1,2,3,4,5,6,7,8,9。,如下是一个正确的数独: 5 8 1 4 9 3 7 6 2 9 6 3 7 1 2 5 8 4 2 7 4 8 6 5 9 3 1 1 2 9 5 4 6 3 7 8 4 3 6 1 8 7 2 9 5 7 5 8 3 2 9 1 4 6 8 9 2 6 7 1 4 5 3 6 1 5 9 3 4 8 2 7 3 4 7 2 5 8 6 1 9 【输入格式】 输入n个数独，你来验证它是否

13、违反规则. 第一行为数独个数，第二行开始为第一个数独，之后为第二个，至第n个. 注意！每个数独之间有一个回车隔开! 【输出格式】 若正确则输出”Right”若不正确则输出”Wrong” 输出一个换一行,【样例输入】 2 5 8 1 4 9 3 7 6 2 9 6 3 7 1 2 5 8 4 2 7 4 8 6 5 9 3 1 1 2 9 5 4 6 3 7 8 4 3 6 1 8 7 2 9 5 7 5 8 3 2 9 1 4 6 8 9 2 6 7 1 4 5 3 6 1 5 9 3 4 8 2 7 3 4 7 2 5 8 6 1 9 1 2 3 4 5 6 7 8 9 2 3 4 5 6

14、7 8 9 1 3 4 5 6 7 8 9 1 2 4 5 6 7 8 9 1 2 3 5 6 7 8 9 1 2 3 4 6 7 8 9 1 2 3 4 5 7 8 9 1 2 3 4 5 6 8 9 1 2 3 4 5 6 7 9 1 2 3 4 5 6 7 8 【样例输出】 Right Wrong 【时间限制】 每个测试点1s,var a,b,c,map:array1.9,1.9 of longint; n:longint; procedure process; var i,j,k:longint; begin fillchar(a,sizeof(a),0); fillchar(b,si

15、zeof(b),0); fillchar(c,sizeof(c),0); for i:=1 to 9 do for j:=1 to 9 do ai,mapi,j:=1; for i:=1 to 9 do for j:=1 to 9 do bi,mapj,i:=1; for i:=1 to 9 do for j:=1 to 9 do if (ai,j1) or (bi,j1) then begin writeln(Wrong); exit; end;,for i:=1 to 3 do for j:=1 to 3 do for k:=3*(i-1)+1 to 3*i do ci,mapj,k:=1

16、; for i:=4 to 6 do for j:=4 to 6 do for k:=3*(i-4)+1 to 3*(i-3) do ci,mapj,k:=1; for i:=7 to 9 do for j:=7 to 9 do for k:=3*(i-7)+1 to 3*(i-6) do ci,mapj,k:=1; for i:=1 to 9 do for j:=1 to 9 do if ci,j1 then begin writeln(Wrong); exit; end; writeln(Right); end;,procedure init; var i,j,k:longint; beg

17、in readln(n); for i:=1 to n do begin for j:=1 to 9 do begin for k:=1 to 9 do read(mapj,k); readln; end; process; readln; end; end;,begin assign(input,sudoku.in); reset(input); assign(output,sudoku.out); rewrite(output); init; close(input); close(output); end.,枚举法的优点： 由于枚举算法一般是现实生活中问题的“直译”，因此比较直观，易于理

18、解； 由于枚举算法建立在考察大量状态、甚至是穷举所有状态的基础上，所以算法的正确性比较容易证明。,枚举法的缺点： 枚举算法的效率取决于枚举状态的数量以及单个状态枚举的代价，因此效率比较低。,二、枚举算法的优化 枚举算法的时间复杂度可以用状态总数*考察单个状态的耗时来表示，因此优化主要是 减少状态总数（即减少枚举变量和枚举变量的值域） 降低单个状态的考察代价 优化过程从几个方面考虑。具体讲 提取有效信息 减少重复计算 将原问题化为更小的问题 根据问题的性质进行截枝 引进其他算法,例4 邮票面值问题,【问题描述】 邮局发行一套票面有四种不同值的邮票，如果每封信所贴邮票张数不超过三枚，存在整数，使得

19、用不超过三枚的邮票，可以贴出连续的整数、，来，找出这四种面值数，使得值最大。 【算法分析】 设四种邮票的面值分别为： A , B , C , D ，根据题意设：A B C D，因此 A=1 。如何保证所取不超过3张的邮票面值能得到连续的整数，关键是面值为B、C、D的取值范围： 因为A=1，且每种面值最多取3张，所以，A+1B3A+1;B+1C3B+1;C+1D3C+1。 邮票张数的控制：确保所取邮票不超过3张,枚举4种面值的张数用4重循环实现：,for n1:= 0 to 3 do 穷举每种邮票所取的张数 for n2:= 0 to 3-n1 do for n3:= 0 to 3-n1- n2

20、 do for n4:= 0 to 3-n1-n2-n3 do 这里循环变量的终值不是简单地都取3，而是加以限制 【参考程序】 Program L4; var a, b , c , d ： integer ; x, x0, x1 , x2 , x3, x4 ： integer ; st1 ： set of 1 100 ;,Function number( a, b, c, d : integer ) ： integer ; var n1, n2, n3 ,n4 , sum :integer ; begin st1:= ; for n1:= 0 to 3 do for n2:= 0 to 3-n

21、1 do for n3:= 0 to 3-n1- n2 do for n4:= 0 to 3-n1-n2-n3 do begin sum:= n1*a+n2*b+n3*c+n4*d ; 计算信封的邮票面值 st1:=st1+sum end; sum:=1 ; while sum in st1 do sum:=sum+1; number:= sum-1; end ; 函数结束 ,BEGIN 主程序 a:=1 ; x0:=0 ; for b:= a+1 to 3*a+1 do for c:= b+1 to 3*b+1 do每种邮票的可取值的范围 for d:= c+1 to 3*c+1 do be

22、gin x:=number(a,b,c,d );调用函数求邮票总面值 if xx0 then begin保存最大面值邮票 x0:=x; x1:=a ; x2:=b ; x3:=c ; x4:=d end end; writeln(x1：5,x2：5,x3：5,x4：10,R=, x0 ); End.,例 完全平方数 【问题描叙】 用1到9九个阿拉伯数字构成的全排列中，每一种排列也可以看成一个九位数，求出其中是完全平方数的所有排列，并输出总共有多少种这样的排列。 输入数据：无 输出数据： 输出所有的完全平方数，一行一个，最后再输 出总个数。,var i,j,num,s,total:longint

23、; used:array0.9 of 0.1; begin for i:=11111 to 31427 do begin num:=sqr(i); fillchar(used,sizeof(used),0); while num0 do begin usednum mod 10:=1; num:=num div 10; end; s:=0; for j:=1 to 9 do inc(s,usedj); if s=9 then begin inc(total); writeln(i*i); end; end; write(total); end.,例5阿姆斯特朗数 【问题描述】 编一个程序找出所有的三位数到七位数中的阿姆斯特朗数。 阿姆斯特朗数也叫水仙花数，它的定义如下:若一个n位自然数的各位数字的n次方之和等于它本身，则称这个自然数为阿姆斯特朗数。例如153(153=1*1*1+3*3*3+5*5*5)是一个三位数的阿姆斯特朗数，8208则是一个四位数的阿姆斯特朗数。,program amsts; var