枚举及优化.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,枚举及优化,枚举法,枚举法的基本思想是根据提出的问题枚举所有可能状态，并用问题给定的条件检验哪些是需要的，哪些是不需要的。能使命题成立，即为其解。虽然枚举法本质上属于搜索策略，但是它与后面讲的回溯法有所不同。因为适用枚举法求解的问题必须满足两个条件：可预先确定每个状态的元素个数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 ,for anan1 to ank do,if 状态(a1，ai，an)满足检验条件,then 输出问题的解；,陶陶摘苹果(apple.pas/c/cpp)【问题描述】陶陶家的院子里有一棵苹果树，每到秋天树上就会结出10个苹果。苹果成熟的时候，陶陶就会跑去摘苹果。陶陶有个30厘米高的板凳，当她不能直接用手摘到苹果的时候，就会踩到板凳上再试试。现在已知10个苹果到地面的高度，以及陶陶把手伸直的时候能够达到的最大高度，请帮陶陶算一下她能够摘到的苹果的数目。假设她碰到苹果，苹果就会掉下来。,【输入文件】输入文件apple.in包括两行数据。第一行包含10个100到200之间（包括100和200）的整数（以厘米为单位）分别表示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);,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，寻找并打印第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 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%的人被评上了（学生一：听起来像是URAL上的1011。）。现在给你P和Q，你要算出班上最少有多少人。（数据弱了一点，所以好通过）。,【输入格式】,两个实数P，Q。用空格隔开。每个数最多有两位小数。0.00=pqtotal1)and(jtotal2;,until f=true;,close(input);,close(output);,end.,核弹危机,【问题描叙】,安安和庆庆正在玩红警,可不料安安造出了核弹正要发射.（庆庆 _）,已知核弹的攻击范围是边长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,max:longint;,begin,max:=0;,for i:=1 to m+1n 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);,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的格子（共九个这样的格子）都用到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个数独，你来验证它是否违反规则.,第一行为数独个数，第二行开始为第一个数独，之后为第二个，至第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 7 8 9 1,3 4 5 6 7 8 9 1 2,4 5 6 7 8 9 1 2 35 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,sizeof(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;,for i:=4 to 6 do,for j:=4 to 6 do for k:=3*(i4)+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;,begin,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.,枚举法的优点：,由于枚举算法一般是现实生活中问题的“直译”，因此比较直观，易于理解；,由于枚举算法建立在考察大量状态、甚至是穷举所有状态的基础上，所以算法的正确性比较容易证明。,枚举法的缺点,：,枚举算法的效率取决于枚举状态的数量以及单个状态枚举的代价，因此效率比较低。,二、枚举算法的优化,枚举算法的时间复杂度可以用状态总数*考察单个状态的耗时来表示，因此优化主要是,减少状态总数（即减少枚举变量和枚举变量的值域）,降低单个状态的考察代价,优化过程从几个方面考虑。具体讲,提取有效信息,减少重复计算,将原问题化为更小的问题,根据问题的性质进行截枝,引进其他算法,例4 邮票面值问题,【问题描述】,邮局发行一套票面有四种不同值的邮票，如果每封信所贴邮票张数不超过三枚，存在整数，使得用不超过三枚的邮票，可以贴出连续的整数、，来，找出这四种面值数，使得值最大。,【算法分析】,设四种邮票的面值分别为：,A,B,C,D,，根据题意设：,A B C x0 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;,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,i,j,k,num,m,fac:longint;,a:array1.100 of longint;,begin,assign(output,amsts.out);,rewrite(output);,for i:=100 to 9999999 do 枚举产生3位到7位的数,begin,num:=i;m:=0;m表示位数,while num0 do 分解这个产生的数,begin,m:=m+1;,am:=num mod 10;a数组保存各位上的数字,num:=num div 10;,end;,num:=0;,for j:=1 to m do ,begin,fac:=1;,for k:=1 to m do 表示其中一位的幂,fac:=fac*aj;,num:=num+fac;求各位幂的和,end;,if num=i then writeln(i);,end;,close(output);,end.,例,勾股数,【问题描述】,设三个正整数a、b、c,满足,则称a b c 为一组勾股数。,求所有C=N的勾股数（1000),program l1;勾股数,var n,a,b,c:integer;,function f(a,b:integer):integer;,a2+b2完全平方数判断,var i:integer;,begin,i:=1;,while (a*a+b*bi*i)and(i=n)do inc(i);,if i=n then f:=i else f:=0,end;,【参考程序】,begin,write(n=);readln(n);,for a:=1 to n-2 do,for b:=a+1 to n-1 do,begin,c:=f(a,b);,if c0 then writeln(a,b,c);,end;,readln,end.,