当前位置:首页>python>用Python中的递归实现汉诺塔

用Python中的递归实现汉诺塔

  • 2026-10-21 13:28:14
用Python中的递归实现汉诺塔

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

汉诺塔的实现结果
【技术要点】
要实现本案例,需要详细了解汉诺塔问题及其解决方案。
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) # 调用上面自定义的函数,可以实现汉诺塔

今日推荐好书

本书全面系统地介绍了Python语言区块链应用工程师所需的基础知识和相关技术,主要分为Python基础篇、区块链技术篇和区块链开发篇三部分。

全书共10章,其中第1~3章为Python基础篇,介绍Python语法基础、Python的语法特色、Python与数据库操作等内容;第4~6章为区块链技术篇,介绍初识区块链、区块链的技术原理、区块链技术的发展趋势;第7~10章为区块链开发篇,介绍Solidity智能合约开发的入门和进阶、Python语言离线钱包开发、通过Python和Solidity开发一个“赏金任务系统”,项目中将使用FISCO BCOS联盟链作为基础,结合Django框架,并应用Python-SDK与区块链交互完成数据的读写操作,完成一个区块链的Web项目。

本书内容系统全面,案例丰富翔实,既适合想学习Python语言编程和区块链开发的初学者阅读,也适合作为区块链行业从业者、金融科技爱好者的学习用书,还可以作为广大职业院校相关专业的教材参考用书。

关联好书推荐

往期内容回顾

四步明确Excel细节,让你的图表更专业

一个示例让你掌握如何在Origin中绘制折线图

区块链是不可篡改的,那智能合约可以升级吗?

最新文章

随机文章