回溯算法的递归实现 由于回溯算法用一栈数组实现的,用到栈一般可用递归实现。 上述例1的递归方法实现如下: program hh;
const n=4;
var i,k:integer;
x:array[1..n] of integer;
st:string[n];
t:string[n];
procedure input;
var i:integer;
begin
write('Enter string=');readln(st);
t:=st;
end;
function place(k:integer):boolean;
var i:integer;
begin
place:=true;
for i:=1 to k-1 do
if x=x[k] then
begin place:=false; break end ;
end;
procedure print;
var i:integer;
begin
for i:=1 to n do write(t[x]);
writeln;readln;
end;
procedure try(k:integer);
var i :integer;
begin
if k=n+1 then begin print;exit end;
for i:=1 to n do
begin
x[k]:=i;
if place(k) then try(k+1)
end
end;
begin
input;
try(1);
end. 例2:n皇后问题的递归算法如下: 程序1: program hh;
const n=8;
var i,j,k:integer;
x:array[1..n] of integer;
function place(k:integer):boolean;
var i:integer;
begin
place:=true;
for i:=1 to k-1 do
if (x=x[k]) or (abs(x-x[k])=abs(i-k)) then
place:=false ;
end;
procedure print;
var i:integer;
begin
for i:=1 to n do write(x:4);
writeln;
end;
procedure try(k:integer);
var i:integer;
begin
if k=n+1 then begin print; exit end;
for i:= 1 to n do
begin
x[k]:=i;
if place(k) then try(k+1);
end;
end ;
begin
try(1);
end. 程序2: 说明:当n=8 时有30条对角线分别用了l和r数组控制, 用c数组控制列.当(i,j)点放好皇后后相应的对角线和列都为false.递归程序如下: program nhh;
const n=8;
var s,i:integer;
a:array[1..n] of byte;
c:array[1..n] of boolean;
l:array[1-n..n-1] of boolean;
r:array[2..2*n] of boolean;
procedure output;
var i:integer;
begin
for i:=1 to n do write(a:4);
inc(s);writeln(' total=',s);
end;
procedure try(i:integer);
var j:integer;
begin
for j:=1 to n do
begin
if c[j] and l[i-j] and r[i+j] then
begin
a:=j;c[j]:=false;l[i-j]:=false; r[i+j]:=false;
if i<n then try(i+1) else output;
c[j]:=true;l[i-j]:=true;r[i+j]:=true;
end;
end;
end;
begin
for i:=1 to n do c:=true;
for i:=1-n to n-1 do l:=true;
for i:=2 to 2*n do r:=true;
s:=0;try(1);
writeln;
end.
|