回溯法第7题—圆盘移动问题
[问题描述]
从左向右依次安放4根细柱A,B,C,D。在A柱上套有n(n<=20)个直径相同的圆盘,从上到下一次用连续的小写字母a,b,c,...编号,将这些圆盘经过B,C单向的移动到D柱上(即不允许从右向左移动。圆盘可在B,C中暂存)。要求找到从A柱初始状态到D柱目标状态的移动过程。
输入:第一行是D柱上的圆盘总数,第二行是D柱上由下到上的圆盘的序列。
输出:是一个文件。该文件的每一行为一个形如"k m l"的字母序列,其中k为圆盘编号,m为k盘原先的柱号,l为目标柱号。如果不能生成排列,则输出“no solution!”
[样例输入]
3 a b c
[样例输出]
c A B
b A C
a A D
b C D
c B D
[问题分析]
懒得写题(dai)解(ma)了…………直接上代码
下面是标准程序:
program p1_7(input,output); var ga,gb,gc,gd,fd:array [0..15] of char; topa,topb,topc,topf:byte; resl:array [1..2000] of record code:char; source:char; target:char end; order:array [‘0‘..‘z‘] of byte; i,n,kz,ks:byte; j:char; procedure print; var i:byte; begin i:=1; repeat writeln(resl[i].code:5,resl[i].source:5,resl[i].target:5); inc(i) until resl[i].code=‘0‘; end; procedure move1(var topa,topb,topc,ks:byte); var t:byte; begin repeat if (topa=0)and(topb=0)and(topc=0) then begin print;halt(1);kz:=1 end; t:=0; if ga[topa]=fd[topf] then begin{a-d} t:=t+1; ks:=ks+1; resl[ks].code:=ga[topa]; resl[ks].source:=‘A‘; resl[ks].target:=‘D‘; topf:=topf+1;topa:=topa-1; end; if gb[topb]=fd[topf] then begin{b-d} t:=t+1; ks:=ks+1; resl[ks].code:=gb[topb]; resl[ks].source:=‘B‘; resl[ks].target:=‘D‘; topf:=topf+1;topb:=topb-1; end; if gc[topc]=fd[topf] then begin {c-d} t:=t+1; ks:=ks+1; resl[ks].code:=gc[topc]; resl[ks].source:=‘C‘; resl[ks].target:=‘D‘; topf:=topf+1;topc:=topc-1; end; until t=0; end; procedure move2(var topa,topb,topc,ks: byte); var tp,ks1:byte; begin move1(topa,topb,topc,ks); ks1:=ks+1; for tp:=1 to 3 do case tp of 1: {a--b} if topa>0 then begin resl[ks1].code:=ga[topa]; resl[ks1].source:=‘A‘; resl[ks1].target:=‘B‘; topb:=topb+1;gb[topb]:=ga[topa];topa:=topa-1; move2(topa,topb,topc,ks1); topa:=topa+1;dec(topb); end; 2: {a--c} if (order[ga[topa]]<order[gc[topc]])and(topa>0) then begin resl[ks1].code:=ga[topa]; resl[ks1].source:=‘A‘; resl[ks1].target:=‘C‘; topc:=topc+1;gc[topc]:=ga[topa];topa:=topa-1; move2(topa,topb,topc,ks1); topa:=topa+1;dec(topc); end; 3: {b--c} if (order[gb[topb]]<order[gc[topc]])and(topb>0)then begin resl[ks1].code:=gb[topb]; resl[ks1].source:=‘B‘; resl[ks1].target:=‘C‘; topc:=topc+1;gc[topc]:=gb[topb];dec(topb); move2(topa,topb,topc,ks1); topb:=topb+1;dec(topc) end; end{case and for}; end; begin{main} assign(input,‘word.in‘); reset(input); assign(output,‘word.out‘); rewrite(output); readln(n); for i:=1 to n do read(fd[i]); i:=1; repeat for j:=‘a‘ to chr(ord(‘a‘)+n-1) do if j=fd[i] then order[j]:=i;i:=i+1 until i>n; order[‘0‘]:=0; order[‘1‘]:=100; for i:=1 to 200 do resl[i].code:=‘0‘; for i:=1 to n do ga[i]:=chr(ord(‘a‘)+i-1); topa:=n;topb:=0;topc:=0;topf:=1;kz:=0; ks:=0;ga[0]:=‘0‘;gb[0]:=‘0‘;gc[0]:=‘1‘; move2(topa,topb,topc,ks); if kz=0 then writeln(‘no solution!‘); end.
郑重声明:本站内容如果来自互联网及其他传播媒体,其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享,并不代表本站赞同其观点和对其真实性负责,也不构成任何其他建议。