Mohamad Samy

Ranch Hand

Posts: 98

posted 3 years ago

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

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

posted 3 years ago

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

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

posted 3 years ago

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.

posted 3 years ago

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

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