汉诺塔问题(解出来了带你看洛丽塔) 深藏阁楼爱情的钟 2024-04-17 06:17 11阅读 0赞 > ![a9447daac3744728aec56e3ef72844d7.jpeg][] > > ?本文作者:大家好,我是paperjie,感谢你阅读本文,欢迎一建三连哦。 > > ?内容专栏:这里是《算法详解》,笔者用重金(时间和精力)打造,将算法知识一网打尽,希望可以帮到读者们哦。 > > ?内容分享:本期会对C语言中的汉诺塔进行分析,讲解什么是汉诺塔,怎样实现冒泡排序。 > > ?:不要998,只要一件三连,三连买不了吃亏,买不了上当(写作不易,求求了?) **目录** ?前言 ?什么叫汉诺塔 ?汉诺塔移动过程分析 ?汉诺塔移动次数分析 ?具体代码分析 ?总结 -------------------- ## ?前言 ## 上期文章我们对c语言中的冒泡排序进行了详细的分析,对于什么是冒泡排序,冒泡排序的思想,怎么实现它进行了分析,让大家对冒泡排序有了清晰的认识。接下来会对汉诺塔问题进行讲解,大家可以端上小板凳了。 ## ?什么叫汉诺塔 ## **汉诺塔**(Tower of Hanoi),又称**河内塔**,是一个源于[印度][Link 1]古老传说的[益智玩具][Link 2]。大[梵天][Link 3]创造世界的时候做了三根[金刚石][Link 4]柱子,在一根柱子上从下往上按照大小顺序摞着64片黄金圆盘。[大梵天][Link 5]命令婆罗门把圆盘从下面开始按大小顺序重新摆放在另一根柱子上。并且规定,在小圆盘上不能放大圆盘,在三根柱子之间一次只能移动一个圆盘。这就是汉诺塔的来源,现在逐渐演变成了一个益智游戏。大家可以想一想,移动这64片圆盘需要多少次呢?今天我们就用函数的递归来实现一下。 ## ?汉诺塔移动过程分析 ## 汉诺塔的规则是:有abc三根柱子,要a柱子上的盘子都移动到c盘上。要求是每次只能移动一个,且大盘子要在小盘子的下面。这里我们以三阶汉诺塔为例来进行分析,通过分析我们可以发现可以分为三步:第一步 将n-1个通过c柱子移动到b柱子 第二步 将第n个移动到c柱子 第三步 将n-1个通过a柱子移动到c柱子 ![4edc77d981374b5ab5be29c8823612a2.png][] ![651fa88c7acb4e50a7e1a8dcba74fd31.png][] ## ?汉诺塔移动次数分析 ## > 对于这么难以计算的问题,我们可以通过穷尽法来从中找规律: > > <table style="width:500px;"> > <thead> > <tr> > <th>阶层</th> > <th>次数</th> > <th>规律</th> > </tr> > </thead> > <tbody> > <tr> > <td>1</td> > <td>1</td> > <td>2^1-1</td> > </tr> > <tr> > <td>2</td> > <td>3</td> > <td>2^2-1</td> > </tr> > <tr> > <td>3</td> > <td>7</td> > <td>2^3-1</td> > </tr> > <tr> > <td> <p>4</p> <p>......</p> <p>n</p> </td> > <td> <p>15</p> <p>......</p> <p>......</p> </td> > <td> <p>2^4-1</p> <p>.......</p> <p>2^n-1</p> </td> > </tr> > </tbody> > </table> 通过穷尽法,我们发现,这个汉诺塔的移动次数是成指数增长的。当有64个盘子时,我们需要移动2^64次=18446744073709551616次,如果一次一秒,婆罗门要移动5833亿年! n阶移动的次数:和上面说的可分为三步,可以把步骤一将n-1个通过c柱子移动到b柱子的次数为f(x-1),步骤二为1,步骤三n-1个通过a柱子移动到c柱子的次数也为f(x-1). 这n的次数为2\*F(x-1)-1; ## ?具体代码分析 ## 用函数递归求移动的次数 ![58a29ff6ff104ebf8af907f4b8113bf4.png][] 用函数递归打印移动的过程 ![9c46db8f4f764c2c9542d2f27e94e1c5.png][] -------------------- ## ?总结 ## 我们可以发现在思考汉诺塔这样的问题的时候,在脑子里想是很难想明白的。这时我们就需要借助图形在宏观的帮助我们了解 ,使问题清晰化。 [a9447daac3744728aec56e3ef72844d7.jpeg]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/15/c25e3da452fc45d8a8dab72c13b584b9.jpeg [Link 1]: https://baike.baidu.com/item/%E5%8D%B0%E5%BA%A6/121904?fromModule=lemma_inlink [Link 2]: https://baike.baidu.com/item/%E7%9B%8A%E6%99%BA%E7%8E%A9%E5%85%B7/223159?fromModule=lemma_inlink [Link 3]: https://baike.baidu.com/item/%E6%A2%B5%E5%A4%A9/2453640?fromModule=lemma_inlink [Link 4]: https://baike.baidu.com/item/%E9%87%91%E5%88%9A%E7%9F%B3/80698?fromModule=lemma_inlink [Link 5]: https://baike.baidu.com/item/%E5%A4%A7%E6%A2%B5%E5%A4%A9/711550?fromModule=lemma_inlink [4edc77d981374b5ab5be29c8823612a2.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/15/d48ee364faa34cccafafb13fd8573769.png [651fa88c7acb4e50a7e1a8dcba74fd31.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/15/41325b5471af4c1a807799c82405fc7b.png [58a29ff6ff104ebf8af907f4b8113bf4.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/15/69a8f7abd9fe4545be96f146766390e2.png [9c46db8f4f764c2c9542d2f27e94e1c5.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/15/441d90217fe345f7b50603cf6a3e9587.png
相关 汉诺塔问题 import java.util.Scanner; / 汉诺塔问题 不考虑中转,只考虑起始柱子到目标柱子的移动 记住始终一点:中间一个不管是啥柱 素颜马尾好姑娘i/ 2022年09月30日 00:32/ 0 赞/ 130 阅读
相关 汉诺塔问题 1.汉诺塔问题:如果将n个盘子(由小到大)从a通过b,搬到c,搬运过程中不能出现小盘子在大盘子下面的情况。 分析:这个一个递归问题。只要将n-1个盘子从a通过c(没有中间点肯 刺骨的言语ヽ痛彻心扉/ 2022年08月20日 10:14/ 0 赞/ 187 阅读
相关 汉诺塔问题 “汉诺塔问题”的Java重写思路:典型的递归问题。 “汉诺塔问题”的Java重写代码: public class Hanoi { 不念不忘少年蓝@/ 2022年07月21日 05:42/ 0 赞/ 125 阅读
相关 汉诺塔问题 汉诺塔比较经典的实现是利用递归,但也可以利用堆栈。 题意理解:有A,B,C三个柱子,将A柱子上的N个盘子(从大到小排列)移到C柱子上,每次只允许移动一个盘子,并且保证每个柱子 た 入场券/ 2022年05月26日 12:14/ 0 赞/ 143 阅读
相关 汉诺塔问题 汉诺塔 汉诺塔:汉诺塔(又称河内塔)问题是源于印度一个古老传说的益智玩具。大梵天创造世界的时候做了三根金刚石柱子,在一根柱子上从下往上按照大小顺序摞着64片黄金圆盘。大梵 爱被打了一巴掌/ 2022年05月18日 00:40/ 0 赞/ 223 阅读
相关 汉诺塔问题 问题描述: 相传在[古印度][Link 1]圣庙中,有一种被称为汉诺塔(Hanoi)的游戏。该游戏是在一块铜板装置上,有三根杆(编号A、B、C),在A杆自下而上、由大到小按顺 向右看齐/ 2022年04月17日 05:12/ 0 赞/ 260 阅读
相关 汉诺塔问题 汉诺塔问题是经典的递归问题,它的递归类型是:求解问题的方法是递归的。 解题思路: 1. 首先将n-1个盘子从X借助Z移动到Y。 2. 将第n个盘子从X移动到Z。 3. ゝ一世哀愁。/ 2022年03月15日 15:48/ 0 赞/ 187 阅读
相关 汉诺塔问题 汉诺塔(Tower of Hanoi)源于印度传说中,大梵天创造世界时造了三根金钢石柱子,其中一根柱子自底向上叠着64片黄金圆盘。大梵天命令婆罗门把圆盘从下面开始按大小顺序重新 梦里梦外;/ 2021年09月28日 17:06/ 0 赞/ 430 阅读
相关 汉诺塔问题 汉诺塔问题 -------------------- 文章目录 汉诺塔问题 1. 问题描述 2. 问题分析 3. 代 刺骨的言语ヽ痛彻心扉/ 2021年09月23日 23:26/ 0 赞/ 312 阅读
还没有评论,来说两句吧...