|
取数之穷举算法、 取数之穷举算法、递归算法 一、穷举搜索法 穷举搜索法是穷举所有可能情形，并从中找出符合要求的解。穷举所有可能情形，最直观 的是联系循环的算法。 [例]找出 n 个自然数(1,2,3,…,n)中 r 个数的组合。例如，当 n=５,r=3 时，所有组合为： ５ ４ ３ ５ ４ ２ ５ ４ １ ５ ３ ２ ５ ３ １ ５ ２ １ ４ ３ ２ ４ ３ １ ４ ２ １ ３ ２ １ total=10 {组合的总数} [解]n 个数中 r 的组合，其中每 r 个数中，数不能相同。另外，任何两组组合的数，所包 含的数也不应相同。例如，５、４、３与３、４、５。为此，约定前一个数应大于后一个 数。 将上述两条不允许为条件，当 r=3 时，可用三重循环进行搜索。 ［程序］ Program zuhe11; const n=5; var i,j,k,t:integer; begin t:=0; for i:=n downto 1 do for j:=n downto 1 do for k:=n downto 1 do if (i<>j)and(i<>k)and(i>j)and(j>k) then begin t:=t+1; writeln(i:3,j:3,k:3); end; writeln('total=',t); end. 或者 Program zuhe12; const n=5; r=3; var i,j,k,t:integer; begin t:=0; for i:=n downto r do for j:=i-1 downto r-1 do for k:=j-1 downto 1 do begin t:=t+1; writeln(i:3,j:3,k:3); end; writeln('total=',t); end. 这两个程序，前者穷举了所有可能情形，从中选出符合条件的解，而后者比较简洁。 但是这两个程序都有一个问题，当 r 变化时，循环重数改变，这就影响了这一问题的解， 即没有一般性。 但是，很多情况下穷举搜索法还是常用的。 【问题描述】在一个８×８格子的棋盘上，要布局八个皇后，条件是不能出现两个皇后在 同一行或同一列或同一斜线的情况，以防“相互攻击” ，请问共有多少种合理的布局方式， 每一种布局的具体情况如何？ 【分析】显然问题的键在于如何判定某个皇后所在的行、列、斜线上是否有别的皇后；可 以从矩阵的特点上找到规律，如果在同一行，则行号相同；如果在同一列上，则列号相同； 如果同在／ 斜线上的行列值之和相同；如果同在＼ 斜线上的行列值之差相同；如果斜线 不分方向，则同一斜线上两皇后的行号之差的绝对值与列号之差的绝对值相同。从下图可 以验证上面的说法： １ １ ２ ３ ４ ５ ６ ７ ８ ／ X 6 4 7 ／ － － ＼ ＼ － ／ ｜ ｜ ▲ ｜ ｜ ｜ 1 8 2 ／ － ＼ ＼ ＼ 5 3 － － － ／ ＼ ２ ３ ４ ｜ ｜ ／ ５ ６ ７ ８ ／ 对于一组布局我们可以用一个一维数组来表示：X:ARRAY [1..8] OF INTEGER;X[I]的下 标 I 表示第 I 个皇后在棋盘的第 I 列， X[I]的内容表示在第 I 列的第 X[I]行， 例如： X[3]=5 就表示第 3 个皇后在第 3 列的第 5 行。在这种方式下，要表示两个皇后 A 和 B 不在同一行 或斜线上的条件可以描述为：X[A]<>X[B] AND ABS(A-B)<>ABS(X[A]-X[B]){A 和 B 分别表 示两个皇后的列号} 八皇后之穷举算法 PROGRAM BHH;{穷举算法 穷举算法：最好理解，但效率最低} 穷举算法 CONST N=8; VAR I1,I2,I3,I4,I5,I6,I7,I8,T:INTEGER; X:ARRAY [1..N] OF INTEGER; PROCEDURE PRINT;{输出正确的解} VAR I:INTEGER; BEGIN INC(T); Writeln(T); FOR I:=1 TO N DO WRITE(X[I]); WRITELN; END; FUNCTION CHECK:BOOLEAN; VAR A,B:INTEGER; BEGIN FOR A:=2 TO N DO FOR B:=1 TO A-1 DO IF (ABS(X[A]-X[B])=ABS(A-B)) OR (X[A]=X[B]) THEN BEGIN CHECK:=FALSE; EXIT; END; CHECK:=TRUE; 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 FOR I5:=1 TO N DO FOR I6:=1 TO N DO FOR I7:=1 TO N DO FOR I8:=1 TO N DO BEGIN X[1]:=I1; X[2]:=I2; X[3]:=I3; X[4]:=I4; X[5]:=I5; X[6]:=I6; X[7]:=I7; X[8]:=I8; IF CHECK THEN PRINT; END; READLN; END. 二、递归法： 可以采用这递归思想来考虑求组合过程的算法。设过程为 comb(n,r:integer)为找出 从 n 个数中任取 r 个数的所有组合。当组合的第一个数字选定时，其后的数字是从余下的 n-1 个数中取 r-1 数的组合。这就将求 n 个数中取 r 个数的组合问题转化成求 n-1 个数中 取 r-1 个数的组合问题。设过程引入工作数组 a[ ]存放求出的组合的数字，约定过程将确 定的 r 个数字组合的第一个数字放在 a[r]中，当一个组合求出后，才将 a[ ]中的一个组合 输出。第一个数可以是 n、n-1、……、r，过程将确定组合的第一个数字放入数组后，有 两种可能的选择，因还未确定组合的其余元素，继续递归去确定；或因已确定了组合的全 部元素，输出这个组合。 ［程序］: Program zuhe2; var n,y,r:integer; a:array[1..100] of integer; Procedure comb(n,r:integer); var i,temp:integer; begin for i:=n downto r do begin a[r]:=i; if r>1 then comb(i-1,r-1) else begin for temp:=y downto 2 do write(a[temp],' '); writeln（a[1]）; end; end; end; Begin {main} readln(n,r); end; y:=r; comb(n,r); End. |
|
|
