NOIP2007的汉诺塔，Pascal解答

Question

数据太大过不掉！！

Answer 1

跟普通HANOI一样，就乘2而已
先用递推法
要把2N个盘从A移动到B上，就先移动2(N-1)个到C上，再移2个到B上，最后把2(N-1)个移到B上
因此F(N)=2*F(N-1)+2 F(1)=2
易得F(N)=2*2^N-2=2^(N+1)-2

又因为N最大到200，2的201次方太大，因此要使用高精度

var
a:array[1..100] of integer;
n,i,j:integer;
begin
fillchar(a,sizeof(a),0);
readln(n);
a[1]:=1;
for i:=1 to n+1 do
begin
for j:=1 to 100 do
a[j]:=a[j]*2;
for j:=2 to 100 do
begin
a[j]:=a[j]+a[j-1] div 10;
a[j-1]:=a[j-1] mod 10;
end;
end; //标准的高精度，算2^(N+1)
j:=100;
while a[j]=0 do j:=j-1;
a[1]:=a[1]-2; //因为2^K末位数为2 4 6 或 8，所以减去2以后没有退位问题
for i:=j downto 1 do write(a[i]);
writeln;
end.

还不会的话问我

Answer 2

高精度啊，童鞋....

Answer 3

program ex;
var m:integer;
procedure move(f,putone:char);
begin writeln(getone,'->',putone) end;
procedure hanoi(n:integer;one,two,three:char);
begin
if n=1 then move(one,three) else
begin
hanoi(n-1,one,three,two);
move(one,three);
hanoi(n-1,two,one,three)
end
end;
begin
readln(m);
write('the step to moving disks:');
writeln;
hanoi(m,'A','B','C')
end.