Python基于递归算法实现的汉诺塔与Fibonacci数列示例

yipeiwu_com6年前Python基础

本文实例讲述了Python基于递归算法实现的汉诺塔与Fibonacci数列。分享给大家供大家参考,具体如下:

这里我们通过2个例子,学习python中递归的使用。

1. 找出Fibonacci数列中,下标为 n 的数(下标从0计数)

Fibonacci数列的形式是这样的:0,1,1,2,3,5,8,13……

① 使用while循环,python2代码如下:

def fib(n):
  a,b=0,1
  count=0
  while count<n:
    a,b=b,a+b
    count=count+1
  print a

运行结果如下:

>>> fib(0)
0
>>> fib(1)
1
>>> fib(2)
1
>>> fib(3)
2
>>> fib(4)
3
>>> fib(5)
5

② 使用递归(递归必须要有边界条件),python2代码如下:

def fib(n):
  if n==0 or n==1:#递归的边界条件
    return n
  else:
    return fib(n-1)+fib(n-2)

运行结果如下:

>>> fib(0)
0
>>> fib(1)
1
>>> fib(2)
1
>>> fib(3)
2
>>> fib(4)
3
>>> fib(5)
5

递归是最能表现计算思维的算法之一,我们以f(4)为例,看一下递归的执行过程:

同一程序,使用递归虽然程序简洁,但递归的执行效率要比循环低,系统的资源消耗比循环大。因为递归是一层一层地往里面调用,结束后又一层一层地返回,所以递归的执行效率并不高。那为什么还要使用递归呢?因为有一些问题,我们找不到非常明显的循环方案,但容易找到明显的递归方案。比如说著名的汉诺塔问题。

2. 汉诺塔

下图是一个简化版的汉诺塔游戏,只有4个盘子:

汉诺塔游戏规则如下:

python2代码如下:

def hanoi(a,b,c,n):
  if n==1:#递归结束条件
    print a,'->',c
  else:
    hanoi(a,c,b,n-1)
    print a,'->',c
    hanoi(b,a,c,n-1)

运行结果:

>>> hanoi('A','B','C',1)
A -> C
>>> hanoi('A','B','C',2)
A -> B
A -> C
B -> C
>>> hanoi('A','B','C',3)
A -> C
A -> B
C -> B
A -> C
B -> A
B -> C
A -> C

更多关于Python相关内容感兴趣的读者可查看本站专题:《Python数据结构与算法教程》、《Python函数使用技巧总结》、《Python字符串操作技巧汇总》、《Python入门与进阶经典教程》及《Python文件与目录操作技巧汇总

希望本文所述对大家Python程序设计有所帮助。

相关文章

PyCharm更改字体和界面样式的方法步骤

PyCharm更改字体和界面样式的方法步骤

更改主题 File → Settings → Appearance & Behavior → Appearance → Theme 结果: 更改字体大小 File → Sett...

基于Python中isfile函数和isdir函数使用详解

Python编程语言判断是否是目录 在Python编程语言中可以使用os.path.isdir()函数判断某一路径是否为目录。其函数原型如下所示。 os.path.isdir(pat...

Python实现点云投影到平面显示

值得学习的地方: 1.选择合法索引的方式 2.数组转图像显示 import numpy as np from PIL import Image #input : shape(N,...

python实现监控某个服务 服务崩溃即发送邮件报告

前言:最近我们的升级服务器有点不太稳定,经常崩溃掉。然后客户连接不上,跟我们反馈才知道。所以写这个脚本的目的就是为了比客户提前知道升级服务的运行状况,一旦崩溃掉,就能第一时间登录上去,开...

Django管理员账号和密码忘记的完美解决方法

Django管理员账号和密码忘记的完美解决方法

发现问题 看着Django的教程学习搭建网站,结果忘记第一次创建的账号和密码了。结果搭建成功以后,一直无法登陆到管理页面,进行不下去了。 如图所示: 在网上找了很多的方法都不行,最后使...