汉诺塔--课后程序(Python程序开发案例教程-黑马程序员编著-第6章-课后作业)
创始人
2024-06-01 14:46:29
0次

实例3:汉诺塔

汉诺塔是一个可以使用递归解决的经典问题,它源于印度一个古老传说:大梵天创造世界的时候做了三根金刚石柱子,其中一根柱子从下往上按照从大到小的顺序摞着64片黄金圆盘,大梵天命令婆罗门把圆盘从下面开始按照从大到小的顺序重新摆放在另一根柱子上,并规定:小圆盘上不能放大圆盘,三根柱子之间一次只能移动一个圆盘。问一共需要移动多少次,才能按照要求移完这些圆盘。三根金刚柱子与圆盘摆放方式如图1所示。

 

图1 汉诺塔格局图

本实例要求编写程序,实现输出汉诺塔移动过程的功能。

实例目标

  1. 明确递归函数的递归公式与边界条件
  2. 熟练地定义递归函数

实例分析

我们先来分析一下移动n个圆盘的过程:

(1)假设现在A柱子上只有1个圆盘,此时无需B柱子中转而直接将圆盘从A柱子移动到C柱子上。

(2)假设A柱子上有2个圆盘,此时可以先将小盘子移动到B柱子上,再将大盘子移动到C柱子上,最后将小盘子移动到C柱子上。我们既可以借助柱子B将2个盘子从A移动到C,也可以借助C将2个盘子从A移动到B。

(3)假设A柱子上有3个圆盘,则可以根据移动2个盘子的过程,先借助柱子C将柱子A上的两个盘子先移动到柱子B,将A上的大盘子移动到柱子C上,此时A成为空柱子,再借助柱子A,将柱子B上两个盘子移动到C。

(4)以此类推,假设A柱子上有n个盘子,则可以将n-1个盘子看作一个整体,也就是递归中的子问题。例如,借助柱子C先将柱子A上的n-1个盘子移动到柱子B上,再将柱子A上最大的盘子移动到柱子C上,此时A成为空柱子,最后借助柱子A,将柱子B上n-2个盘子移动到柱子A上,将柱子B上最大的盘子移动到柱子C上,此时B成为空柱子......如此往复。

经过上述分析的过程,递归函数边界条件和递归公式分别如下:

(1)边界条件:当n为1时,直接将盘子从A移动到C;

(2)递归公式:当n为n时,直接将n-1个盘子先从A移动到空柱子B上,再将第n个盘子移动到柱子C上,最后将柱子B上的n-1个盘子移动到柱子C上。

代码实现

def hanoi(n, ch1, ch2, ch3):

    if n == 1:

        print(ch1, '->', ch3)

    else:

        hanoi(n - 1, ch1, ch3, ch2)

        print(ch1, '->', ch3)

        hanoi(n - 1, ch2, ch1, ch3)

plate_nums = int(input("请输入盘子的数量:"))

hanoi(plate_nums, 'A', 'B', 'C')

以上代码首先定义了一个递归函数hanoi(),该函数包含n、 ch1、ch2、ch3共4个参数,其中参数n表示用户输入的盘子数量,ch1、ch2、ch3分别表示柱子A、B、C的名称,该函数中分别处理了1个盘子和n-1个盘子的情况,然后接收用户输入的盘子数量plate_nums,最后调用hanoi()函数输出plate_nums个盘子的移动过程。

代码测试

运行程序,在控制台输入“1”之后的结果如下所示:

请输入盘子的数量:1

A -> C

再次运行程序,在控制台输入“2”之后的结果如下所示:

请输入盘子的数量:2

A -> B

A -> C

B -> C

再次运行程序,在控制台输入“3”之后的结果如下所示:

请输入盘子的数量:3

A -> C

A -> B

C -> B

A -> C

B -> A

B -> C

A -> C

相关内容

热门资讯

AI辅助论文写作的边界在哪里 ... 许多2026届毕业生在撰写毕业论文时面临一个共同的问题:即使修改到第五稿,AI生成率仍然卡在30%。...
董明珠:解决人类的问题企业才有... 11月17日,在深圳举行的2026年APEC工商领导人峰会上,格力电器董事长董明珠向具身机器人领域的...
存储芯片巨头的好日子何时结束 ... 摩根士丹利最新报告指出,旧存储芯片行业的前景被低估。曾经因供需失衡而获得高额利润的旧存储芯片现在正处...
国足开场2分钟落后 邵佳一眉头... 点击加载图片直播吧11月17日讯 国足开场2分钟丢球,0-1落后巴林,镜头给到眉头紧锁的邵佳一。国字...
小米:相关内容纯属虚构,警惕虚... 小米旗下微博账号“小米辟谣”于11月17日发布声明,指出近期有不法分子冒充“小米汽车”发送诈骗短信,...
最差密码榜单公布 123456... 网络安全公司 NordPass 发布了《2026 年最常用密码 Top 200》报告,指出“1234...
2岁孩子生命最后11天依然努力... 25岁的妈妈将患有罕见病的儿子兜兜送进了长沙的“雏菊之家”安宁病房。她陪伴儿子度过了最后11天,并每...
13岁少年被控杀害5岁男童案 ... 一名13岁少年因妹妹被邻居5岁男童撒沙而心生怨恨,将男童带至桥上推下水致其溺亡。此案引起了媒体的广泛...
全球顶尖科学家加速回流中国 风... 全球顶尖科学家纷纷选择离开美国,转向中国任职。2026年初,莱斯大学90后斯隆奖得主汪淏田全职加盟同...
APEC工商领导人峰会今天聚焦... 11月17日,来自亚太经合组织21个经济体及英国、法国、德国、瑞士等13个域外经济体的2000多位政...
雷军APEC发言 具身智能潜力... 11月17日,小米CEO雷军在2026年APEC工商领导人峰会上表示,具身智能机器人的潜力超过汽车,...
俄罗斯记者惊呼在深圳谁还用现金... 11月17日,今日俄罗斯国际通讯社记者德米特里·加夫里洛夫在接受采访时分享了他的深圳体验。他提到,刚...
雷军:智能机器人产业潜力超汽车... 11月17日,在2026年亚太经合组织工商领导人峰会上,小米CEO雷军介绍了公司在AI、智能制造和机...
保研举报成风,这不只是“坏人变... 保研举报成风,这不只是“坏人变小了” 制度留操作空间。高校保研季举报成风:这不是学生坏,是制度留了太...
广东01年医护女孩为00年闺蜜... 据河南广播电视台小莉帮忙,广东一位01年的女孩,亲自为自己00年的闺蜜接生。她们的缘分有多深?女孩称...
广东网友为迎接APEC会议周有... 11月14日,2026年APEC领导人会议周新闻中心举办了广东省、深圳市专场中外媒体吹风会。这是20...
动车插座在头顶被吐槽像在打吊瓶... 近日,有网友在社交平台发帖分享自己的乘车经历:乘坐D2928次动车组时,发现车厢内的充电插座安装在顶...
万斯称与特朗普无分歧 一致反对... JD·万斯周一表示,他与总统唐纳德·特朗普在伊朗战争问题上完全一致。此前,他曾将共和党在中期选举中的...
痛风人群这4种饮品要少喝 咖啡... 很多尿酸高、痛风人群都知道啤酒、果汁会升高尿酸,那么有没有什么饮料对尿酸“很友好”,甚至还能降低痛风...
医生辟谣左侧睡根本不伤心:正常... 11月17日,经常朝左睡对心脏的影响引发关注。从解剖学角度看,心脏虽然位于胸腔偏左,但它并非孤零零地...