网站seo优化

您现在的位置是:主页 > 服务项目 > Python编程 >

用Python几行代码破解《汉诺塔》游戏,递归用好简直就是开挂!

2020-09-10 14:31Python编程 人已围观

简介汉诺塔是一个发源于印度的益智游戏,也叫河内塔。 游戏规定:在小圆盘上不能放大圆盘,在三根柱子之间一次只能移动一个圆盘。 游戏起源: 相传印度神话中的大梵天创造的三个金...

汉诺塔
汉诺塔是一个发源于印度的益智游戏,也叫河内塔。
 
游戏规定:在小圆盘上不能放大圆盘,在三根柱子之间一次只能移动一个圆盘。

游戏起源:
相传印度神话中的大梵天创造的三个金刚柱,一根柱子上叠着上下从小到大64个黄金圆盘。大梵天命令婆罗门将这些圆盘按从小到大的顺序移动到另一根柱子上,其中大圆盘不能放在小圆盘上面。当这64个圆盘移动完的时候,世界就将毁灭。 

汉诺塔预言的宇宙寿命还有多久:
那么好多人会问64个圆盘移动到底会花多少时间?那么古代印度距离现在已经很远,这64个圆盘还没移动完么?我们来通过计算来看看要完成这个任务到底要多少时间? 
我们首先利用数学上的数列知识来看看F(n=1)=1,F(n=2)=3,F(n=3)=7,F(n=4)=15……F(n)=2F(n-1)+1; 
我们使用数学归纳法可以得出通项式:F(n)=2^n-1。当n为64时F(n=64)=18446744073709551615。 
我们假设移动一次圆盘为一秒,那么一年为31536000秒。那么18446744073709551615/31536000约等于584942417355天,换算成年为5845.54亿年。 
目前太阳寿命约为50亿年,太阳的完整寿命大约100亿年。所以不用担心了,可能我们整个人类文明都等不到移动完整圆盘的那一天。

 
算法分析(递归算法):
       我们在利用计算机求汉诺塔问题时,必不可少的一步是对整个实现求解进行算法分析。到目前为止,求解汉诺塔问题最简单的算法还是同过递归来求。
 
       实现这个算法可以简单分为三个步骤:
 
    (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上;

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)
# 调用
hanoi(5, 'A', 'B', 'C')

仅仅9行代码就解决了!

如果用C语言则需要32行代码,用JAVA需要28行,C#26行,感兴趣的小伙伴可以自行百度一下用这些语言实现汉诺塔程序的代码,对比一下Python是不是最精简呢!

Tags: 算法  Python  递归  汉诺塔 

网站建设
    网站建设

相关推荐

    网站优化

热搜关键词

网站统计

  • 信息统计272条资讯
  • 关键词统计词库传送
  • 联系番木:高效沟通,用心服务
  • 网站建设