hanoi(gray 生成算法).cpp

//使用gray code的解法 #include <iostream> #include <cmath> using namespace std #define

//使用gray code的解法
#include <iostream>
#include <cmath>
using namespace std;

#define    ZERO    0
#define    ONE    1

#define    ODD    1
#define    EVEN    0

#define    RIGHT    1
#define    LEFT    0
#define    MAX    10

inline void print(int n , int direction)
{
    cout<<"move plate "<<n<<" to "<<(direction? "RIGHT":"LEFT")<<"\tpillar" <<endl;
}
void hanoi_gray(int n)
{
    int direction , s , guard , next , i , j;
	int BITS[MAX]={0} ;

    if( n & 0x1UL ) direction = LEFT ;
    else direction = RIGHT ;

    guard = 0x1UL << n ;
    for( i = 1,j = 0,s = ODD,next = ONE ; i < guard ;  ++i , j = 0)
    {
        switch(s)
        {
            case ODD:
                BITS[0] = next;
                next = ONE - next ;
                s = EVEN ;
                print(0 , direction) ;
                break ;
            case EVEN:
                while(BITS[j++] == 0 && j < n) ;
                BITS[j] = ONE - BITS[j] ;
                s = ODD ;
                print(j , ( (j&0x1UL)?(ONE-direction):direction )) ;
                break ;
        }
    }
}

int main()
{
	int n ;
	while(1 == scanf("%d" ,&n))
		hanoi_gray(n);

    return 0;
}