摘要：概述汉诺塔是一个经典的递归问题，虽说看人家写好的算法程序就那么几行，但着实理解有一定的难度。查阅了一些资料，参阅别人的思路，对汉诺塔算法进行一番梳理。问题来源有一个梵塔，塔内有三个座，座上有若干个盘子，盘子大小不等，大的在下，小的在上如图。
概述
汉诺塔是一个经典的递归问题，虽说看人家写好的算法程序就那么几行，但着实理解有一定的难度。查阅了一些资料，参阅别人的思路，对汉诺塔算法进行一番梳理。
问题来源有一个梵塔，塔内有三个座A、B、C，A座上有若干个盘子，盘子大小不等，大的在下，小的在上（如图）。
需要把这些个盘子从A座移到C座，中间可以借用B座，但每次只允许移动一个盘子，并且在移动过程中，3个座上的盘子始终保持大盘在下，小盘在上。
实例我们从简单的来看一下如何移动。
只有一个盘子
傻子也知道，直接移动到C座就OK了。
有两个盘子 [1 2]
把1移动到B
把2移动到C
把1移动到C
有三个盘子 [1 2 3]
把1移动到C
把2移动到B
把1移动到B
把3移动到C
把1移动到A
把2移动到C
把1移动到C
虽说好像感觉有一定规律，但好像说不出来个所以然。
规律对于上面的例子，我们可以总结出两点：
最后一步肯定是把1移动到C
如果盘子数大于1（1就直接移了），肯定要把最大的盘子上面的全部盘子放到B上，然后将最大的放到C上
由上面的两点，我们来探究一下递归关系。
假设有n个盘子，分别标记为 [1 2 3... n] 大数表示大盘子，已经在A座上放好。
初始状态
A：有n个盘子 B：空 C：空
我们现在有一个方法：hanoi(int n, String a, String b, String c) ，作用就是将n个盘子从a座借助b座移动到c座。
我们先不考虑它是怎么移过去的。
下面我们使用这个方法，结合上面我们总结的规律进行移动盘子。
第一步，将[1 2 3... n-1]个盘子从A移动到B上，再将 n 盘子移动到C上
hanoi(n-1, A, C, B) // 将A上的n-1个盘子移动到B上 hanoi(1, A, B, C) // 将A上的一个盘子移动到C
现在我们的盘子情况为
A：空 B：有n-1个盘子 C：最大的n盘子
由于最大的n盘子上可以放任何盘子，你可以完全忽略它的存在，不用管它，这时候的情形（忽略n盘子的存在）是不是跟初始状态类似呢（一个有盘子，其余的没有盘子）？是的，只不过顺序发生的变化并且盘子的数量减少了一个。
我们的总盘子数为：n-1
我们的B座就是初始状态的A座，A座就是初始状态的B座，C座还是C座。
第二步，将B座上的[1 2 3... n-1-1] 从B移动到A上，将n-1盘子从B移动到C
hanoi(n-2, B, C, A) // 将B上的n-1-1个盘子移动到A上 hanoi(1, B, A, C) // 将B上的一个盘子移动到C
现在我们的盘子情况为
A：有n-1-1个盘子 B：空 C：最大的n盘子和倒数第二个n-1盘子
C上的盘子已经摆好，可以认为是空座，是不是又回到了初始状态的情形呢？是的，盘子数减一。
第三步，将A座上的[1 2 3... n-2-1] 从A移动到B上，将n-2盘子从A移动到C
hanoi(n-3, A, C, B) // 将A上的n-2-1个盘子移动到A上 hanoi(1, A, B, C) // 将A上的一个盘子移动到C
又回到类似第一步执行后的情形了，如此反复，直到所有盘子都成功移动到C上为止。
经过上述的推敲，我们知道，每经过一步，盘子数少一个，并且A和B两座的位置互换（这里指他们轮流充当初始状态A的角色）。
代码实现(Java)public static void hanoi(int n, String a, String b, String c) {
if (n == 1) {
System.out.println("将" + a + "最上面的盘子移动到" + c);
return;
}
// 当前盘子在a上，将当前盘子数-1放到b上
hanoi(n-1, a, c, b);
// 剩下一个放到c上
hanoi(1, a, b, c);
// 当前盘子在b上，b是下一轮的a， a b 换位置，进行下一轮
hanoi(n-1, b, a, c);
}
调用：
hanoi(1, "A", "B", "C"); // 将A最上面的盘子移动到C hanoi(2, "A", "B", "C"); // 将A最上面的盘子移动到B // 将A最上面的盘子移动到C // 将B最上面的盘子移动到C hanoi(3, "A", "B", "C"); // 将A最上面的盘子移动到C // 将A最上面的盘子移动到B // 将C最上面的盘子移动到B // 将A最上面的盘子移动到C // 将B最上面的盘子移动到A // 将B最上面的盘子移动到C // 将A最上面的盘子移动到C
解释一下a b c 和A B C的关系
A B C是实际的盘子座，a b c表示的是一种状态，即初始状态a 表示有待移动的若干个盘子的座，b c始终表示空座（c上可能有盘子，但已经摆好，可以认为为空）。
每移动一轮，A座与B座交换存盘子，若A有盘子，A就是参数a，若B有盘子，B就是参数a，C位置不动。
总之a 始终代表堆着盘子的座。
文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。
转载请注明本文地址：https://www.ucloud.cn/yun/65418.html
摘要：应用分治法是一种很重要的算法。字面上的解释是分而治之，就是把一个复杂的问题分成两个或更多的相同或相似的子问题，再把子问题分成更小的子问题直到最后子问题可以简单的直接求解，原问题的解即子问题的解的合并。 ...
摘要：汉诺塔问题有三根柱子，源杆，暂存杆，目的杆上有层盘子，由小到大向下排列，现需要将杆的盘子移到杆中要求大的盘在下面，小的盘在上面一次只能移动一个盘子个人思路先分析问题，用数学的归纳法当只有一个盘时，直接移动当有两个盘时，先将小的移到暂存杆，再 汉诺塔问题： 有三根柱子，源杆A，暂存杆temp，目的杆C A上有n层盘子，由小到大向下排列，现需要将A杆的盘子移到C杆中 ...
摘要：由此可知在前柱是中转柱在之后也有两种情况只有上有圆盘。并且我们的游戏目标从一开始的把上所有圆盘移到柱变成了把上所有圆盘移到柱上而在这时中转柱是柱。现在将步骤分为三个小步骤将上个圆盘全部移到柱上中转柱柱。 一.汉诺塔问题 汉诺塔是一种古印度游戏，该游戏的实质就是在一块木板上有三根固定的柱子...
阅读 3040·2021-09-22 15:54
阅读 3951·2021-09-09 11:34
阅读 1748·2019-08-30 12:48
阅读 1144·2019-08-30 11:18
阅读 3408·2019-08-26 11:48
阅读 847·2019-08-23 17:50
阅读 2095·2019-08-23 17:17
阅读 1222·2019-08-23 17:12
