Pascal 穷举.ppt

1、穷举法,2008夏令营,执教：江苏省丹阳高级中学 荆晓虹,一、引入,实例一：编一个程序找出三位数到七位数中所有的阿姆斯特朗数。阿姆斯特朗数也叫水仙花数,它的定义如下:若一个n位自然数的各位数字的n次方之和等于它本身,则称这个自然数为阿姆斯特朗数。例如153(153=1*1*1+3*3*3+5*5*5)是一个三位数的阿姆斯特朗数,8208则是一个四位数的阿姆斯特朗数。,穷举法,算法分析：程序只能采用穷举法,一一验证范围内的数是否阿姆斯特朗数,若是则打印之。,一、引入,算法描述： for I:=100 to 9999999 do begin 验证是否是阿姆斯特朗数，若是则输出； end;,穷举法,

2、一、引入,实例二：从键盘输入一个正整数N，验证其是否为质数，若是则输出“YES”，否则输出“NO”。,穷举法,算法分析：程序采用穷举法,一一验证范围内的数是否是N的因子,若是做标记。,一、引入,算法描述： Read(n); for I:=2 to n-1 do begin 验证i是否是n的因子，若是则做标记； end;,穷举法,二、穷举法的基本概念,穷举法,穷举方法是基于计算机特点而进行解题的思维方法。穷举算法特点是算法简单，但运行时所花费的时间量大。因此，我们在用穷举方法解决问题时，应尽可能将明显的不符合条件的情况排除在外，以尽快取得问题的解。,根据问题中的的部分条件（约束条件）将所有可能解

3、 的情况列举出来，然后通过一 一验证是否符合整个 问题的求解要求，而得到问题的解。,三、穷举算法模式,穷举法,1、问题解的可能搜索范围：用循环或循环嵌套结构实现,3、能使程序优化的语句，以便缩小搜索范 围，减少程序运行时间。,for I:=100 to 9999999 do,2、写出符合问题解的条件。,for I:=2 to n-1 do,四、穷举法应用,穷举法,穷举法应用很多，比如一些密码破译软件通常就是用的穷举算法。如在QQ上，OicqPassOver这个工具穷举你的口令，它根据机器性能最高可以每秒测试20000个口令，如果口令简单，一分钟内，密码就会遭到破译。下面我们来以两个例子说明穷举

4、法的基本应用。,实例二：有形如：ax3+bx2+cx+d=0 这样的一个一元三次方程。给出该方程中各项的系数(a，b，c，d 均为实数)，并约定该方程存在三个不同实根(根的范围在-100至100之间)，且根与根之差的绝对值=1。要求由小到大依次在同一行输出这三个实根(根与根之间留有空格)，并精确到小数点后2位。 样例 输入：1 -5 -4 20 输出：-2.00 2.00 5.00,四、穷举法应用,本题是2001年全国信息学奥林匹克竞赛高中组复赛第一题，如果考虑解方程的话则比较麻烦。我们可以换个角度思考问题，在-100到100之间找三个满足方程的实数，由于穷举时必须用整型变量，题目又要求保留两

5、位小数，我们只需将循环变量扩大100倍即可顺利穷举，最后只要将所求结果再缩小100倍即可。,四、穷举法应用,程序如下： Var a,b,c,d,x:real; i,x1,x2,x3:Integer; Begin Read(a,b,c,d); x1:=MaxInt; x2:=x1; x3:=x1;,四、穷举法应用,For i:=-10000 To 10000 Do Begin x:=i/100; If Then If ix1 Then x1:=i Else If ix2 Then x2:=i Else If ix3 Then x3:=i;确保x1x23 End; Writeln(x1/100:0

6、:2, ,x2/100:0:2, ,x3/100:0:2); End.,四、穷举法应用,Abs(a*x*x*x+b*x*x+c*x+d)0.000001,四、穷举法应用,穷举法,实例三：学校名次。 问题描述：有A，B，C，D，E5所学校。在一次检查评比中，已知E校肯定不是第2名或第3名，他们互相进行推测。A校有人说，E校一定是第1名；B校有人说，我校可能是第2名；C校有人说，A校最差；D校有人说，C校不是最好的；E校有人说，D校会获第1名。结果只有第1名和第2名学校的人猜对了。编程指出这5所学校的名次。,四、穷举法应用,穷举法,分析：本题是一个逻辑判断题，一般的逻辑判断题都采用穷举法进行解决。

7、我们对5所学校所得名次的各种可能情况进行穷举。在每种情况中，为了防止不同学校取相同的名次，设立了逻辑数组x，xI为false表示已有某校取第I名。 此题的难点在于确定判断条件。我们设立逻辑变量b0来描述这一条件，主要有两个条件：“E校不是第2名或第3名”与“只有第1名和第2名的学校的人猜对”，后一条件要判断：1）是否只有两人说法正确？2）说得正确的人是否是取得第1名和第2名的学校的人？要判断是否仅有两人说正确，须统计正确命题的个数。为此，设立了函数bton，将逻辑量数值化。,四、穷举法应用,穷举法,程序： program l3(output); var i,a,b,c,d,e,m:intege

8、r; x:array1.5 of boolean; b0,b1:boolean; function bton(b:boolean):integer; begin if b then bton:=-1 else bton:=0 end;,四、穷举法应用,穷举法,begin for i:=1 to 5 do xi:=true; for a:=1 to 5 do begin xa:=false; for b:=1 to 5 do if xb then begin xb:=false; for c:=1 to 5 do if xc then begin xc:=false; for d:=1 to 5

9、 do if xd then,四、穷举法应用,穷举法,begin e:=15-a-b-c-d;b0:=(e2) and (e3); m:=bton(e=1)+bton(b=2)+bton(a=5)+bton(c1)+bton(d=1); b0:=b0 and (m=-2); b1:=(e=1) and (a2); b1:=b1 or (a=5) and(c1) and(c2); b1:=b1 or (c1) and (d1) and (d2); b1:=b1 or (d=1) and (e2); b0:= ; if b0 then writeln(a=,a:2, b=,b:2, c=,c:2,

10、 d=,d:2, e=,e:2); xd:=true; end;,b0 and not b1,四、穷举法应用,穷举法,xc:=true; end; xb:=true; end; xa:=true; end; end. 运行结果： a=5 b=2 c=1 d=3 e=4,穷举法,实例四：阿姆斯特朗数。 问题描述：编一个程序找出所有的三位数到七位数中的阿姆斯特朗数。 阿姆斯特朗数也叫水仙花数,它的定义如下:若一个n位自然数的各位数字的n次方之和等于它本身,则称这个自然数为阿姆斯特朗数。例如153(153=1*1*1+3*3*3+5*5*5)是一个三位数的阿姆斯特朗数,8208则是一个四位数的阿姆斯

11、特朗数。,五、如何优化穷举算法,穷举法,算法分析： 为了使得程序尽快运行出正确结果,程序中使用了一个数组power存放所有数字的各次幂之值, poweri,j等于i的j次方。变量currentnumber存放当前要被验证的数,数组digit存放当前数的各位数字,开始时digit3=1,其它元素均为0,此时表示当前数为100。 highest为当前数的位数。,五、如何优化穷举算法,穷举法,程序： program ex3(input,outoutp); const maxlen=7; var i,j,currentnumber,highest,sum,total:longint; digit:ar

12、ray 0.maxlen+1 of integer; power:array 0.9,0.maxlen of longint; begin for i:=0 to 9 do begin poweri,0:=1; for j:=1 to maxlen do poweri,j:=poweri,j-1*i end;,五、如何优化穷举算法,穷举法,for i:=1 to maxlen do digiti:=0; digit3:=1; highest:=3; currentnumber:=100; total:=0; while digitmaxlen+1=0 do begin sum:=0; for

13、i:=1 to highest do sum:=sum+powerdigiti,highest; if sum=currentnumber then begin total:=total+1; write(currentnumber:maxlen+5); if total mod 6=0 then writeln end;,五、如何优化穷举算法,穷举法,i:=1; while digiti=10 do begin digiti+1:=digiti+1+1; digiti:=0; i:=i+1 end; if ihighest then highest:=i; ( ) end; writeln

14、end.,digit1:=digit1+1;,currentnumber:=currentnumber+1,五、如何优化穷举算法,穷举法,优化策略一：算法中的时间和空间往往是矛盾的，时间复杂性和空间复杂性在一定条件下也是可以相互转化的,有时候为了提高程序运行的速度,在算法的空间要求不苛刻的前提下,设计算法时可考虑充分利用有限的剩余空间来存储程序中反复要计算的数据,这就是“用空间换时间”策略,是优化程序的一种常用方法。,五、如何优化穷举算法,穷举法,实例五：邮票面值。 问题描述：邮局发行一套票面有四种不同值的邮票，如果每封信所贴邮票张数不超过三枚，存在整数，使得用不超过三枚的邮票，可以贴出连续的

15、整数、，来，找出这四种面值数，使得值最大。,五、如何优化穷举算法,穷举法,分析： 本题知道每封信邮票数的范围（=3 ）,邮票有四种类型，编程找出能使面值最大邮票。其算法是：,(1) 面值不同的四种邮票，每封信所贴邮票不超过 3 张。 (2) 用这四种邮票贴出连序的整数，并且使值最大。 (3) 用穷举法，找出所有符合条件的解。 (4) 本题用集合的方法统计邮票面值，提高判重的速度。 设四种邮票的面值分别为： A , B , C , D ，根据题意设： A B C D，因此 A=1 ，用循环语句完成搜索。,五、如何优化穷举算法,穷举法,Program p12_3 ; var a, b , c ,

16、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,五、如何优化穷举算法,穷举法,i

17、f 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 main x0:=0 ; for b:= to do for c:= to do 每种邮票的可取值的范围 for d:= to do begin x:= number (a, b, c, d ); 调用函数求每封信的邮票总面值 if x x

18、0 then begin x0:=x; x1:=a ; x2:=b ; x3:=c ; x4:=d 保存最大面值邮票 write( x1：5, x2：5, x3：5, x4：5 ); writeln( :10, x0=, x0 );end;end; end.,a+1,3*a+1,b+1,3*b+1,c+1,3*c+1,a:=1 ;,五、如何优化穷举算法,穷举法,程序运行后，其输出结果是： 解答结果有11 组 1 2 3 4 x0=12 1 2 3 5 x0=13 . 1 3 6 10 x0=23 1 4 7 8 x0=24,五、如何优化穷举算法,穷举法,优化思路二：减少穷举的变量，在使用穷举算

19、法之前，先考虑一下解元素之间的关联，将一些非穷举不可的解元素列为穷举变量，其他元素通过计算和分析得出解元素的可能值。,优化思路三： 减少穷举变量的值域，通过和穷举变量间的数 学关系定义解元素的值域。,五、如何优化穷举算法,穷举法,实例六：方格填数。 问题描述：如图所示的8个格子中放入18八个数字，使得相邻的和对角线的数字之差不为1。编程找出所有放法。,五、如何优化穷举算法,穷举法,分析：我们先不考虑后一条件，只考虑第一个条件，即把18八个数字放入8个格子中。这是容易做到的，就是8个数字的全排列，共有8!=40320种放法。然后对这8!个可行解用后一个条件加以检验，输出符合条件的解。对于后一个条

20、件中“相邻”的判断，可以建立一个邻接表来解决：,五、如何优化穷举算法,穷举法,表中表示哪两个格子是相邻的，linki,1和linki,2是相 邻的格子的编号。全排列的产生，可以用八重循环，也可 以用专门的算法，程序留给同学们自己去完成。利用穷举 策略编制的程序，其运算量一般是很大的，因此如何提高 算法效率是穷举算法一个很重要的问题。一般应尽量减少 可行解的个数，使得第二步的检验运算量尽可能地少。,如何来优化算法呢?,五、如何优化穷举算法,穷举法,如果注意到b3和b6两个格子，与它们“相邻”的格子有6个，也就是说，放入这两个格子中的数，必须和6个数不连续，仅可以和一个数是连续的，这样的数只有2个

21、，即1和8。这样，b1，b3，b6，b8；4个格子中数的放法仅有两种可能：2、8、1、7和7、1、8、2。而b2、b4、b5、b7四个格子中的数仅需在36四个数中选择。经过上述优化，可行解仅有：24！48个，大大减少了计算量。并且检验是否符合要求，也只需检查(1，2)，(1，4)，(2，5)，(4，7)，(5，8)，(7，8)这6对数之差就可以了。,五、如何优化穷举算法,穷举法,program exampleb; const link:array1.6,1.2 of integer= (1,2),(1,4),(2,5),(4,7),(5,8),(7,8); var b:array1.8 of

22、integer; procedure print; begin writeln( ,b1:2); writeln(b2:2,b3:2,b4:2); writeln(b5:2,b6:2,b7:2); writeln( ,b8:2) end;,五、如何优化穷举算法,穷举法,function choose:boolean; var i: integer; begin choose:= false; for i:=1 to 6 do if then exit; choose := true end;,abs(blinki, 1 - blinki ,2) = 1,五、如何优化穷举算法,穷举法,proce

23、dure try; begin for b2:=3 to 6 do for b4:= 3 to 6 do if then for b5:= 3 to 6 do if then begin b7:= 18 - b2 - b4 - b5; if choose then print; end; end;,b2b4,(b5b2) and (b5b4),五、如何优化穷举算法,穷举法,begin b1:=2;b3:=8;b6:= 1;b8:=7; try; b1:=7;b3:=1 ;b6:=8;b8:=2; try; readln end.,五、如何优化穷举算法,穷举法,优化思路四：分解约束条件，将拆分的

24、约束条件嵌套在相应的循环体间，尽可能减少可行解的数目，也称为“剪枝”，即把明显不符合条件的可行解尽可能地剪去，减少穷举的计算量。,五、如何优化穷举算法,六、穷举算法的代码实现方法：,实例七：4皇后问题。 问题描述：在44的棋盘上安置4个皇后，要求任意两个皇后不在同一行、不在同一列、不在同一对角线上，输出所有的方案。,穷举法,分析： 1） 本题是一个搜索问题，搜索范围 44，找出符合条件的方案； 2）方案必须满足的条件：任意两个不在同一行、同一列和同一对角线。,六、穷举算法的代码实现方法：,穷举法,方法一程序： const n=4; type stack=array1.n of integer;

25、 var i1,i2,i3,i4:integer; s:stack; function check:boolean; var i,j:integer; begin for i:=1 to n-1 do for j:=i+1 to n do if (si=sj) or (si-i=sj-j) or (si+i=sj+j) then begin check:=false; exit end; check:=true end;,六、穷举算法的代码实现方法：,穷举法,procedure print; var i:integer; begin for i:=1 to n do write(si:2);

26、writeln end; begin for i1:=1 to n do for i2:=1 to n do for i3:=1 to n do for i4:=1 to n do begin s1:=i1;s2:=i2;s3:=i3;s4:=i4; if check then print; end; end.,穷举法,方法二程序： const n=4; type stack=array1.n of integer; var i1,i2,i3,i4:integer; s:stack; function check:boolean; var i,j:integer; begin for i:=1

27、 to n-1 do for j:=i+1 to n do if (si=sj) or (si-i=sj-j) or (si+i=sj+j) then begin check:=false; exit end; check:=true end;,六、穷举算法的代码实现方法：,procedure print; var i:integer; begin for i:=1 to n do write(si:2); writeln end; begin while s0=1 do begin j:=n; while (sj=4) doj:=j-1; sj:=sj+1; forI:=j+1tondo s

28、I：=1; if check then print; end; end.,穷举法,穷举法,方法三程序： const n=8; type stack=array1.n of integer; var count:integer; s:stack; function check:boolean; var i,j:integer; begin for i:=1 to n-1 do for j:=i+1 to n do if (si=sj) or (si-i=sj-j) or (si+i=sj+j) then begin check:=false; exit end; check:=true end;

29、,六、穷举算法的代码实现方法：,procedure print; var i:integer; begin for i:=1 to n do write(si:2); writeln end; procedure search(k: integer); var i:integer; begin if k n then begin if check then begin count:=count+1;print;end; end else for i := 1 to n do begin sk := i; search(k+1); end end; begin count := 0; searc

30、h(1);write(count); end.,穷举法,方法四程序： const n=8; type stack=array0.n of integer; var top,count:integer; s:stack; function check:boolean; var i,j:integer; begin for i:=1 to n-1 do for j:=i+1 to n do if (si=sj) or (si-i=sj-j) or (si+i=sj+j) then begin check:=false; exit end; check:=true end;,六、穷举算法的代码实现方

31、法：,begin fillchar(s,sizeof(s),0); count:=0;top:=1; repeat inc(stop); if stop=n then if top=n then begin if check then begin stop:=0;dec(top); count:=count+1; end end else inc(top) else begin stop:=0;dec(top);end; until top=0; write(count); end.,七、实例分析：,穷举法,实例八：巧妙填数。 问题描述：将19这九个数字填入九个空格中。每一横行的三个数字组成一

32、个三位数。如果要使第二行的三位数是第一行的两倍，第三行的三位数是第一行的三倍，应怎样填数。如图所示。,七、实例分析：,穷举法,分析：本题目有9个格子，要求填数，如果不考虑问题给出的条件，共有9！=362880种方案，在这些方案中符合问题条件的即为解。因此可以采用穷举法。,但仔细分析问题，显然第一行的数不会超过400，实际上只要确定第一行的数就可以根据条件算出其他两行的数了。这样仅需穷举400次。,七、实例分析：,穷举法,program ex_8(input,output); var i,j,k,s:integer; function sum(s:integer):integer; begin

33、sum:=s div 100+s div 10 mod 10+s mod 10 end;sum function mul(s:integer):longint; begin mul:=(s div 100)*(s div 10 mod 10)*(s mod 10) end;mul,七、实例分析：,穷举法,Begin for i:=1 to 3 do for j:=1 to 9 do if ji then for k:=1 to 9 do if (kj) and (ki) then begin s:=i*100+j*10+k; if 3*s1000 then if (sum(s)+sum(2*s

34、)+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.,实例九：数塔问题 问题描述：有形如下图所示的数塔，从顶部出发，在每一结点可以选择向左走或是向右走，一直走到底层，要求找出一条路径，使路径上的数值的和最接近零。,七、实例分析：,输入数据： 输入文件是numbertap.dat。该文件有若干行，第一行是一个正整数n(n=20)，下面共有n行整数，每行整数的个数依次是1，2，n个，行首行末无多余空格。

35、并且每个数字的绝对值不超过1000000。 输出数据： 输出文件是numbertap.out。文件输出一行，代表最接近零数值的绝对值。,七、实例分析：,const n=4; type stack=array0.n of integer; var i,j,k,sum,min:integer; s:stack; a:array1.n,1.n of integer; begin for i:=0 to n do si:=0; for i:=1 to n do for j:=1 to i do begin read(ai,j);end; min:=10000;,while do begin j:=n;

36、 while (sj=1) do j:=j-1; ; for I:=j+1 to n do ; k:=1;sum:=0; for i:=1 to n do begin ; sum:=sum+aI,k; write(ai,k,sum);readln; end; if abs(sum)abs(min) then min:=sum; end; end.,s1=0,sj:=sj+1,sI:=0,k:=k+si,实例十：选数 问题描述：已知n（1=n=20）个整数x1,x2,xn（1=xi=5000000），以及一个整数k（kn）。从n个整数中任选k个整数相加，可分别得到一系列的和。现在，要求你计算出和

37、为素数共有多少种。,七、实例分析：,本题无数学公式可寻，11)是否为素数最简单的方法就是看是否存在一个素数a(a=sqrt(P)是P的约数，如果不存在，该数就为素数，由于在此题中1=xi=5000000,n=20,所以要判断的数P不会超过100000000，sqrt(p)=10000，因此，为了加快速度，我们可以用筛选法将210000之间的素数保存到一个数组里（共1229个），这样速度估计将提高好几倍。,穷举法小结:,穷举法,穷举算法从本质上说，它是一种搜索算法。适合穷举策略求解的问题，首先必须满足其问题规模和可能解的规模（个数）不是特别大，且解变量的值的变化具有一定的规律性。,实际应用中，许

38、多复杂问题的求解策略不止使用一种算法，穷举算法在这类问题的求解过程中起到相当关键的作用。如圆桌骑士问题。,由于穷举算法运行时所花费的时间量大，应对它尽可能进行优化，提高效率。,圆桌骑士问题:,穷举法,很多世纪以前，阿瑟王和他的圆桌武士常在每年元旦聚会庆祝他们的友谊。我们用一个单人玩的棋盘游戏去纪念这个史实：一个国王和多个武士被随机放在8X8的正方形棋盘的不同方格上。只要不越出棋盘，国王可以移至与之相邻的方格内，只要不越出棋盘，武士可以跳日字，在棋局当中，选手可以在同一方格内摆放多个棋子，选手的目标是在尽可能少的步数内把所有的棋子集中到同一方格。为此，他必须按前述方法去移动棋子。此外，当国王和一个或多个武士位于同一方格内时，选手可以选择此后让国王跟随其中一个武士一同向聚会终点移动，就象移动单个武士一样。任务：写出一个程序去计算选手要实现聚会所需最少的移动次数。,圆桌骑士问题:,穷举法,*为国王，图示国王所有可能的移动,A B C D E F G H,1 2 3 4 5 6 7 8,