枚举算法

什么是枚举算法？也称穷举法。指从可能的解的集合中一一列举各对象，用题目给定的检验条件判定哪些是无用的，哪些是有用的。满足条件的，即为题目的解。采用枚举算法解题的基本思路：1.确定枚举对象、枚举范围和判定条件2.一一枚举可能的解，验证是否是问题的解。实例精讲【例1】神秘的五位数有一个神秘的五位数，其中第2、3位上的数字已经模糊不清，如下图所示。已知该数为26或48的倍数，请找出所有满足条件的神秘五位数并统计个数。实例精讲题意在[12008,12998]内寻找26或48的倍数，并统计个数。枚举三要素：枚举对象、枚举范围、判断条件枚举对象：五位数枚举范围：12008～12998判断条件：是26或48的倍数程序实现Vari,j,k:integer;beginfori:=12008to12998doif(imod26=0)and(imod48=0)thenbeginwriteln(i);k:=k+1;end;writeln(k);end.orAnd(imod10=8)【例2】一根29cm长的尺子，只允许在上面刻七个刻度，要能用它量出1~29cm的各种长度。[算法分析]从1~29cm中选择七个刻度的数目有：=1560780对于每一组刻度的选择都需要判断是否将1~29cm的各种刻度量出来，例如选择的刻度为：a1,a2,a3,a4,a5,a6,a7，那么能量出的刻度为：C729a1,29-a1a2,a2-a1,29-a2a3,a3-a1,a3-a2,29-a3a4,a4-a1,a4-a2,a4-a3,29-a4a5,a5-a1,a5-a2,a5-a3,a5-a4,29-a5a6,a6-a1,a6-a2,a6-a3,a6-a4,a6-a5,29-a6a7,a7-a1,a7-a2,a7-a3,a7-a4,a7-a5,a7-a6,29-a7从上面的列表国我们可以量出刻度数为：2+3+4+5+6+7+8=35种但其中有些刻度是重复的，不可能刚好覆盖1~29cm。如果找出刻度a1,a2,a3,a4,a5,a6,a7，利用其对称性29-a1,29-a2,a9-a3,a9-a4,a9-a5,29-a6,29-a7,也是一组解假设a1a2a3a4a5a6a7要1,28两种刻度能量出，在七个刻度中必须有：1或28设a1=1，变成了在2~27中选取六个刻度。[参考程序]Constn=29;m=1;Vara:array[1..7]ofinteger;b:array[1..29]of0..1;f:boolean;a1,a2,a3,a4,a5,a6,a7,i,j:integer;begina[1]:=m;fora2:=2ton-7dofora3:=a2+1ton-6dofora4:=a3+1ton-5dofora5:=a4+1ton-4dofora6:=a5+1ton-3dofora7:=a6+1ton-2dobegina[2]:=a2;a[3]:=a3;a[4]:=a4;a[5]:=a5;a[6]:=a6;a[7]:=a7;fori:=1to29dob[i]:=0;fori:=1to7dobeginb[a[i]]:=1;b[n-a[i]]:=1;b[n]:=1;forj:=i+1to7dob[abs(a[j]-a[i])]:=1;end;j:=0;forI:=1tondoj:=j+b[i];ifj=nthenbeginfori:=1to7dobeginwrite(a[i]:4);end;writeln;end;end;end.当m=1时，得到两组刻度：（1,2,14,18,21,24,27）（1,4,10,17,22,24,27）【例3】巧妙填数。将1~9这九个数字填入九个空格中。每一横行的三个数字组成一个三位数。如果要使第二行的三位数是第一行的两倍，第三行的三位数是第一行的三倍，应怎样填数。如下图所示。192384576算法分析本题目有9个格子，要求填数如果不考虑问题给出的条件，共有方案数：9!=362880种方案在这些方案中符合问题条件的即为解但仔细分析问题，显然第一行的数不会超过400，实际上只要确定第一行的数就可以根据条件算出其他两行的数了。这样仅需枚举400次。[参考程序]Vari,j,k,s:integer;functionsum(s:integer):integer;beginsum:=sdiv100+sdiv10mod10+smod10;end;functionmul(s:integer):longint;beginmul:=(sdiv100)*(sdiv10mod10)*(smod10)end;beginfori=1to3doforj:=1to9doifjithenfork:=1to9doif(kj)and(ki)thenbegins:=I*100+j*10+k;if3*s1000thenif(sum(s)+sum(2*s))+sum(3*s)=45and(mul(s)*mul(2*s)*mul(3*s)=362880)thenbeginwriteln(s);writeln(2*s);writeln(3*s);writeln;end;end;end.实例精讲【例4】狐狸捉兔子围绕着山顶有10个洞，一只狐狸和一只兔子住在各自的洞里。狐狸总想吃掉兔子。一天，兔子对狐狸说：“你想吃我有一个条件，先把洞从1～10编上号，你从10号洞出发，先到1号洞找我；第二次隔1个洞找我，第三次隔2个洞找我，以后依此类推，次数不限。若能找到我，你就可以饱餐一顿。不过在没有找到我以前不能停下来。”狐狸满口答应就开始找了，它从早到晚进了1000次洞，累得昏了过去也没找到兔子。请问，兔子躲在几号洞里？算法分析由于本题给出的数字1000不是很大，可以完全采用枚举算法。检验这1000次的进进出出中，哪些是满足条件的。参考程序constn=10;varcave:array[0..n]of0..1;step,i,num:longint;beginfori:=0to9docave[i]:=0;num:=0;forstep:=1to1000dobeginnum:=num+step;i:=nummodn;cave[i]:=1;end;fori:=0ton-1doifcave[i]=0thenwrite(i:3);readln;end.运行结果：2479【例5】一元三次方程求解有形如：ax3+bx2+cx+d=0这样的一个一元三次方程。给出该方程中各项的系数(a，b，c，d均为实数)，并约定该方程存在三个不同实根(根的范围在-100至100之间)，且根与根之差的绝对值=1。要求由小到大依次在同一行输出这三个实根(根与根之间留有空格)，并精确到小数点后2位。提示：记方程f(x)=0，若存在2个数x1和x2，且x1x2，f(x1)*f(x2)0，则在(x1，x2)之间一定有一个根。样例输入：1-5-420输出：-2.002.005.00算法分析根的范围在[-100，100]结果只要保留两位小数因此，将根的值域扩大100倍x为[-10000，10000]枚举对象：根枚举范围：-10000～10000检验条件：原方程成立参考程序Vara,b,c,d:real;i:integer;functionf(x:real):real;beginf:=a*x*x*x+b*x*x+c*x+dend;beginreadln(a,b,c,d);fori:=-10000to10000doifabs(f(i/100))1e-4thenwrite(i/100:2:2,’’);end.【例6】邮票问题邮局发行一套票面有四种不同值的邮票，如果每封信所贴邮票数不超过三枚，存在整数r，使得用不超过三枚的邮票，可以贴出连续的整数1，2，3，…，r来，找了这四种面值数，使得r值最大。算法分析1.面值不同的四种邮票，每封信所贴邮票不超过3张。2.用这四种邮票贴出连续的整数，并且使r值最大。3.用枚举法找出所有符合条件的解。4.本题用集合的方法统计邮票的面值，提高判重的速度。大致算法结构细化后的程序结构rmax:=0;s1:=1;fors2:=2to10dofors3:=3to10dofors4:=4to10dobegin计算r值；ifrrmaxthenbeginrmax:=r;记录对应的S1，S2，S3，S4；end;end;Vara,b,c,d:integer;{各种邮票的可能值}x,x0,x1,x2,x3,x4:integer;st1:setof1..100;functionnumber(a,b,c,d:integer):integer;varn1,n2,n3,n4,sum:integer;beginst1:=[]forn1:=0to3do{每种邮票所取的张数}forn2:=0to3-n1doforn3:=0to3-n1-n2doforn4:=0to3-n1-n2-n3dobeginifn1+n2+n3+n4=3thenbeginsum:=n1*a+n2*b+n3*c+n4*d;st1:=st1+[sum]end;end;sum:=1;whilesuminst1dosum:=sum+1;number:=sum-1;end;begina:=1;x0:=0;forb:=a+1to3*a+1doforc:=b+1to3*b+1doford:=c+1to3*c+1dobeginx:=number(a,b,c,d);ifxx0thenbeginx0:=x;x1:=a;x2:=b;x3:=c:x4=d;write(x1:5,x2:5,x3:5,x4:5);writeln(‘x0’,x0);end;end;end.【例7】数字组合给出N个正整数，在其中找出其和为M的若干个数的组合。先读入正整数N（1N100）和正整数M（1M10000），再读入N个正整数（可以有相同的数字，每个数字均在10000以内），在这N个数中找出若干个使它们的和等于M，把满足条件的数字组合都找出来以统计组合的个数，输出组合的个数（不考虑组合是否相同）。【输入】：第一行是两个整数，表示N和M。第二行起是N个整数。【输出】：就一个数字，表示和为M的组合的个数。【输入样例】441122【样例输出】3算法分析二进制穷举。对每个数，有取或不取两种方法。算法分析vari,j,count,sum,n,m:longint;a,b:array[1..101]ofinteger;beginreadln(n,m);fori:=1tondoread(a[i]);fillchar(b,sizeof(b),0);count:=0;whileb[n+1]1dobegini:=1;while(b[i]=1)and(i=n)doinc(i);b[i]:=1;forj:=1toi-1dob[j]:=0;sum:=0;fori:=1tondoifb[i]=1thensum:=sum+a[i];ifsum=mthencount:=count+1;end;writeln(count);end.【例8】绝对质数一个质数，当它的数字位置对换以后仍为质数，这样的数称为绝对质数。例如11，13…，编程找出所有的两位绝对质数。算法分析使用枚举法对所有两位整数i进行检验，看其是否满足下列二条件：（1）i是质数（2）i的两位数字交换后仍然是质数。为此，设定两个函数：函数prime(a)检验正整数a是否为质数；参考程序：varn:integer;functionprime(a:integer):boolean;{检验正整数a是否为质数}vark:integer;b:boolean;beginifamod2=0thenprime:=falseelsebeginb:=true;k:=3;while(ksqrt(a))andbdobegi