python语言汉诺塔问题

python语言汉诺塔问题

汉诺塔问题，是编程语言中学习递归经常学习的一道题，但是其流程却很难理解。现结合我学python的过程，将这个问题分析一下。

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

# 上代码，利用递归函数移动汉诺塔:

def move(n, a, b, c): #将盘子从A柱上借助B柱移到C柱上

if n == 1: #如果盘子数是一个，直接将盘子从A柱移到C柱

print('move', a, '-->', c)

return

move(n-1, a, c, b) #将A柱第n个盘子上面的n-1个盘子借助C柱虚拟移到B柱，此时，这n-1个盘子已经在B柱上

print('move', a, '-->', c) #将第n个盘子虚拟移到C柱上

move(n-1, b, a, c) #将B柱上的n-1个盘子移到C柱上

至此，问题解决。但是如果不继续分析其下一步骤的话，只会知其然，不知其所以然。

首先，我们调用move函数时，一开始盘子数是n；

其次，调用move函数一次结束后，下一次调用的函数变为move(n-1, b, a, c),那么这时move函数的状态(是状态，不是定义)实际是这样的：

def move(n-1, b, a, c):

if n-1 == 1:

print('move', b, '-->', c )

return

move(n-2, b, c, a) #将上面的n-2个盘子借助c柱先移到a柱上

print('move', b, '-->', c) #将第n-1个盘子移到c柱上，至此，第n个盘子和第n-1个盘子被成功移到c柱上

move(n-2, a, b, c) #最后将上面的n-2个盘子再移到c柱上

最后剩下的流程，继续重复以上步骤就行了，直到move函数的第一个参数等于1。

其实，仔细分析可以发现，参数c也就是第三根柱子在move函数一次调用完成后的位置是不变的，变化的是a和b的位置，他们是交替变化的，也就是说借助a和b将盘子交替移到c上，函数调用完成后，都是将一个盘子移到C上。

第一次调用时，是a,b,c；第二次调用时，就成了b,a,c；然后再一次，又变成了a,b,c,就这样，把盘子一个一个地移到c柱。

其总体思路就是：先将n-1个盘子移到B柱，再将第n个盘子移到C柱；然后，将B柱上的n-2个盘子移到A柱，将B柱上的第n-1个盘子移到C柱……剩下的盘子以此类推，最终目的都是C柱。