Python实现 — — 汉诺塔问题

这篇具有很好参考价值的文章主要介绍了Python实现 — — 汉诺塔问题。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

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

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

Python实现 — — 汉诺塔问题

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

我们先来看一下代码(这里我们先设只有两个圆盘):

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个圆盘。

我们先看代码的输出:

Python实现 — — 汉诺塔问题

输出部分分为两段 :

(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看做一个整体,看做除了最后一个圆盘的所有圆盘:

我们不断的将n进行n-1的操作,直到n=2时,再算出来的n就等于1了,这个时候n就会进入基例部分不会进入递归链条

所以n-1就是除了最后一个圆盘的所有圆盘,这样理解的话我们瞬间就能理解第5行代码在干什么了,第5行代码表达的意思就是第一步,把n-1个圆盘移到B柱子上,接下去的第6第7行分别对应着第二和第三步。

怎么样有没有醍醐灌顶,如果你之前无法理解什么叫抽象那么想现在应该能初步理解一点了。那么这次精彩的实例分享就到此结束了,在这里我祝大家在2023年里学习一帆风顺,bug越来越少。文章来源地址https://www.toymoban.com/news/detail-441566.html

到了这里,关于Python实现 — — 汉诺塔问题的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 小红书笔记无法展示是什么原因?让我们来看看吧

          最近有的小伙伴发现自己的笔记发布后却不被系统展示,不知道是怎么回事,今天就来分析分析小红书笔记无法展示是什么原因,以及笔记内容应该注意些什么。      首先,小红书笔记无法展示是什么原因呢?可能是内容不宜展示,也可能是被判定违规了。 一、在小

    2024年02月05日
    浏览(81)
  • 今天我们来浅谈一下ChatGPT到底是什么东西

    这是一篇非学术专业性的文章,而我也是为了解chatGPT而学了两三天人工智能,所以哪里写的不好的不对的地方还希望海涵。 图灵测试 1950年,人工智能之父艾伦·图灵提出乐“图灵测试”。就是说当你在不面对面的时候跟机器人进行文字聊天的时候,如果你很难分辨出来对方

    2023年04月09日
    浏览(40)
  • 选购哪种护眼灯对眼睛好,让我们一起来看看吧

    在日常生活中,护眼灯已经是成为家庭流行使用的照明工具之一,护眼灯对视力是有一定帮助的,会摒弃摁掉一些日常灯具,对眼睛造成伤害的可能性,比如说蓝光,对人们的视力有不可逆的损伤,而护眼灯就过滤掉蓝光危害,还有频闪问题等等,护眼灯投射出来的光,会更

    2023年04月08日
    浏览(39)
  • 今天我们来说说常用的三种排序算法:选择排序、插入排序、快速排序

    原文链接:http://www.ibearzmblog.com/#/technology/info?id=8ac4902f82f525e1456624d5d7a545dc 选择排序、插入排序、快速排序这三种算法算是比较初级的排序算法,对它们的原理和技巧,可以方便我们对后面的算法理解。 温馨提示,因为动图不好弄,所以我在网上下载了AlgorithmMan来进行动图演示

    2024年02月16日
    浏览(38)
  • 解决一个程序问题需要多少步——确定我们没有在摸鱼

    3 天前,运行的社区系统报告,很多老的历史照片都无法作为附件加载 —— 小鲨鱼,快来解决问题。 很多人都问题,为什么程序员每天不是在调 Bug 就是在调 Bug 的路上。 其实呀,计算机是一个逻辑性非常强的东西,每一步都应该是原因的,所以我们要通过逻辑性找到不同的

    2024年02月09日
    浏览(46)
  • 还在为表情包而发愁吗?今天教你用 Python 画一个奸笑(滑稽)表情(内附源码)

    微信自带的表情大家应该都用过,其中奸笑(其他的平台也有叫滑稽的)的表情使用率算是比较高的,对于这个表情,有的人喜欢,也有的人不喜欢,这个都是正常的,我们不讨论这个。 大家应该都知道 Python 的 turtle 库可以画画,本文我们就使用这个库画一个奸笑表情。 注

    2024年02月04日
    浏览(45)
  • Google I/O 2023 大会上发布了一些令人兴奋的技术和产品,让我们一起来看看吧!

    Google I/O 2023 大会上发布了一些令人兴奋的技术和产品,让我们一起来看看吧! Google I/O 2023 的日期和地点 Google I/O 2023 于 5 月 10 日在美国加州山景城的海岸线圆形剧场举行12。这是 Google 每年举办的开发者大会,旨在展示 Google 的最新解决方案、产品和技术。今年的大会有限制

    2024年02月04日
    浏览(52)
  • 如何在C++中将int类型的变量转换为string类型呢?今天我们就来介绍两种方法。

    如何在C++中将int类型的变量转换为string类型呢?今天我们就来介绍两种方法。 第一种方法是使用C++11标准引入的std::to_string()函数。这个函数可以将数字类型的变量转换为对应的字符串类型。下面是一个使用示例: 上面的代码将整型变量num转换为字符串类型,并输出到控制台

    2024年02月08日
    浏览(54)
  • matlab发送串口数据,并进行串口数据头的添加,我们来看下pwm解析后并通过串口输出的效果

    uintt16位的话会在上面前面加上00,16位的话一定是两个字节,一共16位的数据 如果是unint8的话就不会, 注意这里给的是13,但是现实的00 0D,这是大小端的问题,在matlanb里设置,我们就默认用这个模式吧,没关系的,小端,小段的小数据在前,所以是00 0D。 下图是串口输出P

    2024年02月20日
    浏览(41)
  • 用three.js做一个3D汉诺塔游戏(上)

    本文由孟智强同学原创,主要介绍了如何利用 three.js 开发 3D 应用,涵盖 3D 场景搭建、透视相机、几何体、材质、光源、3D 坐标计算、补间动画以及物体交互实现等知识点。 入门 three.js 也有一阵子了,我发现用它做 3D 挺有趣的,而且学习门槛也不算高。在这篇博文中,我想

    2024年03月27日
    浏览(64)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包