hanoi塔问题如下图所示_hanoi塔问题最经典的算法

大家好，又见面了，我是你们的朋友全栈君。

什么是hanoi塔?

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

问题解答

问题定义 我们把左边的柱子叫做A,中间的柱子叫做B,右边的柱子叫做C

hanoi`塔的搬运过程； i ：左边的柱子只有两个圆盘

我们先假设在A柱子上只有两个圆盘，不用图我们用大脑想象出来最佳流程就是，现在最小的放在B柱子上面然后把大的放在C上面，最后把B柱子上面的小圆盘放在C柱子上。

ii：左边的柱子上面有三个圆盘 过程如下图： `在这种情况下，我们可以把上面的两个圆盘看作是一个，然后又回到了i情况，下图展示了三个圆盘的转移过程`  iii：左边的柱子上有四个圆盘的时候 在这种情况我们通过作图做出hanoi的转移流程是很困难的了，我们可以用在`ii`中提及到的过程，就是我们先把上面的三个看作是一个，我们第一步的目的就是把前三个移动到中间的柱子上去。下面简单说一下转移步骤 1. 将A柱子上面的三个移动到B柱子上面(借助C柱子) 2. 将A柱子上面中最下面的圆盘移动到C柱子上面 3. 将B柱子上面的所有圆盘移动到C柱子上面(借助A柱子) 过程如下图：  > 问题总结 > 通过上面的描述我们把hanoi移动的步骤一般化 >

1. 将左边柱子上的N-1个圆盘移动带中间的柱子上
2. 将第N个圆盘移动到最右边的柱子
3. 将中间柱子上的所有圆盘移动到最右边的柱子

下面我们给出具体的代码

void hanoi(int n,char A,char B,char C)
{
    if(n<=1) {
        printf("1 move %c to %c\n",A,C);
        return ;
    }
    hanoi(n-1,A,C,B);
    printf("%d move %c to %c \n",n,A,C);
    hanoi(n-1,B,A,C);
}

不要在看了，这就是全部代码了。已经没有了 ╭︿︿︿╮ {/ o o /} ( (oo) ) ︶ ︶︶ 以上是对hanoi塔的总体概述，下面就要聊一聊真正的代码流程！

代码详解

hanoi(n,A,B,C)代表的意义就是讲n个圆盘从A移动到C借助B；

• 当n等于1的时候，就代表把当前A中最大的圆盘直接从A移动到C
• 当n等于2的时候，就调用hanoi(2，A,B,C)也就是执行下面的三个步骤下面就是本文中重点了

1. 调用honoi(1,A,C,B)就是相当于把***B柱和C柱交换***了
2. 执行打印语句，不进行继续调用。所以不用交换柱子
3. 调用hanoi(1,B,A,C)相当于把***B柱和A柱交换***了 上面的语句可以表述为：

hanoi(1,A,C,B); 
printf("%d move %c to %c \n",n,A,C);
hanoi(1,B,A,C); 

这就是对代码的解释！ 当圆盘更多的时候无非就是进行递归知道递归到上面的状态,比如有三个圆盘的时候，调用的是：

hanoi(2,A,C,B); //step1
printf("%d move %c to %c \n",n,A,C);
hanoi(2,B,A,C); 

只要理解了前两个对后面的理解也就不难了！还有一点题外话,当递归到程序注释的step1的时候，会为后续语句分配空间但不执行！

hanoi塔还有一个进阶的题目就是判断当前的状态时第几个最优的状态，将在下篇文章进行讲述！

版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 举报，一经查实，本站将立刻删除。

发布者：全栈程序员栈长，转载请注明出处：https://javaforall.cn/210738.html原文链接：https://javaforall.cn