汉诺塔是指这个：
目标是要把所有的盘子从最左边（柱子A）移动到最右边（柱子C），条件是
1）每次只能移动一个盘子
2）小盘子只能放在大盘子之上
首先考虑最简单的情况：只有1个盘子，那么只要A—>C就可以了，一步就ok。
如果有两个盘子，那么移动顺序如下：先把最上面的盘子（1号盘）移动到B，然后2号盘移动到C，然后1号盘从B移动到C，总共需要3步。
如果是n个盘子呢？
可以用倒推法来考虑这个问题：无论怎么移动，最底下的那个最大号盘子（n号盘）一定是A—>C的，在这之前，我们一定要把所有的上面的小盘子（n-1个盘子）都移动到B上，否则n号盘是无法从A移动到C的。然后，一旦最大号的n号盘从A—>C，我们剩下的工作就是把所有的n-1个盘子从B移动到C。
所以虽然有n个盘子，但是思考的时候，只要把n个盘子看做2个部分就行：n号盘，以及n号盘之上的所有n-1个盘子。
移动的时候的原则就如下表示：
第一阶段：（n-1）A—>B（把所有的n-1个盘子从A移动到B上）
第二阶段：n A—>C（把最底下的n号盘从A移动到C上）
第三阶段：（n-1）B—>C（把n-1个盘子从B移动到C上）
我们来看看如何执行第三阶段，现在的状况是n号盘已经在C上面了，（n-1）个盘子都在B上，为了达成所有盘子都移动到C上的目标，我们要做的就是把B上的最底下的盘子——也就是（n-1）号盘也移到C上。那么（n-1）号盘上面的总共（n-2）个盘子怎么办呢？那当然只有往A上挪咯。
现在（n-2）个盘子都在A上，咋办呢？当然是跟上面步骤一样，第（n-2）号盘子放到C上去，剩下的所有（n-3）个盘子挪到B上。
同样的方法对待n-3、n-4......直到最后只剩下1号盘子。然后把刚才的方法逆序做一遍，就成功啦。
这里有个数学方法，叫递归，也就是我们对待n个盘子、n-1个盘子、n-2个盘子....的方法都是一样：都是把除了最底下以外的盘子移到别的柱子上去，然后把最底下的盘子移到C上。这个不停重复的过程，就是递归。
再举一个递归的例子：比如我定义一个函数：f(x)=2*f(x-1)且f(1)=1，那么f(4)是多少？
f(4)=2*f(3)
f(3)=2*f(2)
f(2)=2*f(1)
根据定义，f(1)=1，所以f(4)=2*(2*(2*f(1)))=8。这个函数不停重复调用自己，就是递归函数。
方法弄清楚了，现在我们的目标是写个小程序，能自动把每一步的移动打印出来。
条件是给定n个盘子，三根柱子ABC，把汉诺塔的每一步移动都打印出来，就可以用递归函数来解决。代码如下(#后面是解释说明，不是程序代码）：
#先定义一个move函数，有4个参数，n代表有n个盘子，abc对应三根柱子ABC，如下：
def move(n, a, b, c):
#设定如果n=1的情况，直接打印a—>c
if n == 1:
print ('请移动：', a, ‘—>’, c)
#如果n>1，就要把n-1个盘子移动到B上去（可以经过c）
move(n-1, a, c, b)
#然后把剩下的n号盘从A移动到C
print (‘请移动：’, a, ‘—>’, c)
#最后把在B上的n-1个盘子都挪到C上去（可以经过a）
move(n-1, b, a, c)
现在程序写好了，如果我们输入move(3, A, B, C)，意思是有3个盘子，ABC三根柱子，程序会根据函数的定义把原始的move变成这样：
move(2, A, C, B)
print (‘请移动：’, A, ‘—>’, C)
move(2, B, A, C)
这里的move(2, x, x, x,)，程序会怎么处理呢？当然是继续分解啦。比如move(2, A, C, B)会根据函数的定义被拆解成：
move(1, A, B, C)#代表剩下的盘子要从a移动到c，注意这里有个位置交换，因为在定义里参数的位置交换了，所以值的位置也要交换
print (‘请移动：’, A, ‘—>’, B)#代表最底下的盘子（第n-1号盘子）从A移动到B
move(1, C, A, B)#剩下的盘子从C移动到B
如果n>3的话也是一样的，一层一层分解，一直分解到n=1的情况为止。哦对了，听说n=64的时候，即使每秒移动一个盘子，整个儿移到C上也需要5845.54亿年以上。
地球的寿命我记得是45亿年？
网友评论