Tower of Hanoi. 1

[SwapSawe]

Hi Friends !!!!

Can you help me with algorithm of Tower of Hanoi using Recursion.

Thanx,
SwapSawe.

 

[mdktindia]

let me suppose that 3 pegs are namely
S : source
T: temp
D: destination

the algorithm is that for moving n disk from S to D you have to move n-1 disks (how to move will discuss now) from S to T and then move 1 disk left from S to D, finally move n-1 disks from temp to D.

but how to move n-1 disks from S to T (as well as n-1 disks from T to D), now we consider T plays as D, and D plays as T, therefore, the problem is to move n-1 disks from S to D(T), similar to the talk above, move n-2 disks from S to T(D), move 1 disk left from S to D(T), move n-2 disks from T(D) to D(T). the process is continued until we reach 1 disk and that time we just move directly from S to D.

The recursion here is for moving n disks, we have to move n-1 disks, for moving n-1 disks, we have to move n-2 disks and so on, until we only have to move 1 disk.

Maybe my explaination is not clear but anyway, i hope this helps you!


mdktindia

 

[SwapSawe]

Hey mdktindia,

I think You are right not about logic i am talking about that last line..... the explanation is very much confusing. It would be a great help if you add either an algo or code; I think that will be easier to understand.

Regards,
SwapSawe.

 

[aphrodita]

You do not really want to see the code. It is just about 10 lines, with 2 recursive calls inside.
The first recursive call would move all but the lowest disk on an auxilary one, and then move the biggest of them to the final destination. As you do it, you again have two towers to mave around your disks, because if you put any disk on top of the biggest, it does not break the rule.
The second recursive call, makes the first one to solve the problem for n - 1 disks, and at the end of it, it will move the pre-biggest disk on top of the biggest in the 3rd tower. Totally, it will happen n time, making the problem smaller each time, until n becomes 1, which is to mave the last disk on top of all in the 3rd tower.

template <class Q>
void Hanoi(n,T Start, T Auxilary, T End)
{
if (n != 0)
{
Hanoi((n-1),Start,End,Auxilary);
Move(Start,End);
Hanoi((n-1),Auxilary,Start,End);
}
}

// That's it
Best Regards,

aphrodita@mail.krovatka.ru {uiuc rules}

http://www.hellforge.org