|
优学合肥奥数网讯：信息学竞赛常用算法与策略：回溯。 回溯是按照某种条件往前试探搜索,若前进中遭到失败,则回过头来另择通路继续搜索. 3.1 回溯的设计 1.用栈保存好前进中的某些状态. 2.制定好约束条件 例1由键盘上输入任意n个符号;输出它的全排列. 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[i]=x[k] then begin place:=false; break end ; end; procedure print; var i:integer; begin for i:=1 to n do write(t[x[i]]); writeln; end; begin input; k:=1;x[k]:=0; while k>0 do begin x[k]:=x[k]+1; while (x[k]<=n) and (not place(k)) do x[k]:=x[k]+1; if x[k]>n then k:=k-1 else if k=n then print else begin k:=k+1;x[k]:=0 end end ; end. 例2.n个皇后问题: 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[i]=x[k]) or (abs(x[i]-x[k])=abs(i-k)) then place:=false ; end; procedure print; var i:integer; begin for i:=1 to n do write(x[i]:4); writeln; end; begin k:=1;x[k]:=0; while k>0 do begin x[k]:=x[k]+1; while (x[k]<=n) and (not place(k)) do x[k]:=x[k]+1; if x[k]>n then k:=k-1 else if k=n then print else begin k:=k+1;x[k]:=0 end end ; end. 3.2 回溯算法的递归实现 由于回溯算法用一栈数组实现的,用到栈一般可用递归实现。 上述例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[i]=x[k] then begin place:=false; break end ; end; procedure print; var i:integer; begin for i:=1 to n do write(t[x[i]]); 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[i]=x[k]) or (abs(x[i]-x[k])=abs(i-k)) then place:=false ; end; procedure print; var i:integer; begin for i:=1 to n do write(x[i]: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[i]: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[i]:=j;c[j]:=false;l[i-j]:=false; r[i+j]:=false; if ic[j]:=true;l[i-j]:=true;r[i+j]:=true; end; end; end; begin for i:=1 to n do c[i]:=true; for i:=1-n to n-1 do l[i]:=true; for i:=2 to 2*n do r[i]:=true; s:=0;try(1); writeln; end. 练习： 1.找出所有从m个元素中选取n(n<=m)元素的组合。 2.设有A,B,C,D,E 5人从事j1,j2,j3,j4,j5 5项工作每人只能从事一项,它们的 效益表如下: 求最佳安排,使效益最高. 3.N个数中找出M个数(从键盘上输入正整数N,M后再输入N个正数),要求从N个数中 找出若干个数,使它们的和为M,把满足条件的数组找出来,并统计组数. 4.地图着色。如下图12个区域用4种颜色着色要求相邻的区域着不同的颜色 5.将任意一正整数(1如:4=1+1+1+1 =2+1+1 =2+2 =3+1. 关于合肥市青少年信息学竞赛更多的信息，请关注优学合肥奥数网“青少年信息学竞赛”频道。 信息学竞赛常用算法与策略：递归 信息学竞赛常用算法与策略：算法的概念 青少年信息学竞赛Pascal语言：程序调试（十一） 青少年信息学竞赛Pascal语言：指针（十） 更多精彩内容推荐>> | 
