1、递归算法解决汉诺塔问题(算法基础)_汉诺塔的递归基础是什么-程序员宅基地

技术标签: 算法  python  数据结构和算法基础  

1、递归算法的特点

1、调用本身
2、设置一个结束条件

需要先将问题简单化,找到一个可以不断递推下去的规律

2、问题背景:

相传在古印度圣庙中,有一种被称为汉诺塔(Hanoi)的游戏。该游戏是在一块铜板装置上,有三根杆(编号A、B、C),在A杆自下而上、由大到小按顺序放置64个金盘(如图1)。
游戏的目标:把A杆上的金盘全部移到C杆上,并仍保持原有顺序叠好。
操作规则:每次只能移动一个盘子,并且在移动过程中三根杆上都始终保持大盘在下,小盘在上,操作过程中盘子可以置于A、B、C任一杆上。

3、问题:如何模拟这个移动的过程

在这里插入图片描述

4、解题核心思路:

假设金盘有n个,那么我们可以看成两部分:最底下的1个和上面的n-1个金盘。
问题就被简化成:移动两部分。

移动两部分的步骤可以拆解为以下三步:
1、把n-1个盘子从A经过C移动到B;(多个盘子想移动到B柱,必须经过C柱才行)
2、把第n个盘子从A移动到C;
3、把n-1个盘子从B经过A移动到C;

5、推演

假设n=3,我们可以根据下图,推演一遍,是否符合这个规律
在这里插入图片描述

6、代码:

def hanoi(n, a, b, c):   # 参数n代表有n个盘子,a, b, c分别代表3个柱子
    if n > 0:
        hanoi(n-1, a, c, b)
        print('moving from %s to %s'%(a, c))
        hanoi(n-1, b, a, c)

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

7、输出结果:

在这里插入图片描述

版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/Jacky_kplin/article/details/120877382

智能推荐

查看crontab的日志记录定位定时任务问题-程序员宅基地

文章浏览阅读186次。1、linux看 /var/log/cron这个文件就可以,可以用tail -f /var/log/cron观察2、unix在 /var/spool/cron/tmp文件中,有croutXXX001864的tmp文件,tail 这些文件就可以看到正在执行的任务了。3、mail任务在 /var/spool/mail/root 文件中,有crontab执行日志的记录,用tail -...

appium python 抓包_利用appium自动控制移动设备并抓取数据-程序员宅基地

文章浏览阅读520次。利用appium自动控制移动设备并提取数据学习目标了解 appium-python-client模块定位元素以及提取其文本内容的方法了解 appium-python-client模块控制滑动动作的方法以控制抖音app滑动并获取抖音短视频发布者昵称和点赞数等信息为例2.1 安装appium-python-client模块并启动已安装好的环境2.1.1 安装appium-python-client模块..._appium自动化,抓到的包是什么样的

vue项目axios解决前后端跨域问题,前端配置方法(已测有用)-程序员宅基地

文章浏览阅读519次。已经在网上找了很多种方法,最后还是这种方法对我有用 1. 更改main.js文件2.更改config/index.js3.更改config/dev.env.js总共更改的文件有三个:1. 更改main.js文件添加下面代码//设置请求的根路径,地址为后端地址axios.defaults.baseURL = 'http://localhost:8088'2.更改config/index.js添加下面代码proxyTable: { '/apis': {

【机器学习】网络表征学习、网络嵌入必读论文_daokun zhang-程序员宅基地

文章浏览阅读7.1k次。以下内容转载于:https://blog.csdn.net/weixin_40400177/article/details/103329924NRL: network representation learning. NE: network embedding.ContentSurvey PapersModelsBacis ModelsAttributed NetworkDyn..._daokun zhang

算法设计技巧-贪婪算法、分治算法、动态规划等_贪婪调度算法-程序员宅基地

文章浏览阅读908次。1.贪婪算法(greedyalgorithm)贪婪算法的核心思想是将问题分阶段进行,在每个阶段选择当前最优的,而不考虑对之后的影响。这意味着选择是局部最优的,我们希望贪婪算法结束时我们希望局部最优等于全局最优,否则得到的只是次最优解。一个典型的问题是货币找零问题,假设现在有面值10元,5元,1元的钞票,要选出最少的钞票组成23元,那么方法是,从面值最大的开始重复选取,直到超过所要组成的面值。..._贪婪调度算法

Redis的并发问题_100个人同时查redis-程序员宅基地

文章浏览阅读631次。数据库有就保存到Redis中,返回数据。Redis没有再查询数据库。Redis存在就直接返回。先从Redis查询数据。为数据库挡住大量并发。_100个人同时查redis

随便推点

P4 Runtime和p4 info-程序员宅基地

文章浏览阅读964次。p4runtimeP4 Runtime是一套基于Protobuf以及gRPC框架上的协议,通过P4runtime,SDN控制器可以控制能够支援p4的设备。p4runtime当前由p4 API workgroup指定,主要来自于barefoot公司。barefoot公司,其还设计了第一款原生支持p4的芯片——tofino,以及基于tofino的交换机——wedge 100bf-65x。控制器..._p4 编译架构 runtime tofino

.NET PDF转图片_vb.net pdf文件转图片-程序员宅基地

文章浏览阅读4.9k次。VB.NET下的PDF转图片首先需要添加引用O2S.Components.PDFRender4NET.dllImports O2S.Components.PDFRender4NETSub ConvertPDF2Image(ByVal pdfInputPath As String, ByVal imageOutputPath As String, ByVal imageName As Str_vb.net pdf文件转图片

爬取新浪新闻(嵌套爬取,爬取子链接,然后每个子链接的详情页里面内容)_爬取新闻时子链接格式不一样-程序员宅基地

文章浏览阅读981次。1.首先命令行输入: scrapy startproject newsSpider2.在spider文件夹下,建立Spider.py文件,具体如下:import osimport scrapyfrom ..items import NewsspiderItemclass newsSpider(scrapy.Spider): name = 'news' allowed_..._爬取新闻时子链接格式不一样

ca盘显示无证书_CA根证书无法识别-程序员宅基地

文章浏览阅读2.2k次。近些年来,越来越多的企业和组织开始建立他们自己的企业 CA,目的是为了增强日益增长、数量众多的基于网络的商业过程安全性。一个企业要建立自己的企业 CA, 必须自签发一张 CA 根证书。根证书用来为员工、外部网用户、机器及设备颁发数字证书。这类证书被用来进行数字签名和通讯加密,也用来控制网络资源的非法接入。但是,这种自签发的根证书无法被主流操作系统(如微软Windows)、浏览器(如微软 IE、Mo..._certum trusted network ca 此ca根证书不在受信任的根证书颁发机构存储区

java 集成开发工具_最好的Java开发人员测试和集成工具-程序员宅基地

文章浏览阅读558次。java 集成开发工具 通过从您的应用程序学习企业APM产品,发现更快,更有效的性能监控。 参加AppDynamics APM导览! 无论您是刚刚起步还是已经从事了一段时间,使用正确的工具进行编程都可以对项目的成功产生巨大的影响。 适当的工具使您可以编写更好的代码并快速识别错误。 所有这些使您的代码变得更好。 期。 如果您选择的编程语言是Java,那么从编码和测试到服务器集成和文档编制..._java软件集成

爬取虎扑博客内容的Python代码_虎扑爬虫代码-程序员宅基地

文章浏览阅读440次。爬取虎扑博客内容的Python代码爬取目标使用的工具具体步骤1.导入库并连接数据库2.获取前10页的URL3.获取网页4.爬取内容并导入到MongoDB数据库总代码运行成功截图爬取目标主要爬取的为虎扑网站博客前十页的标题、作者、发布时间、浏览量、回复数等信息,结果如下图所示:使用的工具数据库: MongoDB数据库语言: python解析方式: BeautifulSoup具体步骤..._虎扑爬虫代码