终于理解汉诺塔

木子李工

/*
 * 总体思路：
 * 1.只考虑最后一步和上一步，其他的套壳来用
 * 2.假如只有一层，那一定是x-》y
 * 3.假如有两层，那么就是先x-》tmp，然后x-》y，再tmp-》y
 * 4.假如有更多层，思路其实就是
 * 5.首先将n-1曾看作一个整体，移动到tmp
 * 6.然后将最底层移动到y
 * 7.再然后将存放在tmp上的移动到y
 * 8.tmp可以不用，例如只有一层
 */
int cnt = 0;
void hano(int n, char x, char tmp, char y){


        if(n==1){
                printf("\r\n 1.(%03d) %c ->> %c", cnt++, x, y);        //最后一层，将x直接移动到y
        }else{
                hano(n-1, x, y, tmp);                                //先将除了最下面的一层移动到tmp上
                printf("\r\n 2.(%03d) %c ->> %c", cnt++, x, y);        //然后将最下面的移动到y
                hano(n-1, tmp, x, y);                                //再将刚刚移动到tmp上的移动到y上
        }
}


void main(void){
        int n;
        printf("\r\n please input hano num:");
        scanf("%d", &n);
        hano(n, 'x', 't', 'y');        
}

参考资料：
1.如何理解汉诺塔的递归？ - IT边界的回答 - 知乎
2.如何理解汉诺塔的递归？ - Fireman A的回答 - 知乎

木子李工

http://www.hannuota.cn/