汉诺塔问题非递归算法集锦

巧若拙（欢迎转载，但请注明出处：http://blog.）

汉诺塔问题介绍：
在印度，有这么一个古老的传说：在世界中心贝拿勒斯（在印度北部）的圣庙里，一块黄铜板上插着三根宝石针。印度教的主神梵天在创造世界的时候，在其中一根针上从下到上地穿好了由大到小的64片金片，这就是所谓的汉诺塔。不论白天黑夜，总有一个僧侣在按照下面的法则移动这些金片，一次只移动一片，不管在哪根针上，小片必在大片上面。当所有的金片都从梵天穿好的那根针上移到另外一概针上时，世界就将在一声霹雳中消灭，梵塔、庙宇和众生都将同归于尽。
汉诺塔问题递归算法思路简单且代码简洁，算得上最美代码之一：
int count = 0;//全局变量，累积操作步数
void Hanoi(int n, char a, char b, char c)//递归算法
{
    if (n == 1)//如果只有一个盘，直接将其从a柱移动到c柱
        printf("%d: %d %c -> %c   ", ++count, n, a, c);
    else
    {
        Hanoi(n-1, a, c, b); //利用c柱中转，将n-1个盘从a柱移动到b柱
        printf("%d: %d %c -> %c   ", ++count, n, a, c);//将第n个盘从a柱移动到c柱
        Hanoi(n-1, b, a, c);//利用a柱中转，将n-1个盘从b柱移动到c柱
    }
}

    但是，非递归算法就没那么容易理解了，笔者搜集整理了以下几种方案（还有几种方案，由于本人一时未能理解，暂时不予贴出，同时请聪明的你补充简明易懂的算法，谢谢！）
    常见的思路是利用栈对递归算法进行非递归转换，李春葆老师编著的《数据结构（c语言篇）——习题与解析》（清华大学出版社）一书中介绍了一种方法。该方法设计了一个数据结构    struct act {int flag, num;  char x, y, z;} S[2000];  存储当前操作信息，其中flag==0表示直接移动num号圆盘，否则需要进一步分解；num表示当前操作移动盘子的编号，x，y，z表示当前操作对应的3个塔柱，分别是出发柱，中点柱和目标柱。
    算法的基本思路与中序遍历二叉树很类似，深入理解该算法后，我对书中的代码进行了一些改进，使其更简洁明了。代码如下：
void Hanoi_1(int n, char a, char b, char c)//非递归算法1
{
    struct act {int flag, num;  char x, y, z;} S[2000]; //存储当前操作信息，flag==0表示直接移动num号圆盘，否则需要进一步分解
    int top,  m;
    char ta, tb, tc;
   
    S[0].flag = 1;//初值入栈
    S[0].num = n;
    S[0].x = a;
    S[0].y = b;
    S[0].z = c;
    top = 0;
    count = 0;
    while (top >= 0)
    {
        if (S[top].flag == 0 || S[top].num == 1)//直接将num号圆盘从x移动到z
        {
            printf("%d: %d %c -> %c   ", ++count, S[top].num, S[top].x, S[top].z);
            --top;
        }
        else
        {  //提取栈顶信息
            m = S[top].num;
            ta = S[top].x;
            tb = S[top].y;
            tc = S[top].z;   
            //将 Hanoi(n-1, b, a, c); 操作入栈 ，覆盖原栈顶信息
            S[top].num = m - 1;
            S[top].x = tb;
            S[top].y = ta;
            S[top++].z = tc;   
            //将 将第m个盘从a柱移动到c柱 操作入栈
            S[top].flag = 0;
            S[top].num = m;
            S[top].x = ta;
            S[top++].z = tc;
            //将 Hanoi(n-1, a, c, b); 操作入栈
            S[top].flag = 1;
            S[top].num = m - 1;
            S[top].x = ta;
            S[top].y = tc;
            S[top].z = tb;
        }
    }
}

    非递归算法1是对递归算法的模拟过程，但由于其把当前操作分成两种类型，即直接移动和进一步分解，人为地增加了算法的复杂度。实际上，仔细分析二叉树的中序遍历非递归算法（详见拙作《史上最简明易懂非递归遍历二叉树算法》http://blog.），我们可以发现，完全可以采用类似的方法把汉诺塔非递归算法转化为非递归算法，思维方式几乎一模一样。代码如下：
void Hanoi_2(int n, char a, char b, char c)//非递归算法2
{
    struct act {int num;  char x, y, z;} S[MAX]; //存储当前操作信息
    int top = -1;
    int count = 0;
   
    while (n > 0 || top >= 0)
    {
        if (n > 0)//入栈，并搜索左孩子,即将 Hanoi(n-1, a, c, b); 操作入栈
        {  
            S[++top].num = n--;
            S[top].x = a;
            S[top].y = b;
            S[top].z = c;
            a = S[top].x;
            b = S[top].z;
            c = S[top].y;   
        }
        else//输出并退栈，搜索右孩子，即将 Hanoi(n-1, b, a, c); 操作入栈
        {
            printf("%d: %d %c -> %c   ", ++count, S[top].num, S[top].x, S[top].z);
            n = S[top].num - 1;
            a = S[top].y;
            b = S[top].x;
            c = S[top--].z;  
        }
    }
}

非递归算法1和2是利用栈模拟递归过程的基本方法，我们还可以从另外一个角度来分析汉诺塔问题。对于有n个盘子的汉诺塔问题，需要操作的步骤为2^n – 1，如果每一个步骤看成一个节点，则刚好构成一棵满二叉树，树高h与盘子数量的关系为h==n。结点所在的层数与对应盘子的编号关系为level==n+1-level，即盘子1在第n层，盘子n在第1层；若某个结点的操作为“盘子n从A->C”，则其左孩子操作为“盘子n-1从A->B”，右孩子操作为“盘子n-1从B->C”；中序遍历满二叉树，结点的编号恰好对应移动的次序。
因此我们可以构造一棵满二叉树，然后中序遍历该二叉树即可。代码如下：
void Hanoi_3(int n, char a, char b, char c)//非递归算法3，缺点是需要辅助空间太大
{
    struct act {int num;  char x, y, z;} BT[132000]; //存储每一步操作的满二叉树，假设n<=17.
    int S[MAX] = {0};
    int i, top, count = 0;
   
    BT[1].num = n;//为根结点赋值
    BT[1].x = a;
    BT[1].y = b;
    BT[1].z = c;
    n = pow(2, n-1);  
    for (i=1; i<n; i++)//为每个节点的左右孩子赋值
    {
        BT[i+i].num = BT[i+i+1].num = BT[i].num - 1;
        BT[i+i].x = BT[i+i+1].y = BT[i].x;
        BT[i+i].z = BT[i+i+1].x = BT[i].y;
        BT[i+i].y = BT[i+i+1].z = BT[i].z;
    }

    //中序遍历满二叉树
    n += n;
    i = 1;
    top = -1;
    while (i < n || top >= 0)
    {
        if (i < n)//入栈，并搜索左孩子
        {  
            S[++top] = i;
            i += i;
        }
        else//输出并退栈，搜索右孩子
        {
            i = S[top--];
            printf("%d: %d %c -> %c   ", ++count, BT[i].num, BT[i].x, BT[i].z);
            i += i + 1;  
        }
    }   
}

算法3的思路简明易懂，代码也很简洁，但是有一个致命缺陷，就是需要的辅助空间太多，当n较大时不太适用。有没有更好的方法呢？
    其实已经走到这一步了，再仔细观察一下这棵满二叉树，可以发现更多的规律（请读者自行画出满二叉树图，以便于理解算法）。以下是我的观察结果：
①树高h与盘子数量的关系为h==n。结点所在的层数与对应盘子的编号关系为level==n+1-level，即盘子1在第n层，盘子n在第1层;
②中序遍历满二叉树，结点的编号恰好对应移动的次序。
③第n层共2^(n-1)个结点，它们能被2^0整除且不能被2^1整除: 1,3,5,7,9,...2^n - 1.
  第n-1层共2^(n-2)个结点，它们能被2^1整除且不能被2^2整除: 2,6,10,14,...2^n - 2.
  ......
第3层 共2^2个结点，它们不能被2^(n-2)整除: 2^(n-3) * 1, 2^(n-3) * 2, 2^(n-3) * 3, 2^(n-3) * 4
  第2层 共2^1个结点，它们不能被2^(n-1)整除: 2^(n-2) * 1, 2^(n-2) * 2
  第1层 共2^0个结点，它不能被2^n整除: 2^(n-1) * 1
④奇数层各个结点的操作依次是：A->C、C->B、B->A、A->C、C->B、B->A、…模3循环;
  偶数层各个结点的操作依次是：A->B、B->C、C->A、A->B、B->C、C->A、…模3循环;
综合以上分析,得出以下结论
①盘子数N确定后,步骤总数m=2^n-1;
②第i(0<i<2^n)步所处的层数是确定的,当i能被2^(n-j)整除且不能被2^(n+1-j)整除时,i处在第j层;
③第i(0<i<2n)步在第j层的顺序号(从0开始)k=i/s，其中s = 2<<(n-j);
    根据上述分析，我们可以给出相应的代码：
void Hanoi_4(int n, char a, char b, char c)//非递归算法4，根据满二叉树的规律输出
{
    int i, level, k, s;
    int m = 1<<n;  
   
    for (i=1; i<m; i++)
    {
        for (s=2,level=n; i%s==0; s=s<<1)//判断是第几层的结点
        {
            --level;
        }
        
        k = i / s; //是第leve层第k+1个结点
        printf("%d: %d ", i, n+1-level);
        if (level & 1)//奇数层
        {
            switch (k % 3)
            {
                case 0: printf("A -> C   "); break;
                case 1: printf("C -> B   "); break;
                case 2: printf("B -> A   ");
            }
        }
        else  //偶数层
        {   
            switch (k % 3)
            {
                case 0: printf("A -> B   "); break;
                case 1: printf("B -> C   "); break;
                case 2: printf("C -> A   ");
            }
        }
    }
}

    算法3和4属于利用满二叉树特征而得出的方法，谈祥柏老师在《数学营养菜》中提到过一位美国学者发现的方法，只要轮流进行两步操作就可以了。
首先把三根柱子按顺序排成品字型，把所有的圆盘按从大到小的顺序放在柱子A上。根据圆盘的数量确定柱子的排放顺序：若n为偶数，按顺时针方向依次摆放 A B C；若n为奇数，按顺时针方向依次摆放 A C B。
（1）按顺时针方向把圆盘1从现在的柱子移动到下一根柱子，即当n为偶数时，若圆盘1在柱子A，则把它移动到B；若圆盘1在柱子B，则把它移动到C；若圆盘1在柱子C，则把它移动到A。
（2）接着，把另外两根柱子上可以移动的圆盘移动到新的柱子上。即把非空柱子上的圆盘移动到空柱子上，当两根柱子都非空时，移动较小的圆盘。这一步没有明确规定移动哪个圆盘，你可能以为会有多种可能性，其实不然，可实施的行动是唯一的。
（3）反复进行（1）（2）操作，最后就能按规定完成汉诺塔的移动。
有了这个步骤说明，代码是很容易写出来的。代码如下：
void Hanoi_5(int n, char a, char b, char c)//非递归算法5
{
    struct pillars {int S[MAX], top;  char pos;} P[3]; //存储各个柱子上的盘子信息   
    int i, count, next, pre;
   
    for (i=0; i<n; i++)
    {
        P[0].S[i] = n - i;
    }
    P[0].pos = a;
    P[0].top = n - 2; //1号盘不入栈
    P[1].top = P[2].top = -1;
   
    if (n % 2 == 0)
    {
        P[1].pos = b;
        P[2].pos = c;
    }
    else
    {
        P[1].pos = c;
        P[2].pos = b;
    }
   
    n = pow(2, n) - 1;  
    count = i = 0;
    while (count < n)
    {
        printf("%d: 1 %c -> %c   ", ++count, P[i%3].pos, P[(i+1)%3].pos);//将1号盘从顺时针移动到下一个柱子
        if (count == n)
            break;
        ++i;
        next = (i+ 1) % 3;
        pre  = (i - 1) % 3;
        if (P[next].top < 0 || P[pre].top >= 0 && P[pre].S[P[pre].top] < P[next].S[P[next].top])
        {
            P[next].S[++P[next].top] = P[pre].S[P[pre].top--];//将前一根柱子上的盘子移动到下一根柱子上
            printf("%d: %d %c -> %c   ", ++count, P[next].S[P[next].top], P[pre].pos, P[next].pos);
        }
        else
        {
            P[pre].S[++P[pre].top] = P[next].S[P[next].top--];//将下一根柱子上的盘子移动到前一根柱子上
            printf("%d: %d %c -> %c   ", ++count, P[pre].S[P[pre].top], P[next].pos, P[pre].pos);
        }
    }
}

汉诺塔问题博大精深，我稍微搜集整理了一下，就得到如此多方法，还有好些方法一时不能理解，没有贴出来，请广大网友共同探讨，分享更多更好的方法。