当前位置:首页 >> 学科竞赛 >>

枚举算法_图文

什么是枚举算法?
?
?

? ? ?

也称穷举法。 指从可能的解的集合中一一列举各对象,用题 目给定的检验条件判定哪些是无用的,哪些是 有用的。满足条件的,即为题目的解。 采用枚举算法解题的基本思路: 1.确定枚举对象、枚举范围和判定条件 2.一一枚举可能的解,验证是否是问题的解。

实例精讲
【例1】神秘的五位数 ? 有一个神秘的五位数,其中第2、3位上的 数字已经模糊不清,如下图所示。已知该 数为26或48的倍数,请找出所有满足条件 的神秘五位数并统计个数。
?

实例精讲
题意 ? 在[12008,12998]内寻找26或48的倍数 ,并统计个数。 ? 枚举三要素:枚举对象、枚举范围、判断 条件 ? 枚举对象:五位数 ? 枚举范围:12008~12998 ? 判断条件: 是26或48的倍数
?

程序实现
Var i,j,k:integer; And (i mod 10=8) begin for i:=12008 to 12998 do if (i mod 26=0) and (i mod 48=0) then begin or writeln(i); k:=k+1; end; writeln(k); end.

【例2】一根29cm长的尺子,只允许在上面刻 七个刻度,要能用它量出1~29cm的各种长度。
[算法分析] 从1~29cm中选择七个刻度的数目有: C =1560780 对于每一组刻度的选择都需要判断是否将1~29cm的各种刻 度量出来,例如选择的刻度为:a1,a2,a3,a4,a5,a6,a7, 那么能量出的刻度为: a1,29-a1 a2,a2-a1,29-a2 a3,a3-a1,a3-a2,29-a3 a4,a4-a1,a4-a2,a4-a3,29-a4 a5,a5-a1,a5-a2,a5-a3,a5-a4,29-a5 a6,a6-a1,a6-a2,a6-a3,a6-a4,a6-a5,29-a6 a7,a7-a1,a7-a2,a7-a3,a7-a4,a7-a5,a7-a6,29-a7
7 29

?

?
?

?

?

? ? ? ?

从上面的列表国我们可以量出刻度数为: 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,29a7,也是一组解 假设a1<a2<a3<a4<a5<a6<a7 要1,28两种刻度能量出,在七个刻度中必须有: 1或28 设a1=1,变成了在2~27中选取六个刻度。

[参考程序] Const n=29;m=1; Var a:array[1..7] of integer; b:array[1..29] of 0..1; f:boolean; a1,a2,a3,a4,a5,a6,a7,i,j:integer; begin a[1]:=m; for a2:=2 to n-7 do for a3:=a2+1 to n-6 do for a4:=a3+1 to n-5 do for a5:=a4+1 to n-4 do for a6:=a5+1 to n-3 do for a7:=a6+1 to n-2 do begin a[2]:=a2;a[3]:=a3;a[4]:=a4;a[5]:=a5;a[6]:=a6;a[7]:=a7; for i:=1 to 29 do b[i]:=0; for i:=1 to 7 do begin b[a[i]]:=1;b[n-a[i]]:=1;b[n]:=1; for j:=i+1 to 7 do b[abs(a[j]-a[i])]:=1; end; j:=0; for I:=1 to n do j:=j+b[i]; if j=n then begin for i:=1 to 7 do begin write(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这九个数字填入九个空格中。每一横行的三个数字 组成一个三位数。如果要使第二行的三位数是第一行的两 倍,第三行的三位数是第一行的三倍,应怎样填数。如下 图所示。

1 3 5

9 8 7

2 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 begin writeln(s);writeln(2*s);writeln(3*s);writeln; end; end; end.

实例精讲
?
?

【例4】狐狸捉兔子 围绕着山顶有10个洞,一只狐狸和一只兔子住 在各自的洞里。狐狸总想吃掉兔子。一天,兔子 对狐狸说:“你想吃我有一个条件,先把洞从1 ~10编上号,你从10号洞出发,先到1号洞找我 ;第二次隔1个洞找我,第三次隔2个洞找我, 以后依此类推,次数不限。若能找到我,你就可 以饱餐一顿。不过在没有找到我以前不能停下来 。”狐狸满口答应就开始找了,它从早到晚进了 1000次洞,累得昏了过去也没找到兔子。请问 ,兔子躲在几号洞里?

算法分析
?

?

由于本题给出的数字1000不是很大,可 以完全采用枚举算法。 检验这1000次的进进出出中,哪些是满 足条件的。

参考程序
const n=10; var cave:array[0..n] of 0..1; step,i,num:longint; begin for i:=0 to 9 do cave[i]:=0; num:=0; for step:=1 to 1000 do begin num:=num+step; i:=num mod n; cave[i]:=1; end; for i:=0 to n-1 do if cave[i]=0 then write(i:3); readln; end. 运行结果:2 4 7 9

【例5】一元三次方程求解
?

?

? ? ?

有形如:ax3+bx2+cx+d=0 这样的一个一元三次方程。给出 该方程中各项的系数(a,b,c,d 均为实数),并约定该 方程存在三个不同实根(根的范围在-100至100之间),且 根与根之差的绝对值>=1。要求由小到大依次在同一行输 出这三个实根(根与根之间留有空格),并精确到小数点后 2位。 提示:记方程f(x)=0,若存在2个数x1和x2,且x1<x2, f(x1)*f(x2)<0,则在(x1,x2)之间一定有一个 根。 样例 输入:1 -5 -4 20 输出:-2.00 2.00 5.00

算法分析
?
? ?

?
? ? ?

根的范围在[-100,100] 结果只要保留两位小数 因此,将根的值域扩大100倍 x为[-10000,10000] 枚举对象:根 枚举范围:-10000 ~ 10000 检验条件:原方程成立

参考程序
Var a,b,c,d:real; i:integer; function f(x:real):real; begin f:=a*x*x*x+b*x*x+c*x+d end; begin readln(a,b,c,d); for i:=-10000 to 10000 do if abs(f(i/100))<1e-4 then write(i/100:2:2,’’); end.

【例6】邮票问题
?

邮局发行一套票面有四种不同值的邮票, 如果每封信所贴邮票数不超过三枚,存在 整数r,使得用不超过三枚的邮票,可以 贴出连续的整数1,2,3,…,r来,找 了这四种面值数,使得r值最大。

算法分析
?
? ? ?

1.面值不同的四种邮票,每封信所贴邮票不 超过3张。 2.用这四种邮票贴出连续的整数,并且使r值 最大。 3.用枚举法找出所有符合条件的解。 4.本题用集合的方法统计邮票的面值,提高 判重的速度。

大致算法结构

细化后的程序结构
rmax:=0;s1:=1; for s2:=2 to 10 do for s3:=3 to 10 do for s4:=4 to 10 do begin 计算r值; if r>rmax then begin rmax:=r;记录对应的S1,S2,S3,S4; end; end;

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-n1 do for n3:=0 to 3-n1-n2 do for n4:=0 to 3-n1-n2-n3 do begin if n1+n2+n3+n4<=3 then begin sum:=n1*a+n2*b+n3*c+n4*d; st1:=st1+[sum] end; end; sum:=1; while sum in st1 do sum:=sum+1; number:=sum-1; end;

begin a:=1;x0:=0; for b:=a+1to 3*a+1 do for c:=b+1 to 3*b+1 do for d:=c+1 to 3*c+1 do begin x:=number(a,b,c,d); if x>x0 then begin x0:=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(1<N<100)和正整数M(1<M<10000),再读入N个 正整数(可以有相同的数字,每个数字均在10000以内),在这N 个数中找出若干个使它们的和等于M,把满足条件的数字组合都找出 来以统计组合的个数,输出组合的个数(不考虑组合是否相同)。 【输入】: 第一行是两个整数,表示N和M。 第二行起是N个整数。 【输出】: 就一个数字,表示和为M的组合的个数。 【输入样例】 4 4 1 1 2 2 【样例输出】 3

算法分析
?
?

二进制穷举。 对每个数,有取或不取两种方法。

算法分析
var i,j,count,sum,n,m:longint; a,b:array[1..101] of integer; begin readln(n,m); for i:=1 to n do read(a[i]); fillchar(b,sizeof(b),0); count:=0; while b[n+1]<>1 do begin i:=1; while (b[i]=1) and (i<=n) do inc(i); b[i]:=1; for j:=1 to i-1 do b[j]:=0; sum:=0; for i:=1 to n do if b[i]=1 then sum:=sum+a[i]; if sum=m then count:=count+1; end; writeln(count); end.

【例8】绝对质数
一个质数,当它的数字位置对换以后仍为质数,这样的 数称为绝对质数。例如11,13…,编程找出所有的两位 绝对质数。

算法分析
?

? ? ?

使用枚举法对所有两位整数i进行检验,看其是否满足 下列二条件: (1)i是质数 (2)i的两位数字交换后仍然是质数。 为此,设定两个函数:函数prime(a)检验正整数a是否 为质数;

参考程序: var n:integer; function prime(a:integer):boolean; {检验正整数a是否为质数} var k:integer; b:boolean; begin if a mod 2=0 then prime:=false else begin b:=true;k:=3; while (k<sqrt(a)) and b do begin if a mod k=0 then b:=false;k:=k+2; end; prime:=b; end; end.; function inv(a:integer):integer; {将a的两位数字交换} var i,j:integer; begin i:=a div 10;j:=a mod 10;inv:=j*10+i; end; begin for n:=11 to 97 do if prime(n) and prime(inv(n)) then write(n:4); end.