图解汉诺塔问题(Java递归实现)汉诺塔简介最近在看数据结构和算法,遇到了一个非常有意思的问题——汉诺塔问题。先看下

先看下百度百科是怎么定义汉诺塔的规则的:

汉诺塔(又称河内塔)问题是源于印度一个古老传说的益智玩具。大梵天创造世界的时候做了三根金刚石柱子,在一根柱子上从下往上按照大小顺序摞着64片黄金圆盘。大梵天命令婆罗门把圆盘从下面开始按大小顺序重新摆放在另一根柱子上。并且规定,在小圆盘上不能放大圆盘,在三根柱子之间一次只能移动一个圆盘。

额,好吧,好像有点啰里啰嗦的。其实一句话就是,在三个柱子之间移动盘子,一次只能移动一个,并且要保证每一步上边的盘子都要比下边的盘子小,最终实现把所有的盘子都从最左边柱子移动到最右边的柱子上。

我找了一个小游戏,可以玩一下,体验一下这个过程。相信我,你玩不过第五关的!嘿嘿,玩不过再过来看一下,我是怎么给你做游戏攻略(作弊)的。

我相信,有很多童鞋在学递归的时候,都会受到这个问题的困扰。别着急,你不是一个人,我第一次看到这个也是一脸懵逼,这什么鬼啊,这么复杂。下面我通过图解的方式,演示整个移动过程,帮助你理解用递归解决这个问题的思想。

我们一步一步从简单到复杂。为了方便,我把三个柱子从左到右分别叫A,B,C。盘子的数字从上到下依次增大。

只有一个盘子的时候,就比较简单了。如图,只需要一步,直接把第1个盘子从A移动到C就完成了。

两个盘子的时候,也比较简单,如下图,只需要借助一下B柱子即可完成。

这个过程可以表述为:

把第1个盘子从A移到B把第2个盘子从A移到C把第1个盘子从B移到C三个盘子三个盘子的时候,稍微复杂一些,但是我们一般也是可以通过心算,把过程推演出来的。

把第1个盘子从A移到C把第2个盘子从A移到B把第1个盘子从C移到B把第3个盘子从A移到C把第1个盘子从B移到A把第2个盘子从B移到C把第1个盘子从A移到Cn个盘子铛铛铛,现在到了第四关了,我相信已经有部分小伙伴感觉开始吃力了,通过演算就不好搞了。如果你搞不出来,我们就借助计算机来帮我们推算出来这个过程(哈哈,我是不是很机智)。

其实,通过前面的三个例子,我们可以发现,盘子的移动是有规律可循的。

细心的你有没有发现,在每一步盘子移动的过程中,总会有一步,是下边最大的盘子,从A移到C的。如,两个盘子,就是第2个盘子从A移到C,三个盘子,就是第3个盘子从A移到C。

仔细观察,以三个盘子为例,把第3个盘子从A移动到C这一步,其实,第1个和第2个盘子是已经按顺序摆放好了的,即一起放在中间的B柱子。

因此,我们可以把这个动作抽象出来,把除了最下边的盘子之外的其他盘子看成一个整体。这样的话,整个流程,就和两个盘子的移动过程没什么两样了。总共就三步,我以四个盘子为例。看以下动画,

整个过程可以表述为:

把1,2,3盘子整体从A移到B(可以认为是借助C柱子移动的),把第4个盘子从A移到C(不需要借助额外的柱子),把1,2,3盘子整体从B移到C(借助A柱子)但是,这只是我们把它抽象出来的过程,游戏中不允许我们整体移动,怎么办呢。

好说,我把1,2,3这个整体再拆分,不就是三个盘子的移动过程嘛。完全可以把1,2看成一个整体一起移动,3单个移动,也是三步完成。然后再拆分,直到只有最后一个盘子的时候,就完成了整个过程。

所以,可以看到,这个拆分的过程,就是不断递归的过程。而每次递归时,都可以把第1个盘子到第n-1个盘子看成一个整体。每一次递归都是一个三步曲,借助另外一个柱子,从当前柱子移动到目标柱子。看代码,

publicclassHanioTest{publicstaticvoidmain(String[]args){intn=4;chara='A',b='B',c='C';hanio(n,a,b,c);}/****@paramn一共需要移动的盘子*@parama盘子移动的起始柱子*@paramb借助的柱子*@paramc盘子需要移动到的目标柱子*/publicstaticvoidhanio(intn,chara,charb,charc){//只有一个盘子的时候,就直接从A移到Cif(n==1){move(n,a,c);}else{//三步曲,注意观察,a,b,c三个的位置变化//1.把n-1个盘子看成一个整体,借助C从A移动到Bhanio(n-1,a,c,b);//2.把第n个盘子从A移动到Cmove(n,a,c);//3.再把n-1盘子整体,借助A从B移动到Chanio(n-1,b,a,c);}}publicstaticvoidmove(intn,chara,charb){System.out.println("把第"+n+"个盘子从"+a+"移到"+b);}}聪明的你,如果游戏第四关通关了,可以用来检查一下这个代码执行过程是否和你的移动过程一致。

第五关,如果你不借助程序,能心算出来,我只能说你太厉害了,I服了YOU,佩服佩服。

那么第六关,第七关呢。

回到最开始,百度百科说要移动64片黄金圆盘,OMG的,如果谁能手动计算出来,那才是真的大神(不过,话说,谁会这么无聊呢,哈哈)。

THE END
1.什么是算法?算法第一篇本文阐述自己对算法的理解,如果不正确,还请指正。 算法是实践数学是本文最新颖最核心的观点。我们要区分应用数学和实践数学的区别,也要区分计算数学和实践数学的区别。 计算数学和应用数学都是世界观,都是理论,而并没有重视实践的重要性。 而算法就是更加符合辩证唯物论的学科,这https://mp.weixin.qq.com/s?__biz=MjM5NzEyMzg4MA==&mid=2649498413&idx=8&sn=1a3bb98bcd0ef37a0dc6bbb4600f04f0&chksm=bec6416a89b1c87c457038d43307c6877407f95096e77eb430361611fd4c17dbbac9d000fc76&scene=27
2.什么是算法?(翻译文章)算法的概念来自于哪个数学家“算法”一词源自波斯学者Abdullah Jafar Muhammad ibn Musa Al-Khwarizmi的名字,他是九世纪的数学家和天文学家。他的工作为代数和数学算法过程的发展奠定了基础。他经常被称为“代数之父”。Al-Khwarizmi 对算法定义的贡献是深远的: 算法是一种定义明确的计算程序,由一组有限的步骤组成,接受一个或多个输入并产生https://blog.csdn.net/qq_20245171/article/details/143428003
3.科技名词算法algorithm科技博览科普博览资讯核心提示:算法algorithm定义:解决给定问题的确定的计算机指令序列,用以系统地描述解决问题的步骤。学科:计算机科学技术_理论计算机科学_算法设计与分析相关名词:指令 程序 软件开发图片来源:视觉中国【延伸阅读】算法是解题方案准确而完整的描述,是一系列解决问题的清晰指令,代表着用系统的方法描述解决问题的策略机制。也就http://www.agricoop.net/news/show.php?itemid=21242
4.粒子群算法(ParticleswarmoptimizationPSO)百度百科版本 粒子群算法,也称粒子群优化算法或鸟群觅食算法(Particle Swarm Optimization),缩写为 PSO, 是由J. Kennedy和R. C. Eberhart等开发的一种新的进化算法(Evolutionary Algorithm – EA)。 PSO 算法属于进化算法的一种,和模拟退火算法相似,它也是从随机解出发,通过迭代寻找最优解,它也是通过适应度来评价https://cloud.tencent.com/developer/article/1555832
5.PythonRSA算法使用dmyHero基于python使用RSA算法加密数据 算法百科 (https://baike.baidu.com/item/RSA算法/263310?fromtitle=RSA&fromid=210678"RSA算法百度百科") RSA算法的三位爸爸们 Python代码实现 公钥密钥为随机生成 MIGfMA0GCSqGSIb3DQEBAQUAA4GNADCBiQKBgQDeOF64E9PkZ7XR4xEz4BZs4z0X https://www.cnblogs.com/rain-chenwei/p/15209423.html
6.一文看懂机器学习「3种学习方法+7个实操步骤+15种常见算法」15种经典机器学习算法 ner“> 百度百科+维基百科 百度百科版本 机器学习(Machine Learning, ML)是一门多领域交叉学科,涉及概率论、统计学、逼近论、凸分析、算法复杂度理论等多门学科。 专门研究计算机怎样模拟或实现人类的学习行为,以获取新的知识或技能,重新组织已有的知识结构使之不断改善自身的性能。 它是人工智https://easyai.tech/ai-definition/machine-learning/
7.组合算法组合算法(combinatorial algorithm)是组合学的一个研究分支,一些组合问题需用电子计算机解决,当研究如何进行计算时,就需要研究算法,组合算法是一类不同于代数计算的方法,为使这种算法能够有效地进行,对于每种组合算法,必须研究其组合结构和在此基础上讨论其时间的复杂性和空间的复杂性问题,即对算法所需的时间和存储https://baike.baidu.com/item/%E7%BB%84%E5%90%88%E7%AE%97%E6%B3%95/10537547
8.计算机视觉和算法计算机视觉算法分类摘自百度百科。。。 (1)基于区域的跟踪算法 起初,基于区域的跟踪算法中所用到的目标模板是固定的,如 Lucas 等人提出 Lucas-Kanade 方法,该方法利用灰度图像的空间梯度信息寻找最佳匹配区域,确定目标位置。之后,更多的学者针对基于区域方法的缺点进行了不同的改进,如:Jepson 等人提出的基于纹理特征的自适应目标外观模型https://blog.51cto.com/u_16099326/9231856
9.干货遗传算法(GeneticAlgorithm)(附代码及注释)1.2 遗传算法的执行过程(参照百度百科) 遗传算法是从代表问题可能潜在的解集的一个种群(population)开始的,而一个种群则由经过基因(gene)编码的一定数目的个体(individual)组成。每个个体实际上是染色体(chromosome)带有特征的实体。 染色体作为遗传物质的主要载体,即多个基因的集合,其内部表现(即基因型)是某种基因组合,https://zhuanlan.zhihu.com/p/555431690