Source code for a recursive function - Tower of Hanoi
-----------------------------------------------------
::
In article <452915$kup@uuneo.neosoft.com>,
Nguye^~n Ma.nh Hu`ng wrote:
>Does anyone have the source code for the problem of Tower of Hanoi.
No, sorry, not yet.
>It is solved with a recursive function but I do not know how to.
Well, it certainly *can* be solved with a recursive function, and the
beauty of recursion is that you don't have to know how to solve the
entire problem.
Let's say the three columns are called A, B, and C, and you're trying to
move 5 disks from A to C. It's easy:
move 4 disks from A to B using C;
move 5th disk from A to C;
move 4 disks from B to C using A.
How the middle step is accomplished depends on how you are representing
the problem: you might simply output "move 5th disk from A to C", or you
might display an animation of the disk moving, or you might direct a
robot actually to move a disk, or...
The only remaining difficulty is with the first and last steps: how do we
move 4 disks? Fortunately, this is also easy. To move 4 disks from A to
B:
move 3 disks from A to C using B;
move 4th disk from A to B;
move 3 disks from C to B using A.
The only remaining difficulty is: how do we move 3 disks? Fortunately,
this is also easy...
[ some lines omitted for brevity ]
The only remaining difficulty is: how do we move 0 disks? Fortunately,
this is also easy: do nothing.
>If you have the source code please send it to me at hnguyen@neosoft.com
It took me about 2 minutes to write the 4 line function that implements
the algorithm outlined above. Since this smells like a homework problem,
I'm not going to include it.
Tim.
--
Tim Goodwin | "MS-DOS gets this sort of lack of performance automatically,
Unipalm PIPEX | since it tends to busy-wait on everything." -- Chris Torek
Original headers::
From: tim@pipex.net (Tim Goodwin)
Newsgroups: comp.lang.c
Subject: Re: Source code for a recursive function - Tower of Hanoi
Date: 6 Oct 1995 12:17:05 GMT
Organization: Unipalm PIPEX
Message-ID: <4536o1$mmv@wave.news>
References: <452915$kup@uuneo.neosoft.com>