+关注
已关注

分类  

暂无分类

标签  

暂无标签

日期归档  

2019-07(2)

2019-08(106)

2019-09(110)

2019-10(14)

2019-11(8)

汉诺塔递归问题:一个从佛教神话到python代码的蜕变

发布于2020-05-14 18:56     阅读(222)     评论(0)     点赞(6)     收藏(3)


0

1

2

3

4

5

6

今天我会用故事的形式带大家了解汉诺塔的问题。
我们先从汉诺塔的来源说起,汉诺塔问题是1883年由法国科学家卢卡斯发明的,关于这个游戏有一个传说,传说在佛教里面有一个神叫梵天,他创造世界的时候在印度的胜地贝拿勒斯造了一个庙宇,庙宇里有黄铜做的台子,台子上有三根宝石柱子,在其中一个台子上,梵天放了64个金片,上面小,下面大,一个僧侣在移动着金片,移动的规则是:

  1. 每次只能移动一片,并且只能从一根柱子移动到另一根柱子
  2. 必须保证小片在上,大片在下

梵天说当这些金片从一根柱子移动到另一根柱子上的时候,世界就会毁灭,这就是汉诺塔的传说来源。

接下来我用下图表示:将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

0

1

2

3

4

5

6



所属网站分类: 技术文章 > 博客

作者:9384vfnv

链接: https://www.pythonheidong.com/blog/article/371529/af214ee7fffa2a943567/

来源: python黑洞网

任何形式的转载都请注明出处,如有侵权 一经发现 必将追究其法律责任

6 0
收藏该文
已收藏

评论内容:(最多支持255个字符)