用Python中的递归实现汉诺塔

欢迎大家来到IT世界,在知识的湖畔探索吧!

本实战技能将使用递归来实现汉诺塔，运 行时要求用户输入一个自然数，表示初始柱子上的盘数，并初始化三根柱子，如分别输入“3”“A”“B”“C”，则表示如何移动圆盘实现汉诺塔。运行程序得到的结果如下图所示。

欢迎大家来到IT世界,在知识的湖畔探索吧!

汉诺塔的实现结果

【技术要点】

要实现本案例，需要详细了解汉诺塔问题及其解决方案。

1）汉诺塔问题

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

2）汉诺塔实现

在利用计算机求汉诺塔问题时，必不可少的一步是对整个实现求解进行算法分析。到目前为止，求解汉诺塔问题最简单的算法还是递归算法。简单来说，递归就是一个方法或者函数，在这个函数里有调用自身函数的语句。要使这种调用能够正常结束，必须在函数里有一个结束点，具体地说，是在调用最后一次后，函数能返回一个确定的值，根据这个确定的值，可以得到倒数第二次调用时的返回值，依次向前推进，得到第一次调用这个函数的返回值。

实现这个算法可以简单分为3个步骤。

Step1：把第n—1个盘子由a柱移到 b柱。

Step2：把第n个盘子由 a柱移到 c柱。

Step3：把第n—1个盘子由b柱移到 c柱。

从这里入手，再加上数学问题解法的分析，不难发现，移动的步数必定为奇数。

（1）中间的一步是把第n个盘子从a柱移到c柱上去。

（2）中间一步之前可以看成把a柱上第n—1个盘子借助辅助塔（c塔）移到了b柱上。

（3）中间一步之后可以看成把b柱上第n—1个盘子借助辅助塔（a塔）移到了c柱上。

汉诺塔实现图解如下图所示。

汉诺塔实现图解

【主体设计】

汉诺塔的实现流程如下图所示。

汉诺塔的实现流程图

汉诺塔的实现具体通过以下5个步骤实现。

Step1：初始化盘数，并初始化三根柱子。

Step2：判断输入的盘数是否为1，若是，则执行Step3；若不是，则执行Step4。

Step3：移动盘子。

Step4：返回Step2，继续判断盘数是否为1，重复Step3。

Step5：输出返回列表。

【编程实现】

本实战技能使用Jupyter Notebook进行编写，建立相关的源文件【汉诺塔的实现.ipynb】，

在相应的【cell】里面编写代码。具体步骤及代码如 下所示。

Step1：实现递归的执行函数，代码如下所示。

1. def move(n, a, b, c): # n 为圆盘数，a 代表第一根初始圆柱，b 代表第二根过渡圆柱，

2. # c 代表第三根目标圆柱

3. if n == 1:

4. print(” 从 “, a, ” 柱移动到 “, c, ” 柱 “)

5. else:

6. move (n-1, a, c, b) # 将第一根圆柱的第 n—1 个圆盘移动到第二根过渡圆柱，

7. # 此时上一级函数的第二根圆柱为目标圆柱，第三根

8. # 圆柱为过渡圆柱，第一根为初始圆柱

9. print(” 从 “, a, ” 柱移动到 “, c, ” 柱 “)

10. move(n-1, b, a, c) # 将过渡圆柱的第 n—1 个圆盘移动到目标圆柱，

11. # 此时上一级函数的第二根圆柱为初始圆柱，

12. # 第一根圆柱为过渡圆柱，第三根圆柱为目标圆柱

Step2：实现程序主流程。

1. D = int(input(” 请输入初始盘子数：”))

2. E = input(” 请输入初始柱子名称：”)

3. F = input(” 请输入过渡柱子名称：”)

4. G = input(” 请输入目标柱子名称：”)

5. print(” 具体的移动过程如下：”)

6. move(D, E, F, G) # 调用上面自定义的函数，可以实现汉诺塔