穷举法2010.ppt

1、穷举法,2010曹文信息学奥林匹克夏令营,穷举法概念 穷举的策略是直接基于计算机特点而使用的思维方法，在一时找不到解决问题的更好途径（指从数学上找到求解公式或规则）时，可以根据问题中的部分条件（约束条件）将可能解的情况列举出来，然后一一验证是否符合整个问题的求解要求。,例1：获奖名次,三位老师对参加信息学竞赛的四名学生将获得的名次预测如下： 甲：学生c得第一名，学生d得第四名； 乙：学生a得第一名，学生b得第三名； 丙：学生d得第一名，学生b得第三名； 竞赛结果表明，每位老师都说对了一半，说错了一半。试编写程序排出学生的名次。,例2：分鱼,a,b,c,d,e五人合伙夜间捕鱼，清晨时都疲倦不堪，

2、各自在河边的树丛中找地方睡着了。a第一个醒来，他将鱼平分成五份，把多余的一条扔回河中，拿着自己的一份回家了。b第二个醒来，也将鱼平分成五份，扔掉多余的一条，拿走自己的一份。接着c、d、e依次醒来，也都这样处理。 问：五人至少捕到多少条鱼？ 注：每人拿到的都是整条的鱼,例3：分西瓜,小小询问集市上卖西瓜的农民今天上午卖了几个西瓜，这个农民回答说：我在第一个小时卖出了全部西瓜的1/2又1/2个；第二个小时卖出了剩余的1/3又1/3个；第三个小时卖出了剩余的1/4又1/4个；第四个小时卖出了剩余的1/5又1/5个.最后正好剩余11个西瓜。问：这个农民原来一共有多少个西瓜？,例4：百元买百鸡,百元买百

3、鸡问题 （一只公鸡5元，一只母鸡3元，三只小鸡1元） 讨论多种解法的优劣性,例5：数字分组,19这9个数字平均分成三组，每组组成一个三位数，且使这三个三位数构成1：2：3的比例，试求所有满足条件的三个三位数。例如：192，384，576这三个就满足条件。,例6：阿姆斯特朗数,阿姆斯特朗数也叫水仙花数。 153(153=1*1*1+3*3*3+5*5*5)是一个三位数的阿姆斯特朗数。 如果要求37位的阿姆斯特朗数呢？,例7：锯木棍,长短不一木棍共n根，现要求锯成同样长度，你能求出锯成的最长长度吗？ 方法：最大公约数？穷举？,例8: 勾股数,问题描述 设三个正整数a、b、c,满足 则称a b c

4、为一组勾股数。 求所有C=N的勾股数（1000) 问题分析 算法设计 参考程序,勾股数参考程序,var n,a,b,c:longint; function f(a,b:longint):longint; a2+b2完全平方数判断 var x,y:longint; begin x:=a*a+b*b; y:=trunc(sqrt(x); if (y=n)and(y*y=x) then f:=y 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,

5、b); if c0 then writeln(a, ,b, ,c); end; Readln; end.,例9直尺刻度,问题描述一长厘米的尺子，只允许在上面刻个刻度，就能用它直接量出厘米的长度。求这个刻度的位置。 问题分析 算法设计 参考程序,直尺刻度问题分析,(1) 从 129 厘米中选择七个刻度的所有可能情况数是: C（29，7） = （29*28*27*26*25*24*23）/（1*2*3*4*5*6*7） = 1560780 (2) 对于每一组刻度的选择都需要判断是否能将 129 厘米的各种刻度量出来, 例如选择的刻度为: a1,a2,a3,a4,a5a,6,a7 那么能量出的刻度为

6、： a1, 29-a1; 2 a2, a2-a1, 29-a2; 3 a3, a3-a1 ,a3-a2, 29-a3 ; 4 a4, a4-a1, a4-a2, a4-a3, 29-a4; 5 a5,a5-a1,a5-a2, a5-a3, a5-a4, 29-a5; 6 a6,a6-a1,a6-a2,a6-a3,a6-a4, a6-a5, 29-a6; 7 a7,a7-a1, a7-a2, a7-a2, a7-a3, a7-a4, a7-a5, a7-a6, 29-a7； 8 共可量出 2+3+4+5+6+7+8 种刻度, 即 35 种刻度 。 事实上其中有许多刻度是重复的, 不可能复盖 12

7、9。例如： 取 a1, a2, a3, a4, a5, a6, a7为1, 3, 6, 10, 15, 21, 28 能量出的刻度为：,直尺刻度问题分析,1 , 28 3, 2, 26 6, 5, 3, 23 10, 9, 7, 4, 19 15, 14, 12, 9, 5, 14 21, 20, 18, 15, 11, 6, 8 28, 27, 25, 22, 18, 13, 7, 1 缺 16,17,24 ( 29 即尺子长度 ) 问题的解必须使所有的刻度是否都能量得。 (3)显然要使1,28 两种刻度能量出来, 则在七个刻度就必须有 1 或 28; 这样就可设a1=1 ( 或 a1=28

8、 )。本题就变成了只要在 227 中选取六个刻度问题了。其刻度选择的数目为 C（26，6） = （26*25*24*23*22*21）/（1*2*3*4*5*6）=230230,直尺刻度参考程序1,直尺刻度问题 const n=29;m=1; var a:array1.7 of byte; b:array1.n of 0.1; i,j:byte; begin a1:=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

9、for a7:=a6+1 to n-2 do begin,直尺刻度参考程序2,for i:=1 to n do bi:=0; bn:=1; for i:=1 to 7 do begin bai:=1;bn-ai:=1; for j:=i+1 to 7 do babs(aj-ai):=1; end; j:=0; for i:=1 to n do inc(j,bi); if j=n then begin for i:=1 to 7 do write(ai:4);writeln;end; end;for End.,例10 邮票面值问题,【问题描述】 邮局发行一套票面有四种不同值的邮票，如果每封信所贴

10、邮票张数不超过三枚，存在整数，使得用不超过三枚的邮票，可以贴出连续的整数、，来，找出这四种面值数，使得值最大。 【算法分析】 设四种邮票的面值分别为： 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

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

12、in 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 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:=

13、 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 end end; writeln( x1：5, x2：5, x3：5, x4：10, R=, x0 ); End.,例11：分棋子1,【问题描述】 今有甲、乙、丙三堆棋子，先将甲堆棋子分给另外两堆，使另外两堆棋子数各增加1倍，再把乙堆棋子照这样分配一次，最后把丙堆棋子也这样分配。

14、结果甲堆棋子数是丙堆棋子数的4/5，乙堆棋子数是丙堆棋子数的1又7/15。求三堆中原来的棋子各有多少个？ 【输入】: 无 【输出】: 输出到屏幕。三个整数，分别表示甲、乙、丙堆棋子原来有的数量。,分棋子2,var i,j,k,x,y,z:longint; begin for i:=1 to 1000 do for j:=1 to i do for k:=1 to i do begin x:=i;y:=j;z:=k; x:=x-y-z;y:=y*2;z:=z*2; y:=y-x-z;x:=x*2;z:=z*2; z:=z-x-y;x:=x*2;y:=y*2; if (5*x=4*z)and(15

15、*y=22*z) then begin writeln(i, ,j, ,k);halt;end; end; end.,例12：幂十全数1,【问题描述】 如果一个数包含了09这十个数字，就称为十全数。给定N，找一个最小的正整数M，使NM(表示连续M个N连乘，如23=2*2*2)为十全数。 【输入】: 一个整数，即N(0=N=100)。 【输出】: 输出到屏幕。若无解，输出“No”，否则输出M。 【样例】： 输入1： 4 输出1： 34 输入2： 1 输出2： No,幂十全数2,var a:array0.1000of longint; n,m:longint; procedure mul; 高精度

16、乘法，在原来的基础上再乘以n，是高精度乘以单精度 var i,x:longint; begin for i:=1 to a0 do ai:=ai*n; for i:=1 to a0 do begin ai+1:=ai+1+ai div 10; ai:=ai mod 10; end;,i:=a0+1; x:=ai; while x0 do begin ai:=x mod 10; x:=x div 10; inc(i); end; a0:=i-1; end;,幂十全数3,function check:boolean;检查0-9是否都出现 var s:set of 0.9; i,t:longint;

17、 begin s:=;t:=0;i:=1; while (t10)and(i=a0) do begin if not(ai in s) then begin s:=s+ai;inc(t);end; inc(i); end; if t=10 then check:=true else check:=false; end;,幂十全数4,begin readln(n); if(n=0)or(n=1)or(n=10)or(n=100) then begin writeln(No);halt;end; fillchar(a,sizeof(a),0); a0:=1;a1:=1; m:=0; repeat

18、inc(m); mul; until check; writeln(m); end.,例13： NOIP2009T_2火柴棒等式,【问题描述】 给你n根火柴棍，你可以拼出多少个形如“A+B=C”的等式？等式中的A、B、C是用火柴棍拼出的整数（若该数非零，则最高位不能是0）。用火柴棍拼数字0-9的拼法 如图所示： 注意： 1. 加号与等号各自需要两根火柴棍 2. 如果AB，则A+B=C与B+A=C视为不同的等式（A、B、C=0） 3. n根火柴棍必须全部用上 【输入】共一行，又一个整数n（n=24）。 【输出】共一行，表示能拼成的不同等式的数目。 【输入输出样例1】输入14，输出2 【输入输出样

19、例1解释】2个等式为0+1=1和1+0=1。 【输入输出样例2】输入18输出9 【输入输出样例2解释】 9个等式为： 0+4=4,0+11=11,1+10=11,2+2=4,2+7=9, 4+0=4,7+2=9,10+1=11,11+0=11,火柴棒等式参考程序,const hc:array0.9of longint=(6,2,5,5,4,5,6,3,7,6); var a:array0.2000of longint; i,j,x,n,t:longint; begin readln(n); fillchar(a,sizeof(a),0); a0:=hc0;,for i:=1 to 2000 d

20、o begin x:=i; while x0 do begin inc(ai,hcx mod 10); x:=x div 10; end; end; t:=0; for i:=0 to 1000 do for j:=0 to 1000 do if ai+aj+ai+j=n-4 then inc(t); writeln(t); end.,例14：代数和 问题描述自然数从左到右排列，在相邻两个数之间添加一个“”或“”，使所得式子的代数和等于自 然数。= ,N=16 例如n=5、k=3时，得到下列等式： 任务：输入n k,输出所有符合要求的等式。 问题分析 算法设计 参考程序,代数和参考程序1,1到

21、N的代数和 const maxn=16; type btype=array1.maxn-1 of 0.1; var n,k,i:longint; m:word; b:btype; procedure ntob(n1:longint;var b:btype); 整数化为二进制数 var i:longint; begin fillchar(b,sizeof(b),0);,i:=0; while (i0) do begin inc(i); bi:=n1 mod 2; n1:=n1 div 2; end; end;,代数和参考程序2,function sum(b:btype):longint;求代数和

22、 var i,s:longint; begin s:=1; for i:=n-1 downto 1 do if bi=1 then s:=s+(n-i+1) else s:=s-(n-i+1); sum:=s end;,代数和参考程序3,代数和参考程序4,procedure print(b:btype);输出 var i:longint; begin write(1); for i:=2 to n do if bn-i+1=1 then write(+,i) else write(-,i); writeln(=,k); end;,begin write(n,k=);readln(n,k); f

23、illchar(b,sizeof(b),0); m:=1; for i:=1 to n-1 do m:=m*2; m:=m-1; if sum(b)=k then print(b); for i:=1 to m do begin ntob(i,b); if sum(b)=k then print(b); end; readln end.,代数和参考程序5,根据处理对象状态的构造特点,以及不同状态之间的生成关系,利用简单操作,从当前状态转变为下一个新的状态,实现所有状态的枚举. 例如例14代数和问题中N-1位二进制数b的状态共有 2n-1个,两个相邻的状态可以通过加1或减1的操作实现转变，从最初

24、的000逐个“加1”，依次转变为001、00.10、1110、1111。下面的算法实现从当前的二进制数通过“加1”转变为下一个二进制数。算法描述如下：,构造法简介,Procedure next(var b:btype); Var i,c:longint; Begin c:=1;i:=0; Repeat inc(i);bi:=bi+c; if bi=2 then begin bi:=0; c:=1;end else c:=0; Until c=0; End;,二进制数加1,例15：构造法求N个元素全排列,问题描述N盆不同颜色的鲜花摆成一排，求所有不同的摆法。 问题分析 算法设计 参考程序,构造法

25、求全排列参考程序1,const maxn=9; var x:array1.maxn of byte; n,i,k,l,r,temp:longint; b:boolean; begin write(n=);readln(n); for i:=1 to n do xi:=i; for i:=1 to n do write(xi); writeln; 第一个排列,b:=true; while b do begin k:=n-1; 找最靠右的数字变大的位置 while (k0) and (xkxk+1) do dec(k); if k=0 then b:=false终止 else begin i:=n

26、; while xkxi do dec(i); temp:=xk;xk:=xi;xi:=temp;,构造法求全排列参考程序2,l:=k+1;r:=n; while lr do begin temp:=xl;xl:=xr;xr:=temp; inc(l);dec(r); end; for i:=1 to n do write(xi);writeln; end;else end;while readln end.,构造法求全排列参考程序3,例16：求数组,问题描述 给出任意一个自然数N (N100)，数组满足下列条件： 1.数组元素由各不相同自然数组成； 2.数组元素的最后一个元素必为N； 3.每

27、一个数组元素都不小于它前面一个元素的平方 (第一个元素除外)； 4.数组中包含的元素个数可不相同，但至少要有一个元素。 求符合上述条件的不同数组个数 例如： N=1 有1个 数组 (1) N=5 有4个 数组 (5)、(1，5)、(1，2，5)、(2，5),例17： NOIP2001P_1数的计算,问题描述 我们要求找出具有下列性质数的个数(包含输入的自然数n): 先输入一个自然数n(n=1000),然后对此自然数按照如下方法进行处理: 不作任何处理; 在它的左边加上一个自然数,但该自然数不能超过原数的一半; 加上数后,继续按此规则进行处理,直到不能再加自然数为止. 样例: 输入: 6 满足条

28、件的数为 6 (此部分不必输出) 16 26 126 36 136 输出: 6,数的计算1（未优化）,var n:longint; function ope(x:longint):longint; var s,i:longint; begin s:=1; for i:=1 to x div 2 do s:=s+ope(i); ope:=s; end; begin readln(n); writeln(ope(n); end.,数的计算2（优化）,var n:longint; a:array1.10000of int64; function cacu(x:longint):int64; var

29、i:longint; s:int64; begin if ax0 then cacu:=ax else begin s:=1; for i:=1 to x div 2 do s:=s+cacu(i); ax:=s; cacu:=s; end; end;,begin readln(n); fillchar(a,sizeof(a),0); writeln(cacu(n); close(input);close(output); end.,例18：完全平方数拆分1,【问题描述】 一个整数，如果是另一个整数的平方，那么这个数就被称为完全平方数，如4（=2*2）、36（=6*6）都是完全平方数。现在给你

30、一个数N，要把N拆成某些完全平方数的和，例如：23=1+4+9+9。我们希望N拆成的数越少越好，请你找到这种拆分。 【输入】:一个整数N（n=1000），表示待拆分的数。 【输出】: 输出到屏幕。一个整数，表示N最少可以被拆成几个完全平方数的和。 【样例】： 输入： 23 输出： 4,完全平方数拆分2,var a:array0.40of longint; n,min:longint; procedure initu; 预处理求出小于等于n的完全平方数 var i:longint; begin i:=1; while i*i=n do begin ai:=i*i; inc(i); end; a0:=i-1; end;,完全平方数拆分3,procedure dg(rem,ceng,fen:longint); 递归求解最小份数 var i,gs:longint; begin if fen1 then begin gs:=rem div aceng; for i:=0 to gs do dg(rem-i*aceng,ceng-1,fen+i); end; end;,完全平方数拆分4,begin readln(n); initu; 预处理求出小于等于n的完全平方数 min:=n; dg(n,a0,0);递归求解最小份数 w