汉诺塔的图解递归算法.pdf
免费下载
汉诺塔的图解递归算法
一．起源：
汉诺塔（又称河内塔）问题是源于印度一个古老传说的益智玩具。大梵天创造世界的时
候做了三根金刚石柱子，在一根柱子上从下往上按照大小顺序摞着 64 片黄金圆盘。大梵天
命令婆罗门把圆盘从下面开始按大小顺序重新摆放在另一根柱子上。并且规定，在小圆盘上
不能放大圆盘，在三根柱子之间一次只能移动一个圆盘。
二．抽象为数学问题：
如下图所示，从左到右有 A、B、C 三根柱子，其中 A 柱子上面有从小叠到大的 n 个圆
盘，现要求将 A 柱子上的圆盘移到 C 柱子上去，期间只有一个原则：一次只能移到一个盘
子且大盘子不能在小盘子上面，求移动的步骤和移动的次数
解：（1）n == 1
第 1 次 1 号盘 A---->C sum = 1 次
(2) n == 2
第 1 次 1 号盘 A---->B
第 2 次 2 号盘 A---->C
第 3 次 1 号盘 B---->C sum = 3 次
（3）n == 3
第 1 次 1 号盘 A---->C
第 2 次 2 号盘 A---->B
第 3 次 1 号盘 C---->B
第 4 次 3 号盘 A---->C
第 5 次 1 号盘 B---->A
第 6 次 2 号盘 B---->C
第 7 次 1 号盘 A---->C sum = 7 次
不难发现规律：1 个圆盘的次数 2 的 1 次方减 1
2 个圆盘的次数 2 的 2 次方减 1
3 个圆盘的次数 2 的 3 次方减 1
。 。 。 。 。
n 个圆盘的次数 2 的 n 次方减 1
故：移动次数为：2^n - 1
三．算法分析（递归算法）：
我们在利用计算机求汉诺塔问题时，必不可少的一步是对整个实现求解进行算法分
析。到目前为止，求解汉诺塔问题最简单的算法还是同过递归来求。
实现这个算法可以简单分为三个步骤：
（1） 把 n-1 个盘子由 A 移到 B；
（2） 把第 n 个盘子由 A 移到 C；
（3） 把 n-1 个盘子由 B 移到 C；
从这里入手，在加上上面数学问题解法的分析，我们不难发现，移到的步数必定为奇数步：
（1）中间的一步是把最大的一个盘子由 A 移到 C 上去；
（2）中间一步之上可以看成把 A 上 n-1 个盘子通过借助辅助塔（C 塔）移到了 B
上，
（3）中间一步之下可以看成把 B 上 n-1 个盘子通过借助辅助塔（A 塔）移到了 C
of 5
免费下载
【版权声明】本文为墨天轮用户原创内容，转载时必须标注文档的来源（墨天轮），文档链接，文档作者等基本信息，否则作者和墨天轮有权追究责任。如果您发现墨天轮中有涉嫌抄袭或者侵权的内容，欢迎发送邮件至：contact@modb.pro进行举报，并提供相关证据，一经查实，墨天轮将立刻删除相关内容。
下载排行榜
评论