首页 / 算法 / 算法题 - 汉诺塔问题 - Python
算法题 - 汉诺塔问题 - Python
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了算法题 - 汉诺塔问题 - Python，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含2457字，纯文字阅读大概需要4分钟。
内容图文
问题描述：
在汉诺塔传说，有三根柱子可以用大写字母A， B， C命名，其中只有A柱子摆放n片圆盘(1<=n<=64)， 若要把A柱子上的所有圆盘转移到 C柱子上，问最少需要移动多少次圆盘？
移动圆盘的规则如下：
- 每次只能移动一片圆盘
- 任何情况下，大的圆盘必须摆放在小的圆盘之下
问题分析：
昨天baidu校招一面碰到的题目，问了其他同学，基本上一面都是以基础的数据结构题目为主，现在总结一下。问题估计是经典的不能在经典了，递归解决，这个题目对于递归的理解还是比较深刻。当时问了两个问题：1，是求出移动次数；2，输出每一步移动的情况。个人感觉对这类问题，重在理解。
递归解决，具体步骤如下：
（1）设Hanoi(n, A, B, C)表示，把A中的n个圆盘，通过中间媒介B，移动到C。现在思考如何分解Hanoi(n, A, B, C)：
-
要想把
A中的n个圆盘，移动到C，一定会经过什么操作？ -
第一步：一定会先把
A中上面的n-1圆盘移动到B， 这个过程中C一定是中间媒介。 -
第二步：然后，把
A中剩下的最大的一个圆盘（也就是最下面那个圆盘）移动到C。 -
第三步：最后，把
B中所有的n-1过个圆盘移动到C， 很显然，现在A一定是中间媒介。 -
通过上面三个步骤，可以依次类推，子问题又形成子问题，然后递归解决（切记，重在理解，不要死记）
（2） 《数据结构教程第四版》中给出的C++代码如下：
void Hanoi(int n,char a,char b,char c)
{
if (n==1)
printf("\t将第%d个盘片从%c移动到%c\n",n,a,c);
else
{
Hanoi(n-1,a,c,b); //对应着，第一步
printf("\t将第%d个盘片从%c移动到%c\n",n,a,c); //对应着，第二步
Hanoi(n-1,b,a,c); //对应着，第三步
}
}
（3）当初始值A中有 n 个圆盘的时候，要移动多少次？结合上面的代码，不难推出：
??当n = 1时：Hanoi(n)=1
??当n > 1时：Hanoi(n)=2?Hanoi(n?1)+1
??令f(n)=Hanoi(n)+1 ，带入可得：f(n)=2(f(n?1)?1)，像什么？等比数列。进一步得：
?? f(n)=2n，所以得出： Hanoi(n)=2n?1,n>0
Python3实现：
# @Time :2018/10/13
# @Author :LiuYinxing
# 递归
class Solution:
def Hanoi(self, n, a, b, c):
if n == 1:
print('将第%d个盘片从%c移动到%c' % (n, a, c))
else:
self.Hanoi(n - 1, a, c, b) # 把 a 中最上面 n-1 个圆盘移到 b，在 a 中剩下最大的哪一个
print('将第%d个盘片从%c移动到%c' % (n, a, c)) # 把 a 中最大的那个移动到 c
self.Hanoi(n - 1, b, a, c) # 现在，把 b 中上的 n-1 个圆盘，移到 c 中
if __name__ == '__main__':
solu = Solution()
n = 4
a, b, c = 'A', 'B', 'C'
solu.Hanoi(n, a, b, c)
注意： n不应过大，从推导公式可以看出，n = 64时，需要的步数普通计算机已经跑不了了，别说我的古董笔记本了。
声明： 总结学习，有问题或不妥之处，可以批评指正哦。
推导参考：www.cnblogs.com/vsky/p/5014657.html
内容总结
以上是互联网集市为您收集整理的算法题 - 汉诺塔问题 - Python全部内容，希望文章能够帮你解决算法题 - 汉诺塔问题 - Python所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。