「优质题解」Hanoi双塔问题

这道题的地址，想尝试的小伙伴可以来试哦：

https://www.dotcpp.com/oj/problem.php?id=1109

这是大家熟悉的汉诺塔问题，每次只能移动一次，问最少的移动次数。

思路：

1. 双盘汉诺塔和单盘汉诺塔的移动次数只有一个区别，那就是双盘的比单盘的移动次数多一倍
2. 现在来分析单盘的汉诺塔：
   • 当只有一个盘的时候，只需要移动一次；
   • 当有两个盘的时候，只需要移动三次，（最上层的那个盘需要移动两次，下面的那个盘移动一次）
   • 当盘数为n时（n>=2），我们可以将上面的n-1层看成一个盘，由于初始摆放顺序是从上往下盘子由小到大，因此，无论上面的哪个盘都是小于最底下那个盘的，而上面n-1个盘组合成的大盘移动一次所需要搬动盘子的次数，实际上就是将这n-1个盘子从一个柱子搬到另一个柱子所需要搬动的次数，我们可以再根据刚刚所分析的方法，将n-1个盘子上面的n-1个盘子当做一个盘子，以此类推，直到上面的大盘只包含一个盘子
   • 刚刚上面也分析到有两个盘子的时候，上面的那个盘子需要移动两次，下面的盘子是一次，设n个盘需要移动的次数是f(n),上面n-1个盘需要移动的次数是f(n-1)，那么就有递推式f(n)=2*f(n-1)+1;
3. 输出双盘汉诺塔结果

代码1（只能得到n范围小的结果）

题目给出的n的范围最大是200，由于n=200时结果过于庞大，上述的程序无法存储这么大的数字（即使是long long也不行），但是代码1相比代码2更容易理解解题的思想，因此这里放出来参考参考，所以：

代码2，结果通过数组进行存储（即使2000也存得下）：

若觉得文章对你有帮助，随手转发分享，也是我们继续更新的动力