python递归——汉诺塔

简介: 汉诺塔的传说法国数学家爱德华·卢卡斯曾编写过一个印度的古老传说:在世界中心贝拿勒斯(在印度北部)的圣庙里,一块黄铜板上插着三根宝石针。印度教的主神梵天在创造世界的时候,在其中一根针上从下到上地穿好了由大到小的64片金片,这就是所谓的汉诺塔。

汉诺塔的传说

法国数学家爱德华·卢卡斯曾编写过一个印度的古老传说:在世界中心贝拿勒斯(在印度北部)的圣庙里,一块黄铜板上插着三根宝石针。印度教的主神梵天在创造世界的时候,在其中一根针上从下到上地穿好了由大到小的64片金片,这就是所谓的汉诺塔。不论白天黑夜,总有一个僧侣在按照下面的法则移动这些金片:一次只移动一片,不管在哪根针上,小片必须在大片上面。僧侣们预言,当所有的金片都从梵天穿好的那根针上移到另外一根针上时,世界就将在一声霹雳中消灭,而梵塔、庙宇和众生也都将同归于尽。

  不管这个传说的可信度有多大,如果考虑一下把64片金片,由一根针上移到另一根针上,并且 始终保持上小下大的顺序
  这需要多少次移动呢?这里需要递归的方法。假设有n片,移动次数是f(n).显然f(1)=1,f(2)=3,f(3)=7,且f(k+1)=2*f(k)+1。此后不难证明 f(n)=2^n-1。n=64时,
假如每秒钟一次,共需多长时间呢?一个平年365天有31536000 秒,闰年366天有31622400秒,平均每年31556952秒,计算一下:
  18446744073709551615秒
  这表明移完这些金片需要 5845.54亿年以上,而地球存在至今不过45亿年,太阳系的预期寿命据说也就是数百亿年。真的过了5845.54亿年,不说太阳系和银河系,至少地球上的一切生命,连同梵塔、庙宇等,都早已经灰飞烟灭。

 

python汉诺塔

#函数的递归算法 汉诺塔游戏
def hanoi(n,x,y,z):
    if n==1:
        print(x,'-->',z)
    else:
        hanoi(n-1,x,z,y)#将前n-1个盘子从x移动到y上
        hanoi(1,x,y,z)#将最底下的最后一个盘子从x移动到z上
        hanoi(n-1,y,x,z)#将y上的n-1个盘子移动到z上
n=int(input('请输入汉诺塔的层数:'))
hanoi(n,'x','y','z')

》请输入汉诺塔的层数:3
x --> z
x --> y
z --> y
x --> z
y --> x
y --> z
x --> z

 

 
目录
相关文章
|
11天前
|
算法 Python
在Python编程中,分治法、贪心算法和动态规划是三种重要的算法。分治法通过将大问题分解为小问题,递归解决后合并结果
在Python编程中,分治法、贪心算法和动态规划是三种重要的算法。分治法通过将大问题分解为小问题,递归解决后合并结果;贪心算法在每一步选择局部最优解,追求全局最优;动态规划通过保存子问题的解,避免重复计算,确保全局最优。这三种算法各具特色,适用于不同类型的问题,合理选择能显著提升编程效率。
28 2
|
1月前
|
Java 程序员 C++
【Python】链式、嵌套调用、递归、函数栈帧、参数默认值和关键字参数
【Python】链式、嵌套调用、递归、函数栈帧、参数默认值和关键字参数
23 0
【Python】链式、嵌套调用、递归、函数栈帧、参数默认值和关键字参数
|
3月前
|
算法 Python
python函数递归和生成器
python函数递归和生成器
|
3月前
|
算法 数据挖掘 Python
|
3月前
|
数据采集 Java Python
python 递归锁、信号量、事件、线程队列、进程池和线程池、回调函数、定时器
python 递归锁、信号量、事件、线程队列、进程池和线程池、回调函数、定时器
|
4月前
|
缓存 Python
Python中递归错误
【7月更文挑战第17天】
50 8
|
4月前
|
算法 Python
python中算法递归错误(Recursion Errors)
【7月更文挑战第18天】
69 1
|
4月前
|
搜索推荐 Python
快速排序:Python 中的速度之王,揭秘它的递归魔法与性能极限!
【7月更文挑战第12天】快速排序**是高效排序算法,基于分治策略。它选择基准值,将数组分成小于和大于基准的两部分,递归地对两部分排序。
61 6
|
4月前
|
存储 缓存 算法
python中递归深度超限(RecursionError)
【7月更文挑战第15天】
119 1
|
5月前
|
分布式计算 算法 Python
Python函数进阶:四大高阶函数、匿名函数、枚举、拉链与递归详解
Python函数进阶:四大高阶函数、匿名函数、枚举、拉链与递归详解