第十三讲穷举算法.ppt

6.1 穷举策略的概念 所谓枚举法，指的是从可能的解的集合中一一枚举各元素， 用题目给定的检验条件判定哪些是无用的，哪些是有用的。能使命题成立，即为其解。 有些问题可以用循环语句和条件语句直接求解，有些问题用循环求解时循环次数太多，无法编写程序，怎么办？下面是用“千军万马过独木桥，适者存”的方式实现穷举策略的。 6.2 典型例题与习题 例1.将2n个0和2n个1，排成一圈。从任一个位置开始，每次按逆时针的方向以长度为n+1的单位进行数二进制数。要求给出一种排法，用上面的方法产生出来的2n+1个二进制数都不相同。例如，当n=2时，即22个0和22个1排成如下一圈： 比如，从A位置开始，逆时针方向取三个数000，然后再从B位置上开始取三个数001，接着从C开始取三个数010，...可以得到000，001，010，101，011，111，110，100共8个二进制数且都不相同。 * * 第十三讲　穷举算法 主讲人：张志刚 　　VAR　　　A　　　　:ARRAY[1..36] OF 0..1　　　B　　　　:ARRAY[0..31] OF INTEGER;　　　I,J,K,S,P:INTEGER;　　　BEGIN　　　　FOR I:=1 TO 36 DO　　A[I]:=0;　　　　 FOR I:=28 TO 32 DO　　A[I]:=1;　　　　P:=1;　　A[6]:=1;　　　　WHILE (P=1) DO　　　　　BEGIN　　　　　　J:=27　　　　　　WHILE A[J]=1 DO　　J:=J-1;　　　　　　(　A[J]:=1　)　　　　　　FOR I:=J+1 TO 27 DO (　A[i]:=0　)　　　　　　FOR I:=0 TO 31 DO B[I]:=0;　　　　　　FOR I:=1 TO 32 DO　　　　　　 BEGIN　　　　　　　(　S:=0)　　　　　　　　FOR K:=I TO I+4 DO　　S:=S*2+A[k];　　　　　　　　(　B[S]:=1　)　　　　　　 END;　　　　　　S:=0;　　　　　　FOR I:=0 TO 31 DO　　S:=S+B[I];　　　　　　IF ( S=32　) THEN P:=0　　　　　END;　 　　　FOR I:=1 TO 32 DO　　FOR J:=I TO I+4 DO　　WRITE(A[J]);　　　WRITELN　　END. 例2：在A、B两个城市之间设有N个路站(如下图中的S1，且N100)，城市与路站之间、路站和路站之间各有若干条路段(各路段数=20，且每条路段上的距离均为一个整数)。??? A，B的一条通路是指：从A出发，可经过任一路段到达S1，再从S1出发经过任一路段，…最后到达B。通路上路段距离之和称为通路距离(最大距离=1000)。当所有的路段距离给出之后，求出所有不同距离的通路个数(相同距离仅记一次)。??? 例如：下图所示是当N=1时的情况： 从A到B的通路条数为6，但因其中通路5+5=4+6，所以满足条件的不同距离的通路条数为5。 算法说明：本题采用穷举算法。数据结构：N：记录A，B间路站的个数????????? 数组D[I，0]记录第I-1个到第I路站间路段的个数????????????? D[I，1]，D[I，2]，…记录每个路段距离????????? 数组G记录可取到的距离 VAR I,J,N,S:INTEGER;? B:ARRAY[0..100] OF INTEGER;? D:ARRAY[0..100,0..20] OF INTEGER;? G:ARRAY[0..1000] OF 0..1;BEGIN? READLN(N);? FOR I:=1 TO N+1 DO??? BEGIN????? READLN(D[I,0]);????? FOR J:=1 TO D[I,0] DO READ(D[I,J]);??? END;? D[0,0]:=1;? FOR I:=1 TO N+1 DO B[I]:=1;? B[0]:=0;? FOR I:=1 TO 1000 DO G[I]:=0;? WHILE??????? B[0]1?????? DO??? BEGIN????? S:=0;????? FOR I:=1 TO N+1 DO??????? S:=?????? S+D[I,B[I]];???????????? G[S]:=1;J:=N+1;????? WHILE????????? B[J]=D[J,0]??????? DO J:=J-1;????? B[J]:=B[J]+1;????? F