1. This site uses cookies. By continuing to use this site, you are agreeing to our use of cookies. Learn More.

Problem to understand non recursive hanoi code?

Discussion in 'C' started by tonn, Apr 11, 2009.

  1. tonn

    tonn New Member

    Joined:
    Apr 11, 2009
    Messages:
    2
    Likes Received:
    0
    Trophy Points:
    0
    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!
     
  2. asadullah.ansari

    asadullah.ansari TechCake

    Joined:
    Jan 9, 2008
    Messages:
    356
    Likes Received:
    14
    Trophy Points:
    0
    Occupation:
    Developer
    Location:
    NOIDA
    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..
     
  3. tonn

    tonn New Member

    Joined:
    Apr 11, 2009
    Messages:
    2
    Likes Received:
    0
    Trophy Points:
    0

Share This Page