hanoi塔问题如下图所示_hanoi塔问题最经典的算法

hanoi塔问题如下图所示_hanoi塔问题最经典的算法什么是hanoi塔?汉诺塔问题:古代有一个梵塔,塔内有三个座A、B、C,A座上有64个盘子,盘子大小不等,大的在下,小的在上。有一个和尚想把这64个盘子从A座移到B座,但每次只能允许移动一个盘子,并且在移动过程中,3个座上的盘子始终保持大盘在下,小盘在上。如下图问题解答问题定义我们把左边的柱子叫做A,中间的柱子叫做B,右边的柱子叫做Chanoi塔的搬运过程;i

大家好,又见面了,我是你们的朋友全栈君。如果您正在找激活码,请点击查看最新教程,关注关注公众号 “全栈程序员社区” 获取激活教程,可能之前旧版本教程已经失效.最新Idea2022.1教程亲测有效,一键激活。

Jetbrains全家桶1年46,售后保障稳定

什么是hanoi塔?

汉诺塔问题:古代有一个梵塔,塔内有三个座A、B、C,A座上有64个盘子,盘子大小不等,大的在下,小的在上。有一个和尚想把这64个盘子从A座移到B座,但每次只能允许移动一个盘子,并且在移动过程中,3个座上的盘子始终保持大盘在下,小盘在上。如下图

hanoi塔图示

问题解答

问题定义
我们把左边的柱子叫做A,中间的柱子叫做B,右边的柱子叫做C

hanoi`塔的搬运过程;
i :左边的柱子只有两个圆盘

我们先假设在A柱子上只有两个圆盘,不用图我们用大脑想象出来最佳流程就是,现在最小的放在B柱子上面然后把大的放在C上面,最后把B柱子上面的小圆盘放在C柱子上。

ii:左边的柱子上面有三个圆盘 过程如下图: `在这种情况下,我们可以把上面的两个圆盘看作是一个,然后又回到了i情况,下图展示了三个圆盘的转移过程` ![三个圆盘的hanoi过程](https://img-blog.csdnimg.cn/img_convert/f8d12ace981cf0cd72af4da2f57daaf1.png) iii:左边的柱子上有四个圆盘的时候 在这种情况我们通过作图做出hanoi的转移流程是很困难的了,我们可以用在`ii`中提及到的过程,就是我们先把上面的三个看作是一个,我们第一步的目的就是把前三个移动到中间的柱子上去。下面简单说一下转移步骤 1. 将A柱子上面的三个移动到B柱子上面(借助C柱子) 2. 将A柱子上面中最下面的圆盘移动到C柱子上面 3. 将B柱子上面的所有圆盘移动到C柱子上面(借助A柱子) 过程如下图: ![四个圆盘的hanoi](https://img-blog.csdnimg.cn/img_convert/7e80f4dd8a45878f9ae993e6a0fa6ea8.png) > 问题总结 > 通过上面的描述我们把hanoi移动的步骤一般化 >


  1. 将左边柱子上的N-1个圆盘移动带中间的柱子上
  2. 将第N个圆盘移动到最右边的柱子
  3. 将中间柱子上的所有圆盘移动到最右边的柱子

下面我们给出具体的代码

void hanoi(int n,char A,char B,char C)
{
    if(n<=1) {
        printf("1 move %c to %c\n",A,C);
        return ;
    }
    hanoi(n-1,A,C,B);
    printf("%d move %c to %c \n",n,A,C);
    hanoi(n-1,B,A,C);
}

Jetbrains全家桶1年46,售后保障稳定

不要在看了,这就是全部代码了。已经没有了
╭︿︿︿╮
{/ o o /}
( (oo) )
︶ ︶︶
以上是对hanoi塔的总体概述,下面就要聊一聊真正的代码流程!

代码详解

hanoi(n,A,B,C)代表的意义就是讲n个圆盘从A移动到C借助B;

  • n等于1的时候,就代表把当前A中最大的圆盘直接从A移动到C
  • n等于2的时候,就调用hanoi(2,A,B,C)也就是执行下面的三个步骤下面就是本文中重点了
  1. 调用honoi(1,A,C,B)就是相当于把***B柱和C柱交换***了
  2. 执行打印语句,不进行继续调用。所以不用交换柱子
  3. 调用hanoi(1,B,A,C)相当于把***B柱和A柱交换***了
    上面的语句可以表述为:
hanoi(1,A,C,B); 
printf("%d move %c to %c \n",n,A,C);
hanoi(1,B,A,C); 

这就是对代码的解释!
当圆盘更多的时候无非就是进行递归知道递归到上面的状态,比如有三个圆盘的时候,调用的是:

hanoi(2,A,C,B); //step1
printf("%d move %c to %c \n",n,A,C);
hanoi(2,B,A,C); 

只要理解了前两个对后面的理解也就不难了!还有一点题外话,当递归到程序注释的step1的时候,会为后续语句分配空间但不执行

hanoi塔还有一个进阶的题目就是判断当前的状态时第几个最优的状态,将在下篇文章进行讲述!

如果对我的文章感兴趣可以关注的公众号:云影原生。
在这里插入图片描述

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/210738.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)
blank

相关推荐

  • STL库 总览_stl库函数

    STL库 总览_stl库函数  STL库1泛型程序设计2STL标准模板库2.1STL库的基本组件2.1.1STL基本组件—-容器2.1.2STL基本组件—-迭代器2.1.3STL基本组件—-函数对象2.1.4STL基本组件—-算法3迭代器4容器的基本功能与分类4.1顺序容器  1泛型程序设计  泛型程序设计就是时候,将程序设计的尽量的通用。STL标准库就是泛型程序设计的一个很好的范例。  ◇编写不依赖具体数据类型的程序;  ◇将算法从特定的数据结构中抽象出来,成为通用的;  ◇

    2022年10月10日
  • Keil系列教程(汇总)「建议收藏」

    Keil系列教程(汇总)「建议收藏」推荐分享一个大神的人工智能教程。零基础!通俗易懂!风趣幽默!还带黄段子!希望你也加入到人工智能的队伍中来!http://www.captainbed.net/strongerhuang我的网站:https://www.strongerhuang.com我的知乎:https://www.zhihu.com/people/strongerHuang.com推荐在我公众…

  • ubuntu20.04安装pycharm2021.3.3_ubuntu镜像安装

    ubuntu20.04安装pycharm2021.3.3_ubuntu镜像安装1.下载PyCharmhttps://www.jetbrains.com/pycharm/download/#section=linux这里我下载的是社区开源免费版2.解压PyCharm我下载的pycharm放到了下载文件夹中,在下载文件夹中启动终端,输入以下命令解压到当前文件夹tar-xzfpycharm-community-2021.1.3.tar.gz3.在opt目录下新建pycharm文件夹用于放置pycharm程序文件opt文件夹主要是:安装程序的引导和程序文件,如果缺少必

  • vmware15最新激活码2021_通用破解码

    vmware15最新激活码2021_通用破解码,https://javaforall.cn/100143.html。详细ieda激活码不妨到全栈程序员必看教程网一起来了解一下吧!

  • python中关于命名的例子_Python 命名规范入门实例「建议收藏」

    python中关于命名的例子_Python 命名规范入门实例「建议收藏」这篇文章主要为大家详细介绍了Python命名规范入门实例,具有一定的参考价值,可以用来参考一下。对python这个高级语言感兴趣的小伙伴,下面一起跟随512笔记的小编两巴掌来看看吧!一,包名、模块名、局部变量名、函数名全小写+下划线式驼峰example:this_is_var二,全局变量全大写+下划线式驼峰example:GLOBAL_VAR三,类名首字母大写式驼峰example:ClassNa…

  • 进程间通信方式——共享内存「建议收藏」

    进程间通信方式——共享内存「建议收藏」进程间通信方式共享内存和与共享内存函数详解,以及模拟共享内存实现进程间通信,以及共享内存的优缺点。

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号