• Post Reply Bookmark Topic Watch Topic
  • New Topic

towers of hanoi  RSS feed

 
Mohamad Samy
Ranch Hand
Posts: 98
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
I knew the algorithm very well. It is by removing (n-1) disks from the source peg to the temporary peg using the destination peg as a temporary then remove the nth peg frm source to destination and so.
My problem is in the first recursive call as the first step is to remove smallest disk frm source to final then the second step is to remove bigger disk from source to temp then the thrd step is to get the smallest disk from the final to temporary.
How those three steps are done by one call like:
hanoi(2, source, temp, final)
So please can any one explain me those three steps recursively to get the output of
1- source to final
2- source to temporary
3- final to temporary
 
Steve Fahlbusch
Bartender
Posts: 612
7
Mac OS X Python
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Well actually they are not done by one call, but multiple (or recursive) calls.

I for one would change your method name from hanoi, which tells you very little about what is really being done, to something like movePile. and the method definition becomes like:

movePile ( level, from, to, hold )

Where level is the "bottom" stone to be moved; from is of course the where that pile is now, to where this pile will end up, and hold is the holding area (or what you were calling temp).


now the pseudo code becomes (general or nominal case)



Two points:

1) if you understand that what we are doing each time we call this, is that when we move pile n from a to b, we are moving pile n-1 to c, move the stone n from a to b, then move the pile n-1 from c to a. And of course that moving pile n-1 is move pile n - 2, then move stone n-1, then move pile n - 2 on top of stone n-1.

2) the special case (or terminal case) happens when n = 1 (or 0 depends on how you want to implement), but overall if level is down to 1 all you want to do is to move the stone - thats it.

Hope this helps.

-steve
 
Mohamad Samy
Ranch Hand
Posts: 98
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
I got what you said but during this.recursive call i understand the two first stes by moving stone from first pile to the end one and from the first to the temporary one. But i don't know how changing the arguments could lead to return the smallest pile from the end pile to temporary pile. Please i want this step on detail.
 
Steve Fahlbusch
Bartender
Posts: 612
7
Mac OS X Python
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
If you don't understand algorithms (and this can be especially true of recursive algorithms) then you should expand them with actual values.

So lets move from a to b with n = 1


movePile( 1, a, b, c)

that call will expand to:

moveStone( 1, a, b)

that was the trivial case


So expand with n = 2

movePile( 2, a, b, c )

expands to:

movePile( 1, a, c, b )

moveStone( 2, a, b )

movePile(1, c, b, a)

which from above expands to:

moveStone(1, a, c)

moveStone(2, a, b)

moveStone(1, c, b)

--------------------------------

There you go… try this with n=3, n=4 and n=5 and you should get a good understanding of how this is working.

-steve
 
Mohamad Samy
Ranch Hand
Posts: 98
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
You got what i want to ask about but another qustion please is that:
You said the base case is when n=1 and you mentioned a case when n=2 which i suppose it will call itself two times only. How i got three moves by only those two calls.
 
  • Post Reply Bookmark Topic Watch Topic
  • New Topic
Boost this thread!