【动手学深度学习】15_汉诺塔问题

注: 本系列仅为个人学习笔记,学习内容为《算法小讲堂》(视频传送门),通俗易懂适合编程入门小白,需要具备python语言基础,本人小白,如内容有误感谢您的批评指正

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

在这里插入图片描述

首先考虑A座最下面的盘子移动到C座,如果能将上面的63个盘子从A座借助C座移到B座,再将63个盘子从B座借助A座移到C座,那任务即可完成,以此类推~直到仅有一个盘子的情形,则将一个盘子从一个座移动到另一个座,问题也就全部得到解决。而这就是典型的递归问题(可以理解为套娃,代码是从最大的娃往里一层一层套到最小的那个,输出是把最小到最大的一层层摆出来)

由以上描述我们可以知道递归算法的一些特征,为了求解规模为 N 的问题,应先设法将该问题分解成一些规模较小的问题,从这些较小问题的解可以方便地构造出大问题的解。同时,这些规模较小的问题也可以采用同样的方法分解成规模更小的问题,并能从这些规模更小的问题的解中构造出规模较小问题的解。特别地,当 N=1 时,可直接获得问题的解。

现在我们来找出解决问题的方法,定义一个递归函数hanno(N,A,B,C),该方法表示将N个盘子从A座借助B座移动到C座,盘子的初始个数为N。具体步骤为:

  1. 若 A 座上只有 1 个盘子,此时 N=1,则可直接将盘子从 A 座移动到 C 座上,问题得到解决。
  2. 若 A 座上有 1 个以上的盘子,即 N>1,此时需要再考虑 3 个步骤:
    1)先将 N-1 个盘子从 A 座借助 C 座移动到 B 座上。显然,这 N-1 个盘子不能作为一个整体移动,而是要按照要求来移动。此时,可递归调用函数 hanoi(N-1,A,C,B)。需要注意的是,这里借助 C 座将 N-1 个盘子从 A 座移动到 B 座,A 是源,B 是目标。
    2)将 A 座上剩下的第 N 个盘子移动到 C 座上。
    3)将 B 座上的 N-1 个盘子借助 A 座移动到 C 座上。此时,递归调用函数 hanoi(N-1,B,A,C)。需要注意的是,这里借助于 A 座将 N-1 个盘子从 B 座移动到 C 座,B 是源,C 是目标。
    完成了这 3 步,就可以实现预期的效果,在 C 座上按照正确的次序叠放好所有的盘子。

代码实现如下:

def hanno(N,A,B,C):
    if N==1:
        print('将盘子1从{}移到{}'.format(A,C))
    else:
        hanno(N-1,A,C,B)
        print('将盘子{}从{}移到{}'.format(N,A,C))
        hanno(N-1,B,A,C)
        
if __name__=='__main__':
    hanno(3,'A','B','C')

输出结果:

将盘子1从A移到C
将盘子2从A移到B
将盘子1从C移到B
将盘子3从A移到C
将盘子1从B移到A
将盘子2从B移到C
将盘子1从A移到C

注:递归这里不能简单的认为A,C一直等于最开始传入的实参,本篇参考汉诺塔(图文结合),超好理解,可自行阅读原文

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/532980.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

2024谷歌Google广告推广投放怎么做?如何收费?

当今全球市场,谷歌作为全球最大的搜索引擎,其广告服务——Google Ads,已成为企业触达全球消费者、提升品牌知名度、驱动业务增长的首选渠道之一。尤其是在2024年,随着数字营销环境的持续演进,精准、高效地运用Google A…

MySQL-创建和管理表:基础知识、创建和管理数据库、创建表、修改表、重命名表、删除表、清空表、拓展

创建和管理表 1. 基础知识1.1 一条数据存储的过程1.2 标识符命名规则1.3 MySQL中的数据类型 2. 创建和管理数据库2.1 创建数据库2.2 使用数据库2.3 修改数据库2.4 删除数据库 3. 创建表3.1 创建方式13.2 创建方式23.3 查看数据表结构 4. 修改表4.1 追加一个列4.2 修改一个列4.3…

Prometheus+Grafana监控K8S集群(基于K8S环境部署)

目录 一.环境信息二.部署提前工作三.部署Prometheus监控系统四.部署Node_exporter组件五.部署Kube_state_metrics组件六.部署Grafana可视化平台七.Grafana接入Prometheus数据八.Grafana添加监控模板九.拓展 一.环境信息 1.服务器及k8s版本信息 IP地址主机名称角色版本192.168…

SAM功能改进VRP-SAM论文解读VRP-SAM: SAM with Visual Reference Prompt

现已总结SAM多方面相关的论文解读,具体请参考该专栏的置顶目录篇 一、总结 1. 简介 发表时间:2024年3月30日 论文: 2402.17726.pdf (arxiv.org)https://arxiv.org/pdf/2402.17726.pdf代码: syp2ysy/VRP-SAM (github.com)htt…

JVM面试整理--对象的创建和堆

文章目录 对象的创建过程是怎样的?对象在内存中的结构是怎样的(专业的叫法:对象的内存布局)对象在内存分配时使用的哪种方式(有的地方也称为:分配算法)知道什么是“指针碰撞”吗?知道什么是“空…

电商技术揭秘十八:电商平台的云计算与大数据应用小结

电商技术揭秘相关系列文章 电商技术揭秘一:电商架构设计与核心技术 电商技术揭秘二:电商平台推荐系统的实现与优化 电商技术揭秘三:电商平台的支付与结算系统 电商技术揭秘四:电商平台的物流管理系统 电商技术揭秘五&#xf…

【产品】ANET智能通信管理机 物联网网关 电力监控/能耗监测/能源管理系统

产品概述 本系列智能通信管理机是一款采用嵌入式硬件计算机平台,具有多个下行通信接口及一个或者多个上行网络接口,用于将一个目标区域内所有的智能监控/保护装置的通信数据整理汇总后,实时上传主站系统,完成遥信、遥测等能源数据…

遥感图像处理:从畸变消除到专题信息提取

​ ​ ​在遥感技术的应用中,图像处理是不可或缺的关键步骤。从消除各种辐射畸变和几何畸变,到利用增强技术突出景物的光谱和空间特征,再到进一步理解、分析和判别处理后的图像,这一过程为我们呈现了一幅幅更为真实、清晰的…

Elasticsearch:从 ES|QL 到 PHP 对象

作者:来自 Elastic Enrico Zimuel 从 elasticsearch-php v8.13.0 开始,你可以执行 ES|QL 查询并将结果映射到 stdClass 或自定义类的 PHP 对象。 ES|QL ES|QL 是 Elasticsearch 8.11.0 中引入的一种新的 Elasticsearch 查询语言。 目前,它在…

基于GRU实现评论文本情感分析

一、问题建模 在线评论的细粒度情感分析对于深刻理解商家和用户、挖掘用户情感等方面有至关重要的价值,并且在互联网行业有极其广泛的应用,主要用于个性化推荐、智能搜索、产品反馈、业务安全等。此博文,共包含6大类20个细粒度要素的情感倾…

SpringBoot中的Redis的简单使用

在Spring Boot项目中使用Redis作为缓存、会话存储或分布式锁等组件,可以简化开发流程并充分利用Redis的高性能特性。以下是使用Spring Boot整合Redis的详细步骤: 1. 环境准备 确保开发环境中已安装: Java:用于编写和运行Spring…

RISC-V特权架构 - 中断注入

中断注入 1 中断注入的作用2 mip寄存器3 中断注入后的处理过程 本文属于《 RISC-V指令集基础系列教程》之一,欢迎查看其它文章。 1 中断注入的作用 中断注入,就是在M模式下,手动向S模式去产生一个中断。 比如:向mip寄存器的bit5…

✌2024/4/6—力扣—最长公共前缀✌

代码实现&#xff1a; char *longestCommonPrefix(char **strs, int strsSize) {if (strsSize 0) {return "";}for (int i 0; i < strlen(strs[0]); i) { // 列for (int j 1; j < strsSize; j) { // 行if (strs[0][i] ! strs[j][i]) { // 如果比较字符串的第…

三、Mat、Bitmap和Image数据类型之间的转换(OpenCvSharp)

在OpenCV中可以通过ImRead方法读取照片&#xff0c;通过ImShow方法显示照片&#xff1b;但是无法在PictureBox控件中显示 PictureBox控件只能展示Bitmap和Image数据类型图片 为此查阅了网上很多篇博文&#xff0c;将三种数据类型之间的转换进行了归纳整理&#xff0c;感谢网上…

JavaScript进阶6之函数式编程与ES6ESNext规范

函数式编程 柯里化currycurrycompose示例&#xff1a;简化版展开写&#xff1a; debug示例一&#xff1a;示例二&#xff1a; 模板字符串css in js方案 箭头函数问题 生成器 generator应用场景 反射 Reflect 柯里化curry compose是curry的应用 在 lodash/fp underscore ramba …

RTSP/Onvif视频安防监控平台EasyNVR调用接口返回匿名用户名和密码的原因排查

视频安防监控平台EasyNVR可支持设备通过RTSP/Onvif协议接入&#xff0c;并能对接入的视频流进行处理与多端分发&#xff0c;包括RTSP、RTMP、HTTP-FLV、WS-FLV、HLS、WebRTC等多种格式。平台拓展性强、支持二次开发与集成&#xff0c;可应用在景区、校园、水利、社区、工地等场…

怎么快速围绕“人、货、场”做零售数据分析?

做零售数据分析多了&#xff0c;不难发现零售数据分析的关键就是“人、货、场”&#xff0c;那么怎么又快又灵活地分析这三个关键点&#xff1f;不妨参考下奥威BI零售数据分析方案。 奥威BI零售数据分析方案是一套吸取大量项目经验&#xff0c;结合零售企业数据分析共性需求打…

【教学类-50-06】20240410“数一数”4类星号图片制作PDF学具

作品展示&#xff1a; 背景需求&#xff1a; 前文遍历四个文件夹&#xff0c;分别将每个文件夹内的10个图片的左上角加入星号&#xff0c;显示难度系数 【教学类-50-05】20240410“数一数”4类图片添加“难度星号”-CSDN博客文章浏览阅读55次&#xff0c;点赞2次&#xff0c;…

xss跨站脚本攻击笔记

1 XSS跨站脚本攻击 1.1 xss跨站脚本攻击介绍 跨站脚本攻击英文全称为(Cross site Script)缩写为CSS&#xff0c;但是为了和层叠样式表(CascadingStyle Sheet)CSS区分开来&#xff0c;所以在安全领域跨站脚本攻击叫做XSS 1.2 xss跨战脚本攻击分类 第一种类型:反射型XSS 反射…

Prime (2021): 2

前言 这个靶机有亿点难,收获很多。打靶的时候&#xff0c;前面很顺&#xff0c;到创建ssh公钥之后就一点不会了。 1 01 arp扫描&#xff0c;发现有一个130&#xff0c;再查看端口 有22&#xff0c;80&#xff0c;129&#xff0c;445&#xff0c;10123 dirb扫描目录 这…