位置: IT常识 - 正文

汉诺塔问题分治求解(汉诺塔问题动画演示)

编辑:rootadmin
汉诺塔问题 在经典汉诺塔问题中,有 3 根柱子及 n 个不同大小的穿孔圆盘,盘子可以滑入任意一根柱子。一开始,所有盘子自上而下按升序依次套在第一根柱子上(即每一个盘子只能放在更大的盘子上面)。移动圆盘时受到以下限制: (1) 每次只能移动一个盘子; (2) 盘子只能从柱子顶端滑出移到下一根柱子; ( ... 汉诺塔问题

推荐整理分享汉诺塔问题分治求解(汉诺塔问题动画演示),希望有所帮助,仅作参考,欢迎阅读内容。

文章相关热门搜索词:汉诺塔问题解析,汉诺塔问题解析,汉诺塔问题的最佳解决方案,汉诺塔问题总结,汉诺塔问题总结,汉诺塔问题的解决方法,汉诺塔问题分析,汉诺塔问题分析,内容如对您有帮助,希望把文章链接给更多的朋友!

在经典汉诺塔问题中,有 3 根柱子及 n 个不同大小的穿孔圆盘,盘子可以滑入任意一根柱子。一开始,所有盘子自上而下按升序依次套在第一根柱子上(即每一个盘子只能放在更大的盘子上面)。移动圆盘时受到以下限制:(1) 每次只能移动一个盘子;(2) 盘子只能从柱子顶端滑出移到下一根柱子;(3) 盘子只能叠在比它大的盘子上。

请编写程序,用栈将所有盘子从第一根柱子移到最后一根柱子。

你需要原地修改栈。

输入:A = [2, 1, 0], B = [], C = []输出:C = [2, 1, 0]

解题思路:递归与分治这是一道递归方法的经典题目,乍一想还挺难理清头绪的,我们不妨先从简单的入手。

假设 n = 1,只有一个盘子,很简单,直接把它从 A 中拿出来,移到 C 上;

如果 n = 2 呢?这时候我们就要借助 B 了,因为小盘子必须时刻都在大盘子上面,共需要 4 步。

汉诺塔问题分治求解(汉诺塔问题动画演示)

如果 n > 2 呢?思路和上面是一样的,我们把 n 个盘子也看成两个部分,一部分有 1 个盘子,另一部分有 n - 1 个盘子。

观察上图,你可能会问:“那 n - 1 个盘子是怎么从 A 移到 C 的呢?”

当你在思考这个问题的时候,就将最初的 n 个盘子从 A 移到 C 的问题,转化成了将 n - 1 个盘子从 A 移到 C 的问题, 依次类推,直至转化成 1 个盘子的问题时,问题也就解决了。这就是分治的思想。

而实现分治思想的常用方法就是递归。不难发现,如果原问题可以分解成若干个与原问题结构相同但规模较小的子问题时,往往可以用递归的方法解决。具体解决办法如下:

n = 1 时,直接把盘子从 A 移到 C;

n > 1 时,

先把上面 n - 1 个盘子从 A 移到 B(子问题,递归);

再将最大的盘子从 A 移到 C;

再将 B 上 n - 1 个盘子从 B 移到 C(子问题,递归)。

Java代码class Solution { public void hanota(List<Integer> A, List<Integer> B, List<Integer> C) { /* 1.先将A柱子中的n-1个的圆盘移动到B柱子 2.再将A柱子中最后1个圆盘移动到C柱子 3.最后将B柱子的n-1个圆盘移动到C柱子 */ int n = A.size(); move(n, A, B, C); } /* 其中A为原始柱子;B为辅助柱子;C为目标柱子(与位置有关,那么list都有可能) */ private void move(int n, List<Integer> A, List<Integer> B, List<Integer> C) { // A中只剩下1个圆盘了,直接移动到C柱子后结束 if (n == 1) { C.add(A.remove(A.size() - 1));// 将A柱子中最后1个圆盘移动到C柱子 return; } // 1.先将的A柱子中的n-1个的圆盘移动到B柱子(此时B为目标柱子,A为原始柱子) move(n - 1, A, C, B); // 2.再将的A柱子中最后1个圆盘移动到C柱子 C.add(A.remove(A.size() - 1)); // 3.最后将B柱子的n-1个圆盘移动到C柱子(此时C为目标柱子,B为原始柱子) move(n - 1, B, A, C); }}C++代码class Solution {public: void hanota(vector<int>& A, vector<int>& B, vector<int>& C) { int n = A.size(); move(n, A, B, C); } void move(int n, vector<int>& A, vector<int>& B, vector<int>& C){ if (n == 1){ C.push_back(A.back()); A.pop_back(); return; } move(n-1, A, C, B); // 将A上面n-1个通过C移到B C.push_back(A.back()); // 将A最后一个移到C A.pop_back(); // 这时,A空了 move(n-1, B, A, C); // 将B上面n-1个通过空的A移到C }};复杂度分析时间复杂度:O(2^n-1)。一共需要移动的次数。空间复杂度:O(1)。
本文链接地址:https://www.jiuchutong.com/zhishi/311789.html 转载请保留说明!

上一篇:dedecms织梦Tag标签伪静态设置方法(织梦网站特有标识)

下一篇:c语言中如何防止数组下标越界(c语言中如何防止函数重名)

  • vivo来电闪光灯怎么关(vivo手机来电闪光灯在哪里设置)

    vivo来电闪光灯怎么关(vivo手机来电闪光灯在哪里设置)

  • 快手如何自动识别字幕(快手怎么设置自动识别字幕)

    快手如何自动识别字幕(快手怎么设置自动识别字幕)

  • 计算机中ram因断电而丢失的信息(ram储存器中的信息断电后不会丢失)

    计算机中ram因断电而丢失的信息(ram储存器中的信息断电后不会丢失)

  • 9900k支持多少内存频率(9900k支持多大内存频率)

    9900k支持多少内存频率(9900k支持多大内存频率)

  • 举报微信好友他知道吗(举报微信好友有什么后果)

    举报微信好友他知道吗(举报微信好友有什么后果)

  • 美团怎么批量复制商品(美团怎么批量复制同行商品)

    美团怎么批量复制商品(美团怎么批量复制同行商品)

  • ufs3.0读写速度(ufs2.1读写速度)

    ufs3.0读写速度(ufs2.1读写速度)

  • 安全模式也是黑屏鼠标(安全模式进去黑屏什么问题)

    安全模式也是黑屏鼠标(安全模式进去黑屏什么问题)

  • bilibili青少年模式提示怎么关闭(bilibili青少年模式强制关闭)

    bilibili青少年模式提示怎么关闭(bilibili青少年模式强制关闭)

  • 手机淘宝和电脑淘宝有什么区别(手机淘宝和电脑淘宝一样吗)

    手机淘宝和电脑淘宝有什么区别(手机淘宝和电脑淘宝一样吗)

  • 格力空调制热外机声音大怎么回事(格力空调制热外机漏水是正常现象吗)

    格力空调制热外机声音大怎么回事(格力空调制热外机漏水是正常现象吗)

  • 为什么快手看不到别人的粉丝(为什么快手看不到自己的评论)

    为什么快手看不到别人的粉丝(为什么快手看不到自己的评论)

  • qq停止运行是怎么回事(qq停止运行是什么意思)

    qq停止运行是怎么回事(qq停止运行是什么意思)

  • 苹果7手机有几种型号内存(苹果7手机有几个喇叭)

    苹果7手机有几种型号内存(苹果7手机有几个喇叭)

  • 视频怎么加长腿特效(视频怎么加长腿瘦身)

    视频怎么加长腿特效(视频怎么加长腿瘦身)

  • xr怎么开启无线充电(xr怎么开启无线充电设置)

    xr怎么开启无线充电(xr怎么开启无线充电设置)

  • 台式电脑电源设置(台式电脑电源设置平衡还是高性能)

    台式电脑电源设置(台式电脑电源设置平衡还是高性能)

  • 苹果软件自动扣费怎么关闭(苹果软件自动扣款可以退款吗)

    苹果软件自动扣费怎么关闭(苹果软件自动扣款可以退款吗)

  • 小米9pro是ufs3.0吗(小米9pro是几g手机)

    小米9pro是ufs3.0吗(小米9pro是几g手机)

  • 华为p30系统是安卓吗(华为p30的系统)

    华为p30系统是安卓吗(华为p30的系统)

  • 一个邮箱可以注册几个苹果id(一个邮箱可以注册几个任天堂账号)

    一个邮箱可以注册几个苹果id(一个邮箱可以注册几个任天堂账号)

  • 苹果8p能升5g吗(iphone 8p可以升级256内存吗)

    苹果8p能升5g吗(iphone 8p可以升级256内存吗)

  • 红米k20pro摄像头怎么弹出来(红米k20pro摄像头手动校正)

    红米k20pro摄像头怎么弹出来(红米k20pro摄像头手动校正)

  • 百香果的副作用及禁忌(图文)(百香果的副作用及禁忌是哪些)

    百香果的副作用及禁忌(图文)(百香果的副作用及禁忌是哪些)

  • 使用Axios前后端交互(超详细)建议点赞收藏(前端axios请求怎么中断)

    使用Axios前后端交互(超详细)建议点赞收藏(前端axios请求怎么中断)

  • 增值税发票四舍五入
  • 企业收到补贴需要开票吗
  • 个人所得税哪里报税
  • 企业清算的种类
  • 在租赁的土地上建房产权归谁
  • 购买原材料产生的运输费计入什么科目
  • 汽车租赁油费怎么算
  • 抵缴以前年度多缴所得税如何做会计分录?
  • 制造行业运输费包括哪些
  • 增值税和消费税申报对比不符怎么处理
  • 投资利息收入要交所得税吗
  • 税盘忘记清盘了怎么办
  • 流转税税额
  • 固定资产的摊销额计入什么科目
  • 应付票据属于什么类账户
  • 农产品进项税抵扣计算例题
  • 公司周年庆典费用计入什么科目
  • 微信语音音乐怎么调
  • 如何处理企业所得税纠纷
  • 公司股权转让怎么操作
  • ptssvc.exe - ptssvc是什么进程 有什么用
  • windows11怎么设置锁屏密码
  • 环形链表入口节点
  • Vite + Vue3 +Vant4构建项目时,按需引入使用Toast组件,引用 showToast 时出现编译报错的解决方案
  • 小程序怎么自定义tabbar
  • 技术维护费计入
  • 4月满月是几号
  • php匿名函数为何不匿名
  • 高通 adc
  • 预训练的目的
  • php读取word内容
  • 农产品小规模纳税人
  • 申报增值税税额正确,销售额少0.94
  • 怎样网上抄税
  • 哪些企业可以开13点税票
  • 资产处置收益的账务处理
  • 织梦cms怎么样
  • 领取营业执照后超过30天
  • 非盈利机构怎么说
  • 电子发票如何作废,具体怎么操作
  • 背书转让流程图
  • 资金占用费的税费是多少
  • 供应商费用是什么
  • 收员工伙食费会计分录
  • 职工薪酬实际发生额忘记填会有风险吗
  • 单位食堂用餐免费的账务处理
  • 验资费如何做账务处理
  • 年底盈利但有往年亏损怎么处理
  • 税控盘冲红怎么操作
  • 对公账户可以报税吗
  • 营业收入和利润的区别
  • 老办法退休金如何计算
  • 备查账簿有没有固定的格式
  • 编写高质量代码改善JAVA程序的151个建议
  • sql server错误代码1608
  • sql1068错误
  • win8系统设置在哪里
  • centos7yum安装
  • centos6.5怎么安装
  • win10 20h2怎么更新
  • react either
  • unity商店资源在unity中打开
  • shell echo 特殊字符
  • python console不能用
  • js日历插件
  • jquery的优点和缺点
  • jquery图片放大效果
  • 迅雷继续下载
  • python批量执行命令
  • HttpClient.execute() 阻塞问题
  • 浙江省工会经费减免最新政策2019年
  • 北京海淀区国税有几个办税大厅?
  • 社保缴费电子回单在哪里截图
  • 有限责任公司自然人独资属于什么企业
  • 个人自行申报纳税
  • 北京税务查验中心官网
  • 税务注销了怎么查看纳税申报表
  • 云南医保可以网上买药吗
  • 河南工商年检网上申报APP
  • 新企业会计准则长期待摊费用
  • 免责声明:网站部分图片文字素材来源于网络,如有侵权,请及时告知,我们会第一时间删除,谢谢! 邮箱:opceo@qq.com

    鄂ICP备2023003026号

    网站地图: 企业信息 工商信息 财税知识 网络常识 编程技术

    友情链接: 武汉网站建设