ENG  RUS Timus Online Judge
Online Judge
Problems
Authors
Online contests
Site news
Webboard
Problem set
Submit solution
Judge status
Guide
Register
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules
back to board

## Discussion of Problem 1054. Tower of Hanoi

A simple problem-> a impossible solution
Posted by Simeon Kostenski 17 Apr 2001 03:15
Can anyone of those who have solved the problem tell me
how ? If you use recursion 31 is a extremely enormous limit
and it works years. So a formula? How?
use the formula given in the problem ;) (+)
Posted by Dinh Quang Hiep (mg9h@yahoo.com) 19 Apr 2001 14:18
it takes 2^k-1 steps to move k disk from one peg to another

QH@
Re: A simple problem-> a impossible solution
Posted by Timus Observer 26 Aug 2001 07:22
> Can anyone of those who have solved the problem tell me
> how ? If you use recursion 31 is a extremely enormous
limit
> and it works years. So a formula? How?
I am facing the same problem. Time limite exceeding. Could
somone advise me how to optimize the algorithm ?.program
hanoit;
const maxN=31;
var i,n,nmove:integer;
current,target:array[1..maxN] of integer;

function sama:boolean;
var i:integer;
begin
sama:=true;
for i:=1 to N do if current[i]<>target[i] then
begin
sama:=false;
exit;
end;
end;

procedure move(n,to_:integer);
begin
inc(nmove);
current[n]:=to_;
if sama then begin writeln(nmove); readln; halt; end;
end;

procedure hanoi (n, from, to_, temp : integer);
begin
if n > 0 then
begin
hanoi (n-1,from,temp,to_);
move(n,to_);
hanoi(n-1,temp,to_,from);
end;
end;
begin
nmove:=0;
for i:=1 to N do
begin
current[i]:=1;
end;
if sama then begin writeln(nmove); readln; halt; end
else hanoi(N,1,2,3);
writeln(-1 );
end.
Re: A simple problem-> a impossible solution
Posted by Dan Ghinea 7 Jan 2002 04:18
First of all you shouldn't use readln after you print the
solution.It'll wait forever!

Good luck!

> I am facing the same problem. Time limite exceeding. Could
> somone advise me how to optimize the algorithm ?.program
> hanoit;
> const maxN=31;
> var i,n,nmove:integer;
>     current,target:array[1..maxN] of integer;
>
> function sama:boolean;
> var i:integer;
> begin
>   sama:=true;
>   for i:=1 to N do if current[i]<>target[i] then
>   begin
>     sama:=false;
>     exit;
>   end;
> end;
>
> procedure move(n,to_:integer);
> begin
>   inc(nmove);
>   current[n]:=to_;
>   if sama then begin writeln(nmove); readln; halt; end;
> end;
>
> procedure hanoi (n, from, to_, temp : integer);
> begin
>   if n > 0 then
>   begin
>     hanoi (n-1,from,temp,to_);
>     move(n,to_);
>     hanoi(n-1,temp,to_,from);
>   end;
> end;
> begin
>   nmove:=0;
>   for i:=1 to N do
>   begin
>     current[i]:=1;
>   end;
>   if sama then begin writeln(nmove); readln; halt; end
>   else hanoi(N,1,2,3);
>   writeln(-1 );
> end.
>
>
Re: A simple problem-> a impossible solution
Posted by Chen Xiaoke 2 Feb 2002 15:26
faint,of course can't do it in this way...you should find a formula...

> > Can anyone of those who have solved the problem tell me
> > how ? If you use recursion 31 is a extremely enormous
> limit
> > and it works years. So a formula? How?
> I am facing the same problem. Time limite exceeding. Could
> somone advise me how to optimize the algorithm ?.program
> hanoit;
> const maxN=31;
> var i,n,nmove:integer;
>     current,target:array[1..maxN] of integer;
>
> function sama:boolean;
> var i:integer;
> begin
>   sama:=true;
>   for i:=1 to N do if current[i]<>target[i] then
>   begin
>     sama:=false;
>     exit;
>   end;
> end;
>
> procedure move(n,to_:integer);
> begin
>   inc(nmove);
>   current[n]:=to_;
>   if sama then begin writeln(nmove); readln; halt; end;
> end;
>
> procedure hanoi (n, from, to_, temp : integer);
> begin
>   if n > 0 then
>   begin
>     hanoi (n-1,from,temp,to_);
>     move(n,to_);
>     hanoi(n-1,temp,to_,from);
>   end;
> end;
> begin
>   nmove:=0;