# Problem to understand non recursive hanoi code?

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

1. ### tonnNew Member

Joined:
Apr 11, 2009
Messages:
2
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!

Joined:
Jan 9, 2008
Messages:
356
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..

Joined:
Apr 11, 2009
Messages:
2