首页 > 代码库 > 回溯法第7题—圆盘移动问题
回溯法第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!”
[样例输入1]
[样例输出1]
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+1until 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.
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。