代码收藏家技术教程 2023-04-18

Python实现 — — 汉诺塔问题

我们今天来看一个很有意思的实例，叫做汉诺塔问题。

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

我们编写的代码依旧遵循汉诺塔的规则—–小圆盘上不能放大圆盘，也就是说大的圆盘不能放在小的圆盘上面。

我们先来看一下代码（这里我们先设只有两个圆盘）：

count=0
def hanoi(n,a,b,c):
    global count
    if n == 1 :
        print("{}:{}->{}".format(1,a,c))
        count+=1
    else:
        hanoi(n-1,a,c,b)
        print("{}:{}->{}".format(n,a,c))
        hanoi(n-1,b,a,c)
        count+=1

hanoi(2,"A","B","C")
print(count)

我们在这里设三根柱子从左往右分别为ABC，我们先试试2个圆盘。

我们先看代码的输出:

输出部分分为两段：

（1）该怎么搬运

（2）需要多少步

怎么搬运也分为两部分:

（1）搬运的圆盘是第几层的

（2）从哪根柱子搬运到哪根柱子

一下理解代码有点困难我们先缩减代码，我们先把计算需要多少步的代码删减，你们先自己试试一下可以删减几行代码。

这是删减完的代码：

def hanoi(n,a,b,c):
    if n == 1:
        print("{}:{}->{}".format(1,a,c))
    else:
        hanoi(n-1,a,c,b)
        print("{}:{}->{}".format(n,a,c))
        hanoi(n-1,b,a,c)

hanoi(2,"A","B","C")

OK，我们缩减完代码后下一步就要将这个问题抽象，现在我们知道了题目，但怎么解呢？我们把这个解分为三步：

（1）将上面的n-1个圆盘，从A借助C移动到B

（2）将最下面的一个圆盘，从A移动到C

（3）将上面的n-1个圆盘，从B借助A移动到C

（n-1代表除了最下面一个圆盘的所有圆盘，现在不理解没关系后面有解释，现在只需要记住就行了）

接下来我们只需要理解hanoi函数，hanoi函数是一个递归函数，所以分为基例部分和递归链条部分，其中基例部分很好理解，当n=1时，则打印1:A->C。如果n>1则执行第5第6第7行代码，但我们要知道递归函数中的基例和递归链条是密不可分的，我们设n=2时，则先执行的代码是第5行，但代码不知道n=1时该怎么办，所以又重新执行函数寻找答案，代码发现当n=1时执行基例的部分，所以打印1：A->C？我们知道了代码的输出结果所以知道这是不对的，原因就是我们把函数的原本的顺序（a,b,c）变成了（a,c,b）所以输出的结果是1：A->B。

以此类推我们很快就能理解第6第7行代码了。但这样思考就是对的吗，假如现在把圆盘加到20个，那一共有1048575步，25个圆盘有33554431步，如果我们依然和二个圆盘一样去思考肯定是不行的。

这个时候我们就需要理解计算机思维，其中最重要的就是自动化和抽象，而这里就是抽象，我们要把n-1看做一个整体，看做除了最后一个圆盘的所有圆盘：