汉诺塔递归太难理解了_汉诺塔递归算法时间复杂度[通俗易懂]

目录

一. 题意

二. 题解及代码

一. 题意

汉诺（Hanoi）塔问题：古代有一个梵塔，塔内有三个座A、B、C，A座上有64个盘子，盘子大小不等，大的在下，小的在上（如图）。有一个和尚想把这64个盘子从A座移到C座，但每次只能允许移动一个盘子，并且在移动过程中，3个座上的盘子始终保持大盘在下，小盘在上。在移动过程中可以利用B座，要求打印移动的步骤。

注意：如果只有一个盘子，则不需要利用B座，可以直接将盘子从A移动到C。

二. 题解及代码

（1）当只有一个盘子的时候，只需要从将A塔上的一个盘子移到C塔上即可完成。

（2）当A塔上有两个盘子时，先将A塔上的1号盘子（编号从上到下）移动到B塔上，再将A塔上的2号盘子移动的C塔上，最后将B塔上的小盘子移动到C塔上即可完成。

（3）当A塔上有3个盘子时，先将A塔上编号1至2的盘子（共2个）移动到B塔上（需借助C塔），然后将A塔上的3号最大的盘子移动到C塔，最后将B塔上的两个盘子借助A塔移动到C塔上。

（4）当A塔上有n个盘子时，先将A塔上编号1至n-1的盘子（共n-1个）移动到B塔上（借助C塔），然后将A塔上最大的n号盘子移动到C塔上，最后将B塔上的n-1个盘子借助A塔移动到C塔上。

        综上所述，除了只有一个盘子时不需要借助其他塔外，其余情况的移动过程均一样，只是事件的复杂程度不一样。因此算法描述如下：

1. 上面 n-1 个盘子由A借助C移动到B；

2. 下面最大盘子由A直接移动到C;

3. 剩下n-1个盘子再由B借助A移动到C；

#include <stdio.h>
int i;

void move(int N,char move1,char move2)
{
    printf("第%d移动：第 %d 号盘子由 %c --> %c\n",++i,N,move1,move2);//每步移动调用
}

void hannuo(int N,char start,char help,char purpuse)
{
    if(N==1)
        move(N,start,purpuse);//N==1直接移动
    else{
        hannuo(N-1,start,purpuse,help);//先把前N-1个借助C移动到B
        move(N,start,purpuse);//再把最大的移动到C
        hannuo(N-1,help,start,purpuse);//最后把前N-1个借助A移动到C
    }
}

int main()
{
    int n;
    while(scanf("%d",&n)!=EOF){
        i=0;
        printf("汉诺塔的移动情况如下：\n");
        char X='A',Y='B',Z='C';
        hannuo(n,X,Y,Z);
    }
    return 0;
}

今天的文章汉诺塔递归太难理解了_汉诺塔递归算法时间复杂度[通俗易懂]分享到此就结束了，感谢您的阅读。