用格雷码的方法解决汉诺塔问题

　　说到汉诺塔问题，首先想到的是最经典的递归解法。今天看到求格雷码的方法，里面提到可以观察格雷码每一次改变的位数和汉诺塔每次移动的盘子的编号，从而产生一种不需要递归和堆栈的汉诺塔解法。

　　在生成格雷码的算法中，依次改变的位数是最低位和从右往左数第一个1所在位的左一位，对应汉诺塔的盘子就是最小的盘子和中间某个盘子。最小的盘子有两种可能的移动方案，其他的盘子只有一种可能。对于最小盘子移动到的柱子的解决方法是，根据观察，当盘子总数是奇数时，最小盘子的位置依次是“3->2->1->3->2->1...”；当总数是偶数时，这个顺序是“2->3->1->2->3->1...”。据此从格雷码到汉诺塔的一种对应解决方案就产生了。如下是递归和非递归两种方法的代码。

　　

#include<iostream>
using namespace std;
#define MAX 20
#define YES 1
#define LOOP 1
#define FLIP_DIGIT(x) x=((x)=='0'?'1':'0')
#define FLIP(x) x=(1-(x)) 
int n;
void move(int num, int from, int via, int to){
    if(num == 2){
        cout<<from<<"->"<<via<<endl;
        cout<<from<<"->"<<to<<endl;
        cout<<via<<"->"<<to<<endl;
    }
    else{
        move(num-1, from, to, via);
        cout<<from<<"->"<<to<<endl;
        move(num-1, via, from, to);
    }
}
int main()
{
    cin>>n;
    cout<<"This is recursion method"<<endl;
    cout<<"========================="<<endl;
    move(n,1,2,3);
    cout<<"========================="<<endl;
    cout<<"This is gray code method"<<endl;    
    cout<<"========================="<<endl;
    char digit[MAX];
    int position[MAX];
    int i,j;
    for(i = 0; i < MAX; i++){
        digit[i] = '0';
        position[i] = 1;
    }
    int even = YES;
    int circle[3];
    circle[2] = 1;
    if(n % 2 == 0){
        circle[0] = 2;
        circle[1] = 3;
    }
    else{
        circle[0] = 3;
        circle[1] = 2;
    }
    i = 0;
    int m = 0;
    while(LOOP){
        m++;
        if(m > 20)
            break;
        if(even){
            cout<<position[0]<<"->"<<circle[i]<<endl;
            position[0] = circle[i];
            i = (++i)%3;
            FLIP_DIGIT(digit[0]);
        }
        else{
           for(j = 0 ; j < n && digit[j]=='0'; j++)
                ;
           if(j == n-1){
                break;
            } 
            FLIP_DIGIT(digit[j+1]);
            cout<<position[j+1]<<"->"<<6-position[j+1]-position[0]<<endl;
            position[j+1] = 6-position[j+1]-position[0];
        }
        FLIP(even);
    }    
    cout<<"========================="<<endl;
    system("pause");
    return 0;
}