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