I need to write the pseudocode for the Hanoi algorithm, the problem
goes like this:
The "Towers of Hanoi" problem is the following: You are given three
vertical rods (the towers), numbered 1, 2, and 3. On the first rod are
stacked n
rings of decreasing size. The goal is to transfer all rings on
the second rod. The only operation allowed is to take a single ring
from the top
of one of the towers and to move it to the top of another tower,
provided the
ring is not larger than the ring already on top of that tower (if any).
In other
words, for each towers and at any point in time, the rings have to be
stacked in
decreasing size. The question is to write a recursive algorithm that
prints the series
of moves required to transfer all n rings from rod i to rod j. This
seems
awfully difficult until you realize the following. Assume rod i has the
m smallest rings
of all three towers. To transfer the m smallest rings from rod i to rod
j, all
one needs to do is to
1) first transfer the m - 1 smallest rings from rod i to rod k = 6 - i
- j,
2) then transfer the m-th ring from rod i to rod j,
3) finally retransfer the m - 1 smallest rings from rod k to rod j.
Notice that step (1) and step (3) are just smaller versions of the same
original problem. for m = 3, i = 1, j = 2. The question is to write a
procedure Hanoi(m, i, j) that prints (using the pseudocode keyword
"print") the series of moves needed to move
the top m rings from rod i to rod j.
I know how to write the algorithm for the function Hanoi(m,i,j,k) but I
don't understand how to do this with only Hanoi(m,i,j) without the k
variable
for Hanoi(m,i,j,k) it would be
if m is not 0
Hanoi(m-1,i,j,k)
move m from i to j
Hanoi(m-1,k,i,j)
else
stop
and then
Let T(m) be the number of moves required to move m rings from one rod
to another using your algorithm. Give a recurrence expressing
T(m) in
terms of T(m - 1).
and then
Guess an explicit formula for T(m) (i.e. a formula that doesn't have
T(m - 1) on the right part) and prove by induction that your guess was
correct for any m >= 0.
and the last question I have is how do i do this:
Let T(n) = 1 if n = 1
2*T(n - 1) + 1 if n > 1
Prove by induction that T(n) = 2^n - 1 for any n >= 1.
Any help will be REALLY appreciated.
Thank you in advance.
--~--~---------~--~----~------------~-------~--~----~
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to [email protected]
To unsubscribe from this group, send email to [EMAIL PROTECTED]
For more options, visit this group at http://groups.google.com/group/algogeeks
-~----------~----~----~----~------~----~------~--~---
