100个python算法超详细讲解：汉诺塔问题_汉诺塔递归算法及详解python

【100个python算法超详细讲解】@谷哥技术

1．问题描述
汉诺塔问题是一个古典的数学问题，它只能用递归方法来解决。在古代有一个梵
塔，塔内有A、B、C三个座。开始时A座上有64个盘子，盘子大小不同，但保证大的在
下，小的在上。现在有一个和尚想将这64个盘子从A座移动到C座，但他每次只能移动
一个盘子，且在移动过程中在3个座上都必须保持大盘在下小盘在上的状态。在移动过
程中可以利用B座，要求编程将移动步骤打印出来。汉诺塔示意图如图9.11所示。

2．问题分析
汉诺塔问题是一个著名的问题，由于条件是每次只能移动一个盘，且不允许大盘放
在小盘上面，因此64个盘子的移动次数是18 446 744 073 709 551 615这是一个天文数
字，即使使用计算机也很难计算64层的汉诺塔问题。因此在这里仅给出问题的解决方法
并解决盘子数较小时的汉诺塔问题。
首先考虑A座上最下面的盘子，如果能将它上面的63个盘子从A座移动到C座，则任
务完成。具体步骤如下：
1）将A座最上面的63个盘子移动到B座上。
2）将A座上剩下的一个盘子移动到C座上。
3）将B座上的63个盘子移动到C座上。
如果能完成上述3步，则任务完成。这种思考方法就是递归的思考方法。但实际上
问题并没有解决，在步骤1中如何将A座最上面的63个盘子移动到B座上呢？
为了解决将将A座最上面的63个盘子移动到B座上的问题，还需要做如下工作：
1）将A座上面的62个盘子移动到C座上。
2）将A座上剩下的一个盘子移动到B座上。
3）将C座上的62个盘子移动到B座上。
将这个过程进行下去，即不断地递归，继续完成移动62个盘子、61个盘子……的工
作，直到最后达到仅有一个盘子的情形，则将一个盘子从一个座移动到另一个座，问题
也就全部得到了解决，所有的步骤都是可执行的。
要说明的是，只有移动一个盘子的任务完成后，移动两个盘子的任务才能完成，以
此类推，只有移动63个盘子的任务完成后，移动64个盘子的任务才能完成，由此可知该
问题是非常典型的递归问题。
3．算法设计
该问题使用递归算法来解决。递归算法具有一些特征：为了求解规模为N的问题，
应先设法将该问题分解成一些规模较小的问题，从这些较小问题的解可以方便地构造出
大问题的解。同时，这些规模较小的问题也可以采用同样的方法分解成规模更小的问
题，并能从这些规模更小的问题的解中构造出规模较小问题的解。特别地，当N=1时，
可直接获得问题的解。
现在给出解决问题的方法。
先定义递归函数hanio(N,A,B,C)，该方法表示将N个盘子从A座借助B座移动到C座，
盘子的初始个数为N。下面是解题步骤：
若A座上只有1个盘子，此时N=1，则可直接将盘子从A座移动到C座上，问题得到
解决。
若A座上有1个以上的盘子，即N>1，此时需要再考虑3个步骤。
1）先将N-1个盘子从A座借助C座移动到B座上。显然，这N-1个盘子不能作为一个
整体移动，而是要按照要求来移动。此时，可递归调用函数hanio(N-1,A,C,B)。需要注意
的是，这里借助C座将N-1个盘子从A座移动到B座，A是源，B是目标。
2）将A座上剩下的第N个盘子移动到C座上。
3）将B座上的N-1个盘子借助A座移动到C座上。此时，递归调用函数hanio(N-
1,B,A,C)。需要注意的是，这里借助于A座将N-1个盘子从B座移动到C座，B是源，C是
目标。
完成了这3步，就可以实现预期的效果，在C座上按照正确的次序叠放好所有的盘
子。
下面以移动3个盘子为例，给出使用递归函数移动3个盘子的示意图，如图9.12所
示。

 4．确定程序框架
根据前面的分析，编写递归函数hanio(N,A,B,C)，代码如下：

def hanoi(N, A, B, C):
if N == 1: # 将A座上剩下的第N个盘子移动到C座上
print("move dish %d from %c to %c " %(N, A, C)) # 打印移动步骤
else:
借助 座将 个盘子从 座移动到 座
hanoi(N-1, A, C, B) # 借助C座将N-1个盘子从A座移动到B座
print("move dish %d from %c to %c " %(N, A, C)) # 打印移动步骤
hanoi(N-1, B, A, C)

 完成了递归函数后，只需要在main()函数中调用它，把需要移动的盘子个数传递给
它即可。
5．完整的程序
根据上面的分析，编写完整的程序如下：

#!/usr/bin/python3
# -*- coding: utf-8 -*-
# @author : liuhefei
# @desc: 汉诺塔问题
def hanoi(N, A, B, C):
if N == 1: # 将A座上剩下的第N个盘子移动到C座上
print("move dish %d from %c to %c " %(N, A, C)) # 打印移动步骤
else:
hanoi(N-1, A, C, B) # 借助C座将N-1个盘子从A座移动到B座
print("move dish %d from %c to %c " %(N, A, C)) # 打印移动步骤
hanoi(N-1, B, A, C)
if __name__ == "__main__":
#输入要移动的盘子个数
n = int(input("Please input the number of dishes："))
print("The steps to move %2d dishes are: " %n);
hanoi(n, 'A', 'B', 'C'); # 调用递归函数

6．运行结果
在PyCharm下运行程序，输入要移动的盘子数为3，则显示结果如图9.13所示。输入
要移动的盘子数为4时，则显示结果如图9.14所示。根据显示结果可知，在汉诺塔中按规
则移动3个盘子需要7步，移动4个盘子则需要15步。类似地，读者可以运行程序得出移
动更多盘子所需要的步数。