位置: 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语言中如何防止函数重名)

  • vivox70怎么关闭后台应用(vivoX70怎么关闭开发者模式)

    vivox70怎么关闭后台应用(vivoX70怎么关闭开发者模式)

  • 电脑MAC系统任务栏图标怎么调整大小(mac系统任务管理 快捷键)

    电脑MAC系统任务栏图标怎么调整大小(mac系统任务管理 快捷键)

  • 怎么取消淘宝闲鱼同步的呢(怎么取消淘宝闲鱼绑定)

    怎么取消淘宝闲鱼同步的呢(怎么取消淘宝闲鱼绑定)

  • 苹果手机怎么设置视频铃声(苹果手机怎么设置铃声来电铃声)

    苹果手机怎么设置视频铃声(苹果手机怎么设置铃声来电铃声)

  • 电脑版WPS表格斜框线怎么设置(电脑wps表格斜线制作)

    电脑版WPS表格斜框线怎么设置(电脑wps表格斜线制作)

  • med al00什么型号(华为MEDal00什么型号)

    med al00什么型号(华为MEDal00什么型号)

  • vivo手机闪退怎么修复(vivo手机总是闪退怎么回事)

    vivo手机闪退怎么修复(vivo手机总是闪退怎么回事)

  • 陌陌素材包下载失败是什么原因导致的(陌陌素材包下载失败是什么意思)

    陌陌素材包下载失败是什么原因导致的(陌陌素材包下载失败是什么意思)

  • 苹果8p换外屏后遗症(8p换了外屏)

    苹果8p换外屏后遗症(8p换了外屏)

  • cad双击打开没反应(cad双击不能直接打开)

    cad双击打开没反应(cad双击不能直接打开)

  • 屏幕亮但是触屏不能用(屏幕亮触屏没反应)

    屏幕亮但是触屏不能用(屏幕亮触屏没反应)

  • qq说说设置部分人可见对方知道吗(qq说说部分可见别人能看到吗)

    qq说说设置部分人可见对方知道吗(qq说说部分可见别人能看到吗)

  • 佳能相机连拍怎么设置(佳能相机连拍怎么拍)

    佳能相机连拍怎么设置(佳能相机连拍怎么拍)

  • 怎样解除手机pin码(怎样解除手机屏幕锁屏设置)

    怎样解除手机pin码(怎样解除手机屏幕锁屏设置)

  • 好友删了聊天记录能恢复吗(好友删了聊天记录还有吗)

    好友删了聊天记录能恢复吗(好友删了聊天记录还有吗)

  • 苹果手机自带软件有哪些(苹果手机自带软件可以卸载吗)

    苹果手机自带软件有哪些(苹果手机自带软件可以卸载吗)

  • 苹果单只airpods怎么买(苹果单只耳机序列号无效)

    苹果单只airpods怎么买(苹果单只耳机序列号无效)

  • 华为云空间通知怎么关掉(华为云空间 提醒)

    华为云空间通知怎么关掉(华为云空间 提醒)

  • 户户通怎样重新定位(户户通怎样重新定位基站)

    户户通怎样重新定位(户户通怎样重新定位基站)

  • 苹果12系统隐藏app(iphone12隐藏软件)

    苹果12系统隐藏app(iphone12隐藏软件)

  • 荣耀9x怎么分屏(荣耀9x怎么分屏和平精英)

    荣耀9x怎么分屏(荣耀9x怎么分屏和平精英)

  • honor v20是什么手机(honorv20是什么手机型号)

    honor v20是什么手机(honorv20是什么手机型号)

  • nio bio aio的区别(简述 bio, nio, aio 的区别)

    nio bio aio的区别(简述 bio, nio, aio 的区别)

  • 录音大于30m如何发微信(录音大于30m如何发送)

    录音大于30m如何发微信(录音大于30m如何发送)

  • 回执编号好友在哪辅助(回执编号好友在哪能看到)

    回执编号好友在哪辅助(回执编号好友在哪能看到)

  • 一加7有没有耳机孔(一加7有没有耳机插孔)

    一加7有没有耳机孔(一加7有没有耳机插孔)

  • 苹果xsmax可以两个微信吗(苹果xSmax可以两个微信吗)

    苹果xsmax可以两个微信吗(苹果xSmax可以两个微信吗)

  • 魅族电话录音在哪里找(魅族电话录音在哪里找出来)

    魅族电话录音在哪里找(魅族电话录音在哪里找出来)

  • 西瓜视频怎么上传小视频(西瓜视频如何带v)

    西瓜视频怎么上传小视频(西瓜视频如何带v)

  • 小规模纳税人代收水电费税率
  • 金税盘系统维护注册码
  • 原始凭证分类的目的是什么?
  • 销售人员的工资属于什么会计科目
  • 特许权使用费怎样向海关申报
  • 委托境外研发费用不超过境内符合条件的研发费用
  • 普通增值税发票是否可以抵扣?
  • 应交税费核算的税金有哪些
  • 融资租赁开具的发票是货物还是租金
  • 预收款 交税
  • 企业最应避免的外部环境和内部条件组合是
  • 期末数未分配利润为负数的会计分录怎么处理?
  • 年末会计做账怎样少交企业所得税呢?
  • 商业折扣如何开发票
  • 发票作废了还能查验吗
  • 广告业发生错账怎么办
  • 存货计价方法的选择对利润表中的项目没有影响
  • 基建项目税率
  • 股权质押权如何实现
  • 保税区内的货物交易
  • 企业享受小型微利政策
  • 企业合并的会计分录
  • 计提代扣代缴个税
  • 单位支付经济补偿金的情形
  • php header refresh
  • PHP:xml_get_error_code()的用法_XML解析器函数
  • 其他综合收益是什么意思
  • 餐饮发票可以计入研发费用吗
  • 普通发票主营业务收入销项负数发票怎么做账
  • php笔记程序
  • 国有资产无偿使用违反什么规定
  • 结算应付职工薪酬怎么算
  • 员工的生活费会不会扣个税
  • 外贸企业出口免抵退
  • vue+java+mysql
  • 会计年报表怎么做
  • 异地提供建筑服务预缴企业所得税
  • 只有进项税没有销项
  • 汇兑损益计入什么科目
  • vue项目创建流程
  • 处置固定资产清理费用影响利润吗
  • phpcms默认密码
  • 织梦如何给栏目增加缩略图
  • 所得税费用为什么不计入营业利润
  • 发票打印机如何安装在电脑上
  • java方法的返回值类型有哪些
  • 小规模纳税人要报个人所得税吗
  • sql server数据查询语句
  • 汽车销售公司赠车合法吗
  • 长期借款转其他应付款
  • 长期待摊费用待摊费用
  • 公众号认证小额打款流程
  • 旅游业小规模纳税人增值税申报
  • 水利税费会计分录
  • 医院的自助缴费机怎么开具发票
  • 外卖占比总营业额怎么算
  • 记账凭证分为哪几类,应具备哪些主要内容
  • win7怎么添加设备
  • 远程桌面 登录
  • windows没网络是怎么回事
  • ubuntu不支持设置属性
  • windows8.1界面
  • win10高分辨率
  • jquery22插件网
  • node javascript
  • Linux数据库备份的命令
  • unity简单项目
  • javascript怎么设置字体大小
  • android studio downloading
  • 轮廓理论
  • jquery怎么修改样式
  • unity中滚动条控件详解
  • unity 3渲2
  • python一些简单操作
  • 开票物品名称要求
  • 税控发票开票软件提示非征期不得抄报税?是什么意思?
  • 怎样查手机是否维修过
  • 电子税务局房产税怎么申报
  • 哪个部门负责药品检验
  • 河南税筹公司
  • 免责声明:网站部分图片文字素材来源于网络,如有侵权,请及时告知,我们会第一时间删除,谢谢! 邮箱:opceo@qq.com

    鄂ICP备2023003026号

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

    友情链接: 武汉网站建设