Go4Expert

Go4Expert (http://www.go4expert.com/)
-   C (http://www.go4expert.com/forums/c/)
-   -   Problem to understand non recursive hanoi code? (http://www.go4expert.com/forums/understand-recursive-hanoi-code-t16884/)

tonn 12Apr2009 01:30

Problem to understand non recursive hanoi code?
 
Hello!
I found in the internet a code:
Code:

#include <stdio.h>
#include <stdlib.h> 

int main() {   
int n, x;   
printf( "How many disks? " );   
scanf( "%d", &n );   
printf("\n");   
for (x=1; x < (1 << n); x++)     
printf( "move from tower %i to tower %i.\n",(x&x-1)%3, ((x|x-1)+1)%3 );

return 0; }

Problem is i cant understand (x&x-1)%3, ((x|x-1)+1)%3 ) that line, i think its something to do with bit operations, but how exactly rings moving forwards and backwards in the towers i cant understand? So maybe someone can help! In here is en.wikipedia.org/wiki/Tower_of_Hanoi something about that in the Binary solution!

asadullah.ansari 17Apr2009 10:20

Re: Problem to understand non recursive hanoi code?
 
It's not tough to understand Just try...I will give some hint...

First keep in your mind how many iterator (move) you need ....Suppose there are 3 rings named a ring, b ring, c ring . it's like stack in which top rung will be c ring and bottom one will be a ring..

ANALYSIS

>>> c ring will move move from tower 0 to tower 2.
>>> b ring will move from tower 0 to tower 1.
>>> c ring will move from tower 2 to tower 1.
>>> a ring will move from tower 0 to tower 2. ==> that will be final no move for this ring
>>> c ring will move from tower 1 to tower 0.
>>> b ring will move from tower 1 to tower 2. =>>That will also final
>>> c ring will move from tower 0 to tower 2. ==> That is also final

Just see total 8 moves required. Analyze for 4 rings..there will be 16 moves..So for n rings pow(2,n) moves required...

=> Now problem is how to make move generic , totally depends on your logic.. you can go easily by iterative or recursion method....
Tower always be number of 3 only...Given Rings will be on Tower0 and Results will be on Tower 2 and tower1 will be used as temporary...
=> In your program r= exp % 3 is used because the values of r will be always either of 0,1 ,2 .
So your program is using %3...
=> Now points how to make exp...That is only main logic of this program...Go to my Analysis part
and build the formula....that will be the same as your program is using or else you will get
some other formula..

tonn 17Apr2009 23:38

Re: Problem to understand non recursive hanoi code?
 
Thanks!


All times are GMT +5.5. The time now is 04:56.