汉诺塔问题的递归和非递归实现

比眉伴天荒 2022-05-27 03:35 261阅读 0赞

汉诺塔问题：古代有一个梵塔，塔内有3个基座，A基座上有64个盘子，盘子大小不等，大的在下，小的在上。有一个老和尚想把盘子由A座移到B座，但每次只能移动一个盘子，3个基座上的盘子都始终保持大的在下，小的在上。移动过程中可以利用C基座做辅助，求解其移动过程。

--------------------

汉诺塔问题是递归算法比较经典的例题，几乎是每个老师讲解递归算法时都会讲到的问题，对于任意n阶汉诺塔问题，假设有3个基座A，B， C。在基座A上放置有n个直径大小各不同，从小到大依次编号为：1、2、3…n。移动时遵循以下规则：  
       1）每次只能移动一个盘子。  
       2）盘子可以放置在A、B、C、中的任何一个基座上。  
       3）任何时候都不能将一个较大的盘子放在较小的盘子上。

--------------------

如何实现将A上的盘子按规则移动到B盘上呢？根据递归算法的思想：将一个大型复杂的问题层层转化为一个与原问题相似的规模较小的问题，在逐步求解小问题后，再回溯得到大问题的解。我们将问题进一步分解，当只有一个盘子是，我们只需要将A基座上的盘子直接移动到B基座上即可，当有两个盘子是，我们可以借助C基座完成移动过程。具体移动步骤为：A->C(第1个盘子),A->B（第2个盘子）,C->B（第1个盘子）;把n个盘子抽象的看作“两个盘子”，“一个”由1~n-1号组成，最底下是n号盘子，则移动过程为：

*  第一步：先将上面“一个”盘子（1~n-1）以A基座为起点借助B基座移动到C基座；
 *  第二步：将下面一个盘子从A基座，移动到B基座；
 *  第三步：再将C 基座上的一个盘子借助A基座移动到B基座。  
    
    
    --------------------

把n阶汉诺塔问题记作`hanoi(int n, char a, char b, char c)`，这里的A，B，C并不总代表A、B、C三个底座，其意义为：第一个参数n代表基座上的盘子数，a：代表每一次移动的起始基座，b：代表每一次移动的终点基座，c：代表每一次移动的辅助基座。由上述约定，以后的操作等价于：

*  第一步：`hanoi(n-1,a,c,b)`;
 *  第二步：将下面一个盘子从A基座，移动到B基座；
 *  第三步：`hanoi(n-1,c,b,a)`;  
    
    
    --------------------

具体移动过程如下图：

理解了上面的过程，程序就比较好实现了。

--------------------

**源代码**

//递归实现
    #include <stdio.h>
    
    void hanoi(int n, char a, char b, char c)
    {
        if (n > 0)
        {
            hanoi(n - 1, a, c, b);
            printf("move dish %d form pile %c to %c", n, a, b);
            printf("\n");
            hanoi(n - 1, c, b, a);
        }
    }
    int main()
    {
        int n;
        scanf("%d", &n);
        hanoi(n, 'A', 'B', 'C');
        return 0;
    }

--------------------

##### 非递归实现 #####

**源代码**
    #include<stdio.h>
    #define MAXSIZE 100
    
    typedef struct
    {
        int flag;  //flag存放一个标识，为0时表示直接移动一个圆盘，为1时有多个圆盘需要移动
        int num;   //存放当前圆盘数 
        char A, B, C;  //A,B,C表示3个底座
    }Stack;
    
    void hanoi(int n, char A, char B, char C)
    {
        int top = 1;
        int n1 = 0;  //圆盘个数
        int a, b, c;
        Stack stack[MAXSIZE];
        //初值入栈
        stack[top].flag = 1;
        stack[top].num = n;
        stack[top].A = A;
        stack[top].B = B;
        stack[top].C = C;
    
        while (top > 0)  //栈不为空
        {
            if (stack[top].flag == 1)  //需要移动多个圆盘
            {
                /*hanoi(n,a,b,c)退栈,相当于在递归函数中实参传递给形参*/
                n1 = stack[top].num;
                a = stack[top].A;
                b = stack[top].B;
                c = stack[top].C;
                /*hanoi(n-1,a,c,b)入栈,相当于在递归函数中的第一个递归调用 函数，将编号1->n-1的圆盘从塔座A移到C，B做辅助底座*/
                stack[top].flag = 1;
                stack[top].num = n1 - 1;
                stack[top].A = c;
                stack[top].B = b;
                stack[top].C = a;
                top++;
                /*将第n个圆盘从A移到B*/
                stack[top].flag = 0;
                stack[top].num = n1;
                stack[top].A = a;
                stack[top].B = b;
                top++;
                /*hanoi(n-1,b,a,c)入栈，相当于在递归函数中的第一个递归函数调用 函数，将编号1->n-1的圆盘从塔座C移到B，A做辅助底座*/
                stack[top].flag = 1;
                stack[top].num = n1 - 1;
                stack[top].A = a;
                stack[top].B = c;
                stack[top].C = b;
            }
            while (top > 0 && stack[top].flag == 0 || stack[top].num == 1)
            {
                /*将第n个圆盘从A移到B并退栈*/
                if (top > 0 && stack[top].flag == 0)
                {
                    /*\ "\+Enter"续行符*/
                    printf("Move dish %d form pile %c to %c\n", stack[top].num,\
                        stack[top].A, stack[top].B);
                    top--;
                }
                /*将第一个圆盘从A移动到B，并退栈*/
                if (top > 0 && stack[top].num == 1)
                {
                    printf("Move dish %d form pile %c to %c\n", stack[top].num,\
                        stack[top].A, stack[top].B);
                    top--;
                }
            }
        }
    }
    int main()
    {
        int n = 0;
        scanf("%d", &n);
        hanoi(n, 'A', 'B', 'C');
        return 0;
    }

--------------------