2013教科版选修1《穷举法》ppt课件

1、穷举法 一、引入实例一：输入绳子的长度实例一：输入绳子的长度n n，将该绳子分成三段，将该绳子分成三段，每段的长度为正整数，输出由该三段绳子组成的每段的长度为正整数，输出由该三段绳子组成的三角形个数。三角形个数。 一、引入s:=0;s:=0;for a:=1 to n-2 dofor a:=1 to n-2 do for b:=a to n-2 do for b:=a to n-2 do for c:=b to n-2 do for c:=b to n-2 do if (a+bc) and (b+ca) and (c+ab) and if (a+bc) and (b+ca) and (c+ab

2、) and (a+b+c(a+b+c=n) =n) then s:=s+1; then s:=s+1;s:=0;s:=0;for a:=1 to n-2 dofor a:=1 to n-2 do for b:=a to n-2 do for b:=a to n-2 do begin begin c:=n-a-b c:=n-a-b; ; if (a+bc) and (b+ca) and (c+a if (a+bc) and (b+ca) and (c+ab) b) and (c=b) and (c=b) then s:=s+1; then s:=s+1; end; end; 一、引入二、穷举法的

3、基本概念 三、穷举算法模式 1、问题解的可能搜索的范围：问题解的可能搜索的范围： 用循环或循环嵌套结构实现用循环或循环嵌套结构实现 2、写出符合问题解的条件。写出符合问题解的条件。 3、能使程序优化的语句，以便缩小搜索范能使程序优化的语句，以便缩小搜索范 围，减少程序运行时间。围，减少程序运行时间。 四、穷举法应用 穷举法应用很多，比如一些密码破译软件通穷举法应用很多，比如一些密码破译软件通常就是用的穷举算法。如在常就是用的穷举算法。如在QQQQ上，上，OicqPassOverOicqPassOver这个工具穷举你的口令，它根这个工具穷举你的口令，它根据机器性能最高可以每秒测试据机器性能最高可

4、以每秒测试2000020000个口令，个口令，如果口令简单，一分钟内，密码就会遭到破如果口令简单，一分钟内，密码就会遭到破译。下面我们来以三个例子说明穷举法的基译。下面我们来以三个例子说明穷举法的基本应用。本应用。 实例二：有形如：实例二：有形如：ax3+bx2+cx+d=0这样的一个一这样的一个一元三次方程。给出该方程中各项的系数元三次方程。给出该方程中各项的系数(a，b，c，d均为实数均为实数)，并约定该方程存在三个不同实根，并约定该方程存在三个不同实根(根的范围在根的范围在-100至至100之间之间)，且根与根之差的绝，且根与根之差的绝对值对值=1。要求由小到大依次在同一行输出这三。要求

5、由小到大依次在同一行输出这三个实根个实根(根与根之间留有空格根与根之间留有空格)，并精确到小数点，并精确到小数点后后2位。位。提示：记方程提示：记方程f(x)=0，若存在，若存在2个数个数x1和和x2，且，且x1x2，f(x1)*(x2)0，则在，则在(x1，x2)之间一定有之间一定有一个一个根。根。样例样例输入：输入：1-5-420输出：输出：-2.002.005.00四、穷举法应用 本题是本题是2001年全国信息学奥林匹克竞赛高中组复年全国信息学奥林匹克竞赛高中组复赛第一题，如果考虑解方程的话则比较麻烦。我赛第一题，如果考虑解方程的话则比较麻烦。我们可以换个角度思考问题，在们可以换个角度思

6、考问题，在-100到到100之间找之间找三个满足方程的实数，由于穷举时必须用整型变三个满足方程的实数，由于穷举时必须用整型变量，题目又要求保留两位小数，我们只需将循环量，题目又要求保留两位小数，我们只需将循环变量扩大变量扩大100倍即可顺利穷举，最后只要将所求倍即可顺利穷举，最后只要将所求结果再缩小结果再缩小100倍即可。倍即可。四、穷举法应用 程序如下：程序如下：VarVar a,b,c,d,x:real a,b,c,d,x:real; ; i,x1,x2,x3:Integer; i,x1,x2,x3:Integer;BeginBegin Read(a,b,c,d Read(a,b,c,d)

7、;); x1:=MaxInt x1:=MaxInt; ; x2:=x1; x2:=x1; x3:=x1; x3:=x1;四、穷举法应用 For i:=-10000 To 10000 DoFor i:=-10000 To 10000 Do Begin Begin x:=i/100; x:=i/100; If Abs(a If Abs(a* *x x* *x x* *x+bx+b* *x x* *x+cx+c* *x+dx+d)0.000001 )0.000001 ThenThen If ix1 Then x1:=i If ix1 Then x1:=i Else If ix2 Then x2:=i

8、 Else If ix2 Then x2:=i Else If ix3 Then x3:=i; Else If ix3 Then x3:=i;确保确保x1x23x1x23 End; End;Writeln(x1/100:0:2, ,x2/100:0:2, ,x3/100:0:2);Writeln(x1/100:0:2, ,x2/100:0:2, ,x3/100:0:2);End.End.四、穷举法应用 四、穷举法应用 实例三：学校名次。实例三：学校名次。 问题描述：有问题描述：有A A，B B，C C，D D，E5E5所学校。在一次检所学校。在一次检查评比中，已知查评比中，已知E E校肯定不是

9、第校肯定不是第2 2名或第名或第3 3名，他名，他们互相进行推测。们互相进行推测。A A校有人说，校有人说，E E校一定是第校一定是第1 1名；名；B B校有人说，我校可能是第校有人说，我校可能是第2 2名；名；C C校有人说，校有人说，A A校校最差；最差；D D校有人说，校有人说，C C校不是最好的；校不是最好的；E E校有人说，校有人说，D D校会获第校会获第1 1名。结果只有第名。结果只有第1 1名和第名和第2 2名学校的人名学校的人猜对了。编程指出这猜对了。编程指出这5 5所学校的名次。所学校的名次。 四、穷举法应用 分析：本题是一个逻辑判断题，一般的逻辑判断题都采分析：本题是一个逻

10、辑判断题，一般的逻辑判断题都采用穷举法进行解决。我们对用穷举法进行解决。我们对5 5所学校所得名次的各种可所学校所得名次的各种可能情况进行穷举。在每种情况中，为了防止不同学校取能情况进行穷举。在每种情况中，为了防止不同学校取相同的名次，设立了逻辑数组相同的名次，设立了逻辑数组x x，xIxI为为falsefalse表示已有表示已有某校取第某校取第I I名。名。此题的难点在于确定判断条件。我们设立逻辑变量此题的难点在于确定判断条件。我们设立逻辑变量b0b0来来描述这一条件，主要有两个条件：描述这一条件，主要有两个条件：“E E校不是第校不是第2 2名或第名或第3 3名名”与与“只有第只有第1 1

11、名和第名和第2 2名的学校的人猜对名的学校的人猜对”，后一，后一条件要判断：条件要判断：1 1）是否只有两人说法正确？）是否只有两人说法正确？2 2）说得正确）说得正确的人是否是取得第的人是否是取得第1 1名和第名和第2 2名的学校的人？要判断是否名的学校的人？要判断是否仅有两人说正确，须统计正确命题的个数。为此，设立仅有两人说正确，须统计正确命题的个数。为此，设立了函数了函数btonbton，将逻辑量数值化。，将逻辑量数值化。 四、穷举法应用 程序：程序：program l3(output);var i,a,b,c,d,e,m:integer; x:array1.5 of boolean;

12、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 do if xd then四、穷举法应用 begin e:=1

13、5-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:=b0 and not b1; if b0 then writeln(a=,a:2, b=,b:2, c=,c:2, d=,d:2, e=,e:2); xd:=tru

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

15、朗数。例如153(153=1153(153=1* *1 1* *1+31+3* *3 3* *3+53+5* *5 5* *5)5)是一个三位数的阿姆斯特朗数是一个三位数的阿姆斯特朗数,8208,8208则是一个四则是一个四位数的阿姆斯特朗数。位数的阿姆斯特朗数。 五、穷举算法的深入应用算法分析：算法分析：为了使得程序尽快运行出正确结果为了使得程序尽快运行出正确结果, ,程序中使用程序中使用了一个数组了一个数组powerpower存放所有数字的各次幂之值存放所有数字的各次幂之值, , poweri,jpoweri,j等于等于i i的的j j次方。变量次方。变量currentnumbercurr

16、entnumber存放当前要被验证的数存放当前要被验证的数, ,数组数组digitdigit存放当前数的存放当前数的各位数字各位数字, ,开始时开始时digit3=1,digit3=1,其它元素均为其它元素均为0,0,此此时表示当前数为时表示当前数为100100。 highesthighest为当前数的位数。为当前数的位数。五、穷举算法的深入应用程序：程序：program ex3(input,outoutp);program ex3(input,outoutp);const maxlen=7;const maxlen=7;var i,j,currentnumber,highest,sum,to

17、tal:longintvar i,j,currentnumber,highest,sum,total:longint; ; digit:array 0.maxlen+1 of integer; digit:array 0.maxlen+1 of integer; power:array 0.9,0.maxlen of longint power:array 0.9,0.maxlen of longint; ;beginbegin for i:=0 to 9 do for i:=0 to 9 do begin begin poweri,0:=1; poweri,0:=1;for j:=1 to

18、maxlen do poweri,j:=poweri,j-1for j:=1 to maxlen do poweri,j:=poweri,j-1* *i i end; end; 五、穷举算法的深入应用 for i:=1 to maxlen do digiti:=0; for i:=1 to maxlen do digiti:=0; digit3:=1; highest:=3; digit3:=1; highest:=3; currentnumber:=100; total:=0; currentnumber:=100; total:=0; while digitmaxlen+1=0 do wh

19、ile digitmaxlen+1=0 do begin begin sum:=0; sum:=0; for i:=1 to highest do for i:=1 to highest do sum:=sum+powerdigiti,highest; sum:=sum+powerdigiti,highest; if sum=currentnumber if sum=currentnumber then begin total:=total+1; then begin total:=total+1; write(currentnumber:maxlen+5); write(currentnum

20、ber:maxlen+5); if total if total mod 6=0 then writeln mod 6=0 then writeln end; end;五、穷举算法的深入应用 digit1:=digit1+1; i:=1; digit1:=digit1+1; i:=1; while digiti=10 do while digiti=10 do begin begin digiti+1:=digiti+1+1; digiti+1:=digiti+1+1; digiti:=0; i:=i+1 digiti:=0; i:=i+1 end; end; if ihighest then

21、 highest:=i; if ihighest then highest:=i; currentnumber:=currentnumber+1 currentnumber:=currentnumber+1 end; end; writeln writelnend.end.五、穷举算法的深入应用优化策略一：算法中的时间和空间往往是矛盾的，优化策略一：算法中的时间和空间往往是矛盾的，时间复杂性和空间复杂性在一定条件下也是可以时间复杂性和空间复杂性在一定条件下也是可以相互转化的相互转化的, ,有时候为了提高程序运行的速度有时候为了提高程序运行的速度, ,在在算法的空间要求不苛刻的前提下算法的空间要

22、求不苛刻的前提下, ,设计算法时可考设计算法时可考虑充分利用有限的剩余空间来存储程序中反复要虑充分利用有限的剩余空间来存储程序中反复要计算的数据计算的数据, ,这就是这就是“用空间换时间用空间换时间”策略策略, ,是优是优化程序的一种常用方法。化程序的一种常用方法。五、穷举算法的深入应用五、穷举算法的深入应用实例五：邮票面值。实例五：邮票面值。问题描述：邮局发行一套票面有四种不同值的邮票，问题描述：邮局发行一套票面有四种不同值的邮票，如果每封信所贴邮票张数不超过三枚，存在整数，如果每封信所贴邮票张数不超过三枚，存在整数，使得用不超过三枚的邮票，可以贴出连续的整数、使得用不超过三枚的邮票，可以贴

23、出连续的整数、，、，来，找出这四种面值数，使得值，来，找出这四种面值数，使得值最大。最大。五、穷举算法的深入应用分析：分析：本题知道每封信邮票数的范围（本题知道每封信邮票数的范围（=3 ）,邮票有四邮票有四种类型，编程找出能使面值最大邮票。其算法是：种类型，编程找出能使面值最大邮票。其算法是： (1) 面值不同的四种邮票，每封信所贴邮票不超过面值不同的四种邮票，每封信所贴邮票不超过 3 张。张。(2) 用这四种邮票贴出连序的整数，并且使值最大。用这四种邮票贴出连序的整数，并且使值最大。(3) 用穷举法，找出所有符合条件的解。用穷举法，找出所有符合条件的解。(4) 本题用集合的方法统计邮票面值，

24、提高判重的速度。本题用集合的方法统计邮票面值，提高判重的速度。 设四种邮票的面值分别为：设四种邮票的面值分别为： A , B , C , D ，根据题意，根据题意设：设： A B C D，因此，因此 A=1 ，用循环语句完成搜索。，用循环语句完成搜索。 五、穷举算法的深入应用Program p12_3 ; 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,

25、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 x0 then beginx0:=x; x1:=a ; x2:=b ; x3:=c ; x4:=d 保存最大面值邮票保存最大面值邮票 write( x1：5, x2：5, x3：5, x4：5 );writeln( :10

26、, x0=, x0 );end;end; end.五、穷举算法的深入应用程序运行后，其输出结果是：程序运行后，其输出结果是： 解答结果有解答结果有11 组组1 2 3 4 x0=121 2 3 5 x0=13.1 3 6 10 x0=231 4 7 8 x0=24五、穷举算法的深入应用优化思路二：减少穷举的变量，在使用穷举算法之优化思路二：减少穷举的变量，在使用穷举算法之前，先考虑一下解元素之间的关联，将一些非穷举前，先考虑一下解元素之间的关联，将一些非穷举不可的解元素列为穷举变量，其他元素通过计算和不可的解元素列为穷举变量，其他元素通过计算和分析得出解元素的可能值。分析得出解元素的可能值。优

27、化思路三：优化思路三： 减少穷举变量的值域，通过和穷举变量间的数减少穷举变量的值域，通过和穷举变量间的数学关系定义解元素的值域。学关系定义解元素的值域。 五、穷举算法的深入应用实例实例六六：方格填数。：方格填数。问题描述：如图所示的问题描述：如图所示的8个格子中放入个格子中放入18八个数八个数字，使得相邻的和对角线的数字之差不为字，使得相邻的和对角线的数字之差不为1。编。编程找出所有放法。程找出所有放法。五、穷举算法的深入应用分析：我们先不考虑后一条件，分析：我们先不考虑后一条件，只考虑第一个条件，即把只考虑第一个条件，即把18八八个数字放入个数字放入8个格子中。这是容易个格子中。这是容易做到

28、的，就是做到的，就是8个数字的全排列，个数字的全排列，共有共有8!=40320种放法。然后对种放法。然后对这这8!个可行解用后一个条件加以个可行解用后一个条件加以检验，输出符合条件的解。对于检验，输出符合条件的解。对于后一个条件中后一个条件中“相邻相邻”的判断，的判断，可以建立一个邻接表来解决：可以建立一个邻接表来解决：11221331442352562673413671478五、穷举算法的深入应用表中表示哪两个格子是相邻的，表中表示哪两个格子是相邻的，linki,1和和linki,2是相是相邻的格子的编号。全排列的产生，可以用八重循环，也可邻的格子的编号。全排列的产生，可以用八重循环，也可以

29、用专门的算法，程序留给同学们自己去完成。利用穷举以用专门的算法，程序留给同学们自己去完成。利用穷举策略编制的程序，其运算量一般是很大的，因此如何提高策略编制的程序，其运算量一般是很大的，因此如何提高算法效率是穷举算法一个很重要的问题。一般应尽量减少算法效率是穷举算法一个很重要的问题。一般应尽量减少可行解的个数，使得第二步的检验运算量尽可能地少。可行解的个数，使得第二步的检验运算量尽可能地少。如何来优化算法呢如何来优化算法呢?五、穷举算法的深入应用如果注意到如果注意到b3和和b6两个格子，与它们两个格子，与它们“相邻相邻”的格子有的格子有6个，也就是说，放入这两个格子中的数，必须和个，也就是说，

30、放入这两个格子中的数，必须和6个数个数不连续，仅可以和一个数是连续的，这样的数只有不连续，仅可以和一个数是连续的，这样的数只有2个，个，即即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)

31、，(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 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:

32、boolean; var i: integer; begin choose:= false; for i:=1 to 6 do if abs(blinki, 1 - blinki ,2) = 1 then exit; choose := true end;五、穷举算法的深入应用procedure try; begin for b2:=3 to 6 do for b4:= 3 to 6 do if b2b4 then for b5:= 3 to 6 do if (b5b2) and (b5b4) then begin b7:= 18 - b2 - b4 - b5; if choose then

33、print; end; end;五、穷举算法的深入应用begin b1:=2;b3:=8;b6:= 1;b8:=7; try; b1:=7;b3:=1 ;b6:=8;b8:=2; try; readlnend.五、穷举算法的深入应用优化思路四：分解约束条件，将拆分的约束条件嵌优化思路四：分解约束条件，将拆分的约束条件嵌套在相应的循环体间，尽可能减少可行解的数目，套在相应的循环体间，尽可能减少可行解的数目，也称为也称为“剪枝剪枝”，即把明显不符合条件的可行解尽，即把明显不符合条件的可行解尽可能地剪去，减少穷举的计算量。可能地剪去，减少穷举的计算量。六、穷举算法的代码实现方法：实例七：实例七：4皇

34、后问题。皇后问题。问题描述：在问题描述：在44的棋盘上安置的棋盘上安置4个皇后，要求个皇后，要求任意两个皇后不在同一行、不在同一列、不在同任意两个皇后不在同一行、不在同一列、不在同一对角线上，输出所有的方案。一对角线上，输出所有的方案。分析：分析：1 1） 本题是一个搜索问题，搜索范围本题是一个搜索问题，搜索范围 4 44 4，找出符，找出符合条件的方案；合条件的方案；2 2）方案必须满足的条件：任意两个不在同一行、）方案必须满足的条件：任意两个不在同一行、同一列和同一对角线。同一列和同一对角线。 六、穷举算法的代码实现方法：方法一程序：方法一程序：const n=4;const n=4;ty

35、pe stack=array1.n of integer;type stack=array1.n of integer;var i1,i2,i3,i4:integer;var i1,i2,i3,i4:integer; s:stack; s:stack;function check:boolean;function check:boolean;var i,j:integer;var i,j:integer;beginbegin for i:=1 to n-1 do for i:=1 to n-1 do for j:=i+1 to n do for j:=i+1 to n doif (si=sj)

36、 or (si-i=sj-j) or (si+i=sj+j)if (si=sj) or (si-i=sj-j) or (si+i=sj+j) then begin check:=false; then begin check:=false; exit exit end; end; check:=true check:=trueend;end;六、穷举算法的代码实现方法：procedure print;procedure print;var i:integer;var i:integer;beginbegin for i:=1 to n do write(si:2); for i:=1 to n

37、 do write(si:2); writeln writelnend;end;beginbegin for i1:=1 to n do for i1:=1 to n do for i2:=1 to n do for i2:=1 to n do for i3:=1 to n do for i3:=1 to n do for i4:=1 to n do for i4:=1 to n do begin begins1:=i1;s2:=i2;s3:=i3;s4:=i4;s1:=i1;s2:=i2;s3:=i3;s4:=i4; if check then print; if check then pr

38、int; end; end;end.end.方法二程序：方法二程序：const n=4;const n=4;type stack=array1.n of integer;type stack=array1.n of integer;var i1,i2,i3,i4:integer;var i1,i2,i3,i4:integer; s:stack; s:stack;function check:boolean;function check:boolean;var i,j:integer;var i,j:integer;beginbegin for i:=1 to n-1 do for i:=1 t

39、o n-1 do for j:=i+1 to n do for j:=i+1 to n doif (si=sj) or (si-i=sj-j) or (si+i=sj+j)if (si=sj) or (si-i=sj-j) or (si+i=sj+j) then begin check:=false; then begin check:=false; exit exit end; end; check:=true check:=trueend;end;六、穷举算法的代码实现方法：procedure print;procedure print;var i:integervar i:integer

40、; ;beginbegin for i:=1 to n do write(si:2); writeln for i:=1 to n do write(si:2); writelnend;end;beginbegin while s0=1 do while s0=1 do begin j:=n; begin j:=n; while (sj while (sj=4)=4) do j:=j-1; do j:=j-1; sj:=sj+1; sj:=sj+1; for I:=j+1 to n do sI for I:=j+1 to n do sI ：=1;=1; if check then print;

41、 if check then print; end; end;end.end.方法三程序：方法三程序：const n=8;const n=8;type stack=array1.n of integer;type stack=array1.n of integer;var count:integervar count:integer; ; s:stack s:stack; ;function check:booleanfunction check:boolean; ;var i,j:integervar i,j:integer; ;beginbegin for i:=1 to n-1 do f

42、or i:=1 to n-1 do for j:=i+1 to n do for j:=i+1 to n doif (si=sj) or (si-i=sj-j) or if (si=sj) or (si-i=sj-j) or (si+i=sj+j(si+i=sj+j) then begin check:=false;) then begin check:=false; exit exit end; end; check:=true end;check:=true end;六、穷举算法的代码实现方法：procedure print;procedure print;var i:integervar

43、 i:integer; ;beginbegin for i:=1 to n do write(si:2); writeln for i:=1 to n do write(si:2); writelnend;end;procedure search(kprocedure search(k: integer);: integer); var i:integer var i:integer; ;beginbegin if k n then begin if k n then begin if check then begin count:=count+1;print;end; if check th

44、en begin count:=count+1;print;end; endend else for i := 1 to n do else for i := 1 to n do begin begin sk sk := i; search(k+1); := i; search(k+1); end end end end; ;begin count := 0; search(1);write(count); end.begin count := 0; search(1);write(count); end.方法四程序：方法四程序：const n=8;const n=8;type stack=a

45、rray0.n of integer;type stack=array0.n of integer;var top,count:integervar top,count:integer; ; s:stack s:stack; ;function check:booleanfunction check:boolean; ;var i,j:integervar i,j:integer; ;beginbegin for i:=1 to n-1 do for i:=1 to n-1 do for j:=i+1 to n do for j:=i+1 to n doif (si=sj) or (si-i=

46、sj-j) or if (si=sj) or (si-i=sj-j) or (si+i=sj+j(si+i=sj+j) then begin check:=false;) then begin check:=false; exit exit end; end; check:=true end; check:=true end;六、穷举算法的代码实现方法：beginbeginfillchar(s,sizeof(s),0);fillchar(s,sizeof(s),0); count:=0; count:=0;top:=1;top:=1;repeatrepeat inc(stop inc(stop

47、);); if stop if stop=n then=n then if top=n then if top=n then begin if check then begin if check then begin begin stop stop:=0;dec(top); count:=count+1;:=0;dec(top); count:=count+1; end end end end else inc(top else inc(top) ) else begin stop else begin stop:=0;dec(top);end;:=0;dec(top);end;until t

48、op=0; write(countuntil top=0; write(count);); end. end.七、实例分析：实例八：巧妙填数。实例八：巧妙填数。问题描述：将问题描述：将19这九个数字填入九个空格中。这九个数字填入九个空格中。每一横行的三个数字组成一个三位数。如果要使第每一横行的三个数字组成一个三位数。如果要使第二行的三位数是第一行的两倍，第三行的三位数是二行的三位数是第一行的两倍，第三行的三位数是第一行的三倍，应怎样填数。如图所示。第一行的三倍，应怎样填数。如图所示。192384576 七、实例分析：分析：本题目有分析：本题目有9个格子，要求填数，如果不考虑个格子，要求填数，如

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

50、r; begin 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(

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

52、格。并且每个数字的绝对值不超过1000000。 输出数据： 输出文件是numbertap.out。文件输出一行，代表最接近零数值的绝对值。七、实例分析：const n=4;const n=4;type stack=array0.n of integer;type stack=array0.n of integer;var i,j,k,sum,min:integervar i,j,k,sum,min:integer; ; s:stack s:stack; ; a:array1.n,1.n of integer; a:array1.n,1.n of integer;beginbegin for i

53、:=0 to n do si for i:=0 to n do si:=0;:=0; for i:=1 to n do for i:=1 to n do for j:=1 to i do for j:=1 to i do begin read(ai,j);end begin read(ai,j);end; ; min:=10000; min:=10000; while s1=0 dowhile s1=0 do begin j:=n; begin j:=n; while (sj while (sj=1) do j:=j-1;=1) do j:=j-1; sj sj:=sj+1;:=sj+1; f

54、or I:=j+1 to n do sI for I:=j+1 to n do sI:=0;:=0; k:=1;sum:=0; k:=1;sum:=0; for i:=1 to n do for i:=1 to n do begin begin k:=k+si;write(k,k k:=k+si;write(k,k);); sum:=sum+aI,k sum:=sum+aI,k; write(ai,k,sum);readln write(ai,k,sum);readln; ; end; end; if abs(sum)abs(min if abs(sum)abs(min) then ) the

55、n min:=sum;min:=sum; end; end;end.end. 实例十：选数 问题描述：已知n（1=n=20）个整数x1,x2,xn（1=xi=5000000），以及一个整数k（kn）。从n个整数中任选k个整数相加，可分别得到一系列的和。现在，要求你计算出和为素数共有多少种。七、实例分析： 本题无数学公式可寻，1=n1)是否为素数最简单的方法就是看是否是否为素数最简单的方法就是看是否存在一个素数存在一个素数a(a=sqrt(P)是是P的约数的约数，如果不存在，该数就为素数，由于在此题中1=xi=5000000,n=20,所以要判断的数P不会超过100000000，sqrt(p)=10000，因此，为了加快速度，我们可以用筛选法将210000之间的素数保存到一个数组里（共1229个），这样速度估计将提高好几倍。穷举法小结:穷举的思想往往是最容