题解 P1242 【新汉诺塔】

· · 题解

这题实际上不难。就是先把每一个圆盘的初始所在的塔和最终所在的塔记录下来，接着从大盘到小盘枚举开始递归，而递归过程的作用就是使第x个圆盘能移到第y个塔上，并移动。

依照题意，不能使第x个圆盘移动到第y个塔上的因素，只有比第x个圆盘小的圆盘在第x个圆盘所在的塔和第y个塔。这样只要使所有比第x个圆盘小的圆盘都移动到另外第三个塔上就行了。而递归的出口就是当第x个圆盘就在第y个塔上。

当然递归的最后别忘了记录下第x个圆盘移动后的结果，并输出以及统计步数。

因为这算法没有什么冗余步骤，所以输出的一定是最优的方法~


program ex1242;
const
  c:array[1..3] of char=('A','B','C');
var
  a:array[1..1000] of longint;
  b:array[1..1000] of longint;
  i,j,k,m,n,s,t:longint;
procedure dg(x,y:longint);
var
  i,j,k,l:longint;
  b:array[1..3] of longint;
begin
  if a[x]=y then exit;
  for i:=1 to 3 do
    b[i]:=0;
  b[a[x]]:=1;
  b[y]:=1;
  for i:=1 to 3 do
    if b[i]=0 then begin j:=i; break; end;
  for i:=x-1 downto 1 do
    dg(i,j);
  writeln('move ',x,' from ',c[a[x]],' to ',c[y]);
  a[x]:=y;
  s:=s+1;
end;
begin
  readln(n);
  for i:=1 to 3 do
  begin
    read(s);
    for j:=1 to s do
    begin
      read(k);
      a[k]:=i;
    end;
  end;
  for i:=1 to 3 do
  begin
    read(s);
    for j:=1 to s do
    begin
      read(k);
      b[k]:=i;
    end;
  end;
  s:=0;
  for i:=n downto 1 do
    dg(i,b[i]);
  writeln(s);
end.

[color=orange]附上代码：[/color]