588
文章
329593
访问
分类
暂无分类
标签
暂无标签
汉诺塔递归问题：一个从佛教神话到python代码的蜕变
发布于2020-05-14 18:56 阅读(222) 评论(0) 点赞(6) 收藏(3)
今天我会用故事的形式带大家了解汉诺塔的问题。
我们先从汉诺塔的来源说起，汉诺塔问题是1883年由法国科学家卢卡斯发明的，关于这个游戏有一个传说，传说在佛教里面有一个神叫梵天，他创造世界的时候在印度的胜地贝拿勒斯造了一个庙宇，庙宇里有黄铜做的台子，台子上有三根宝石柱子，在其中一个台子上，梵天放了64个金片，上面小，下面大，一个僧侣在移动着金片，移动的规则是：
- 每次只能移动一片，并且只能从一根柱子移动到另一根柱子
- 必须保证小片在上，大片在下
梵天说当这些金片从一根柱子移动到另一根柱子上的时候，世界就会毁灭，这就是汉诺塔的传说来源。
接下来我用下图表示：将A柱子上有2块金片，3块金片和4块金片的3种情况移动C柱上的过程：
这里就应用到了我之前文章提到过的divide-and-conquer思想，我们在移动4块金片时，我们会先想到将上面三块金片的整体移动到2柱上，此时就能将最大块的金片移动到三柱上，再将三块金片整体移动到三柱上即可完整。那么接下来我们就考虑三块金片如何移动的呢？我们就去考虑最上面的两块金片做为整体…以此类推，直到考虑到移动一块金片的移动
（参考下两图及上图理解）这个拆分的思想过程就称之为递归！
我们记F（n）为移动的次数，n为金片个数，我们发现F（n）= 2F（n-1）+1：
F（1）= 1，F（2）= 3，F（3）= 7…此时发现规律：F（n）= 2^n-1
所以F（64）= 1.8*10^19步=1800亿亿步！64个金块移动完宇宙都毁灭了！
我们借用Python 来输出这个移动的过程：
def hanoi(n, a, b, c):
if n == 1:
print(a, '-->', c)
else:
hanoi(n-1, a, c, b)
print(a, '-->', c)
hanoi(n-1, b, a, c)
print(hanoi(3, 'A', 'B', 'C'))
"""
output：
A --> C
A --> B
C --> B
A --> C
B --> A
B --> C
A --> C
"""
原文链接:https://blog.csdn.net/Huangkaihong/article/details/106097363
所属网站分类: 技术文章 > 博客
作者：9384vfnv
链接： https://www.pythonheidong.com/blog/article/371529/af214ee7fffa2a943567/
来源： python黑洞网
任何形式的转载都请注明出处,如有侵权 一经发现 必将追究其法律责任
昵称:
评论内容：(最多支持255个字符)