汉诺塔

汉诺塔是什么？

问题：
汉诺塔：汉诺塔（又称河内塔）问题是源于印度一个古老传说的益智玩具。大梵天创造世界的时候做了三根金刚石柱子，在一根柱子上从下往上按照大小顺序摞着64片黄金圆盘。大梵天命令婆罗门把圆盘从下面开始按大小顺序重新摆放在另一根柱子上。并且规定，在小圆盘上不能放大圆盘，在三根柱子之间一次只能移动一个圆盘。

将第一个柱子，原模原样的移动到第三个石柱子上。

首先，明确要求：
移动圆盘时候，都必须确保大盘在小盘下面，且每次只能移动一个圆盘，最终第三个石柱子上有所有的盘子且也是从上到下按从小到大的顺序，与第一个石柱子类似。

思考解法：
首先以三个圆盘为示例，查看解决方案。

*不知道你有没有发现一个问题？

如果我们对三个柱子进行排序，标上序号：123；并且我们需要的最终结果都是第一根柱子开始，要移动到第三根柱子上。
请问：
当你移动第一个圆盘的时候，你是需要将他移动到第二根柱子还是第三根柱子上面呢？

不知道你有没有考虑过这个问题？
你只明白三块圆盘的时候需要将第一个圆盘移动到第三个柱子，如果你移动到第二个柱子，那么结果可能就是最后的结果在第二根柱子上体现。

但是这时候，如果是四块圆盘，你经过尝试你就会发现，你需要将第一个圆盘移动到第二个柱子上，才能保证最终结果正确。

其实很简单，移动圆盘有个规律：
当圆盘数为奇数时，第一个圆盘移动到第三个圆柱。
当圆盘数为偶数时，第一个圆盘移动到第二根圆柱上。

那么，代码怎么写？圆盘数目很多的时候，代码怎么写？

我们来寻找其中的规律？

圆盘数在不断的增加增加的时候，我们在移动一个圆盘的时候，为了使当前圆盘移动到第三个柱子上，其实永远只能移动二个圆盘，因为圆盘的大小有排序，你只能移动两个较小的圆盘，你现在打算要移动第三个柱子最下面的圆盘一定是目前能移动圆盘中最大的，那么这个圆盘你不可能移动到其他圆盘上，所以整个移动过程就是以二个为基础，不断的进行周期性的移动操作。
也就是：
如果圆盘的数目超过两个，将第三个及其以下的盘子忽略掉，每次处理二个盘子，也就是：1->2，1->3，2->3（用柱子序号代表圆盘移动）剩下的部分就会使周期性。
下面我们看看该规律的示意图。

• 首先，我们查看两块圆盘的移动过程：

• 下面是三块圆盘的移动过程：
  

• 移动最大的那个圆盘：
  
  可以很清楚看到，其中存在的等价关系。

• 下面完成后续操作：

依然还是有等价关系的，因此N个圆盘的操作是第N个圆盘和剩余的N-1圆盘的移动过程。

这时候我们在看看三块圆盘移动过程中，前两个圆盘的移动过程：以下图为例，进行分析讲解。

这个过程，不就是两块圆盘的移动过程吗。

因此，整个汉诺塔的移动过程是两块圆盘的移动过程的周期性循环。多个圆盘的移动情况中包含着两个小的圆盘的不断移动，这个就是递归。

下面我们总结一下，圆盘移动规律。

• 首先是整个递归的结束条件，递归首先考虑的一定是结束条件。
  最简单的移动方式就是：第一个柱上的圆盘数为1的时候，肯定就是1->3,后续根本没有操作了，因此这个条件就可以中止递归并返回。

• 下面根据我们的分析出来的，两块圆盘的移动是基础，那么，就用代码描述两块圆盘的移动过程。是且之前分析等价出来的第N块和剩下的N-1块的移动过程。
  
  蓝色代表：N-1块
  红色代表：第N块（1块）
  三个柱子是：1，2，3
  下面把整个过程表现出来：

• 首先：1 -》 2 （N-1）

• 其次：1 -》 3 （1）

• 然后：2 -》 3 （N-1）

如果有人问N-1，因为N-1部分的圆盘还是要向下减一，整个移动过程是，从N块开始一层一层递减，一直减到最初的两块移动。随后完成整个移动。
就如同我们分析三块圆盘时候，中间是包含两块圆盘的移动的。对于N-1的处理，如同N块处理相同。

整体思路确定，下面开始编写代码：

#i:第一个柱子
#j:第二个柱子
#k:第三个柱子
def Han_No_Ta(n, i, j, k):
	if (n == 1):
		print(i, "->", k)
		return
	Han_No_Ta(n - 1, i, k, j)
	Han_No_Ta(1, i, j, k)
	Han_No_Ta(n - 1, j, i, k)

Han_No_Ta(3, "1", "2", "3")

汉诺塔问题，体现了递归思想。