最新要闻
- 国内已超越GPS 北斗卫星今年再发三颗星:下一代已在路上
- 世界观点:称根据身体来划分性别比较好 女星桥本爱被LGBT攻击
- 【独家】女生月薪两万辞职考研八次失败:次次铩羽而归
- 环球今热点:SSD比机械硬盘更容易坏?实测来了:跟想象中不一样
- 全球观天下!2月轿车销量排名:两“逸”同病相怜、秦汉一马平川
- 通讯!姚劲波代表:高学历干家政可能会越发普遍
- 《庆余年2》冲上热搜榜:网曝郭麒麟演的角色范思辙换人了
- 9名初中生花18元点18串里脊庆生 网友看哭:回不去的年华
- 今日报丨金钱豹回拜游客 动物园回应:没人教、第一次见
- 世界今日报丨隅田川进口胶囊咖啡液8杯到手10.9元:更鲜更好喝
- 全球最资讯丨A卡有能力跟RTX 4090正面刚 AMD:不做是因为太贵、功耗高
- 微头条丨深山红烛 照亮希望
- 每日快报!安全性不行 Win7系统真的别用了 又一个游戏《堡垒之夜》放弃支持
- 每日快播:童年回来了!《灌篮高手》发布流川枫角色海报
- 今日热闻!光速破发?iPhone 14黄色版还未开售便降价600元
- 华硕发布ROG Strix Impact III鼠标:双手通用、可更换微动插槽
手机
iphone11大小尺寸是多少?苹果iPhone11和iPhone13的区别是什么?
警方通报辅警执法直播中被撞飞:犯罪嫌疑人已投案
- iphone11大小尺寸是多少?苹果iPhone11和iPhone13的区别是什么?
- 警方通报辅警执法直播中被撞飞:犯罪嫌疑人已投案
- 男子被关545天申国赔:获赔18万多 驳回精神抚慰金
- 3天内26名本土感染者,辽宁确诊人数已超安徽
- 广西柳州一男子因纠纷杀害三人后自首
- 洱海坠机4名机组人员被批准为烈士 数千干部群众悼念
家电
全球消息!汉诺塔问题——分而治之(引入递归,解决重复子问题)
汉诺塔问题的引入:
相传在古印度圣庙中,有一种被称为汉诺塔(Hanoi)的游戏。该游戏是在一块铜板装置上,有三根杆(编号A、B、C),在A杆自下而上、由大到小按顺序放置64个金盘(如图1)。游戏的目标:把A杆上的金盘全部移到C杆上,并仍保持原有顺序叠好。操作规则:每次只能移动一个盘子,并且在移动过程中三根杆上都始终保持大盘在下,小盘在上,操作过程中盘子可以置于A、B、C任一杆上。(ps:来自于百度)
1.求解思路:
假设只有一层塔,那么就只需要将a移动到c即可;
假设有二层塔,需要先将前一个小圆盘从a移动到b,再将最后大圆盘1个移动到c,再将b中的小圆盘从b移动到c;
(资料图片仅供参考)
假设有三层塔,需要先将前两个小圆盘从a移动到b,再将最后大圆盘1个移动到c,再将b中的小圆盘从b移动到c;
……
假设有n-1层塔,需要先将前n-2个小圆盘从a移动到b,再将最后大圆盘1个移动到c,再将b中的小圆盘从b移动到c;
假设有n层塔,需要先将前n-1个小圆盘从a移动到b,再将最后大圆盘1个移动到c,再将b中的小圆盘从b移动到c;
由上述观察可知:求解第二层塔与第n层塔的解题步骤是一致的,求解第n层塔需要求解第n-1层塔;求解第n-1层塔需要求解第n-2层塔………求解第三层塔需要求解第二层2塔,可以将其看成一个等比数列,每次的都需要比上一次多进行一倍操作,由等比数列求和公式得,总共进行了2^n-1次移动,所以时间复杂度为O(2^n)!
2.如何求解:
从上述不难看出,每次求解的步骤都一样,那有没有有什么方法解决重复的问题呢?
————递归会给你答案
什么是递归:递归算法(英语:recursion algorithm)在计算机科学中是指一种通过重复将问题分解为同类的子问题而解决问题的方法。递归式方法可以被用于解决很多的计算机科学问题,因此它是计算机科学中十分重要的一个概念。绝大多数编程语言支持函数的自调用,在这些语言中函数可以通过调用自身来进行递归。计算理论可以证明递归的作用可以完全取代循环,因此在很多函数编程语言(如Scheme)中习惯用递归来实现循环。(ps:来自于百度)
递归实际上就是一种自调用函数,自己调用自己,从而达到解决重复步骤的问题;
如果汉诺塔只有一层的时候我们就需要把a移动到c
如果2层以上呢:由于递归函数再求解过程中不会改变步骤,每次都是固定从a移动到c,所以我们要将每根柱子做一个标记,方便理解交换时所带来的里面元素的改变过程;设:
第一个柱子为交换柱子:需要移动的元素都放在第一个位置
第二个柱子为中间柱子:不需要移动元素放在第二个柱子里
第三个柱子为目标柱:将要移动的元素放到第三个柱子
现在递归循环是从第二层到第n层开始的:
1.从上一层结束开始c元素在目标柱中,所以需要交换到目标柱当中(c元素)
2.将a移动到b,所以a元素在交换柱,b元素在目标柱
3.然后将b移动到c,b为交换柱,c为目标柱,a在中间柱子
3.代码实现
void Hannouta(int n, char pos1, char pos2, char pos3){ if (n == 1) { move(n, pos1, pos3);//move为交换函数 } else { Hannouta(n-1, pos1, pos3, pos2); move(n, pos1, pos3); printf("盘子%d: 从 %c柱 移动到 %c柱\n", n, pos1, pos3); Hannouta(n-1, pos2, pos1, pos3); }}
4.时间复杂度分析
由上述分析可知道——时间复杂度为O(2^n);
关键词:
每日速递:flink入门-流处理
全球消息!汉诺塔问题——分而治之(引入递归,解决重复子问题)
世界球精选!Java基础入门-数组练习
国内已超越GPS 北斗卫星今年再发三颗星:下一代已在路上
世界观点:称根据身体来划分性别比较好 女星桥本爱被LGBT攻击
【独家】女生月薪两万辞职考研八次失败:次次铩羽而归
全球新资讯:第128篇:浏览器存储(cookie、webStorage、 IndexedDB)
世界简讯:关于使用python脚本将同级的其他目录下的所有文件根据年份移动到当脚本位置的年份目录
环球今热点:SSD比机械硬盘更容易坏?实测来了:跟想象中不一样
全球观天下!2月轿车销量排名:两“逸”同病相怜、秦汉一马平川
通讯!姚劲波代表:高学历干家政可能会越发普遍
《庆余年2》冲上热搜榜:网曝郭麒麟演的角色范思辙换人了
资讯:shiro-550反序列化漏洞分析
资讯:64.异常
世界热文:[新媒体运营]新媒体运营概述
9名初中生花18元点18串里脊庆生 网友看哭:回不去的年华
今日报丨金钱豹回拜游客 动物园回应:没人教、第一次见
世界今日报丨隅田川进口胶囊咖啡液8杯到手10.9元:更鲜更好喝
有赞一面:还有任务没执行,线程池被关闭怎么办?
全球快看点丨注解与反射
java基础二-面向对象的三大特性
全球最资讯丨A卡有能力跟RTX 4090正面刚 AMD:不做是因为太贵、功耗高
微头条丨深山红烛 照亮希望
环球新消息丨Redis 深度学习
环球快资讯:前端设计模式——策略模式
新消息丨MySQL学习笔记-SQL实践1
每日快报!安全性不行 Win7系统真的别用了 又一个游戏《堡垒之夜》放弃支持
每日快播:童年回来了!《灌篮高手》发布流川枫角色海报
每日报道:使用web client对 vcenter 进行补丁升级
有监督学习——梯度下降
全球百事通!聪明的燕姿
当前视点!Oracle数据库中没有scott账户的方法
今日热闻!光速破发?iPhone 14黄色版还未开售便降价600元
华硕发布ROG Strix Impact III鼠标:双手通用、可更换微动插槽
真香!重庆购买HUAWEI问界M7直补3万:起售仅25.98万
当前简讯:滴滴快车预付车费什么时候退款_滴滴快车预付车费什么意思
世界通讯!网络安全(中职组)-B模块:Web安全应用-2
今日播报!客服回应疯狂小杨哥带货翻车:有巡查、违规会处罚
怕了吗?长城公布“1000万悬赏计划”:严厉打击网络水军
【世界新要闻】四位计数器testbench的设计
世界滚动:chatgpt 集成飞书实践指南
自以为是 与 思考
天天通讯!伊朗外长:伊沙恢复外交关系将为两国和地区发展注入巨大动能
世界快讯:日系车掀起买一送一热潮:买皓影插混送飞度、买日产楼兰送轩逸
天天热资讯!50万以内最舒适二排 理想L7正式交付:31.98万起售
环球新资讯:10年分红1000多亿!董明珠鼓励员工“砸锅卖铁”买格力股票
剪刀石头布的算法
资讯推荐:全球最强!传音发布260W有线、110无线快充:8分钟充满
世界观热点:美国科学家改变人类科技、终极能源即将实现?真相来了!
世界快讯:《原子之心》更新:添加FOV设置、删除种族主义动画
Shell命令-常用操作2
【质因数分解算法详解】C/Java/Go/Python/JS/Dart/Swift/Rust等不同语言实现
今亮点!霸道女总裁加盟《碟中谍8》
天天播报:00后男生每天下班后卖烤肠解压 50元投资日赚200元:厌恶刷视频、打游戏
【时快讯】网络安全(中职组)-B模块:Web安全渗透测试
环球新消息丨K8S 性能优化-K8S Node 参数调优
环球微速讯:比进口价格便宜!海南三亚榴莲今年6月将大规模上市
当废物挺好?委员称年轻人想躺平更多是调侃 奋斗的是大多数
天天亮点!中国足彩网竞彩11日推荐:曼城取胜无悬念
焦点短讯!使用SSM+Shiro+Layui框架,基于RBAC3模型开发的权限管理系统
snort入侵检测基础概述
当前播报:amusements
环球热议:6月上映!《变形金刚7》角色海报发布:擎天柱、猩猩队长亮相
【速看料】降价潮席卷全国 车企尽数参战是为何?乘联会解答:国六B要来了
观热点:01-C语言概述
环球今热点:真正油电同价!比亚迪投放“深水炸弹”:13.4万买宋Pro DM-i超级混动
环球通讯!立春来首场寒潮横扫我国大部:多地将遭遇滑梯式降温 最高降20℃
【新要闻】活久见!女生家中发现神奇圆柱形手机:登QQ、手电筒、拍照 功能多到炸
读Java性能权威指南(第2版)笔记13_堆内存下
最便宜竖折叠继任者!摩托罗拉Razr 2023真机图出炉:首次拼色后壳
当前快报:汽车价格战新进展:南北大众同日入局 丰田买一辆送一辆
世界速递!day05-功能实现04
Vue————Vue v2.7.14 入口文件【二】
【时快讯】《满江红》中国影史票房榜第6:力压《唐人街探案3》 票房突破45.23亿
环球即时:2023开门红!长四丙成功发射“一箭双星”
环球消息!第一批PCIe 5.0 SSD都是残血!14GB/s满血版还早呢
世界快资讯丨有了ChatGPT 动动嘴就能使唤Excel:我的童年梦想实现了
每日热门:8岁男孩单手打破汉诺塔世界纪录:4.305秒搞定4层
当前头条:海绵宝宝卡通图片线条图_海绵宝宝卡通图片
天生要完美电视剧28集完整版_天生要完美电视剧
对C++做爬虫的代码进行简单分析
世界热推荐:2.HelloSpring
孙海洋夫妇餐饮公司被列经营异常:本人回应
今日报丨香港男子深圳上班每天通勤4小时:月薪3万 每天通勤费用80元
【全球独家】63.C++类型转换
世界今亮点!python可变长参数
当前观察:大获成功!《最后生还者》成史上收视率最高的游戏改编剧
爆款椰子鞋停售后:阿迪在中国凉凉了
1.3kg下颜值、性能、屏幕全给你!华硕灵耀14 2023评测:续航惊人
观热点:长城汽车发布Hi4全新新能源技术:4驱享受 2驱能耗
全球关注:杠上比亚迪秦PLUS DM-i 新款日产轩逸上市:9.98万起
8GB、16GB显存的性能差多少?实测多达172%!
明解数据库------数据库存储演变史
AMD最强核显跑分上来了!但是还打不过GTX 1650 Ti
全球最新:买丰田bZ4X电动车 送一辆威驰轿车?4S店回应:活动属实
RTX 30公版显卡突然集体消失!刚刚降价40%
微头条丨公司规定不接董事长电话1次罚10000元 员工:试岗1天就走了
【全球快播报】校友承诺捐赠1100万元却不兑现被告 学校:他具备履约能力
紧跟微信步伐:支付宝掌纹支付设备外观专利获授权
【天天快播报】搅局中端市场!一加Ace2V评测:将16G满血内存进行到底