Python基于递归算法实现的汉诺塔与Fibonacci数列示例
作者:快递小可 时间:2021-07-01 15:57:12
本文实例讲述了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程序设计有所帮助。
来源:https://blog.csdn.net/sxingming/article/details/51306784
![](/images/zang.png)
![](/images/jiucuo.png)
猜你喜欢
Python Scrapy图片爬取原理及代码实例
CSS Sprites
pytorch显存一直变大的解决方案
Oracle的数据字典技术简析
Python计算素数个数的两种方法
![](https://img.aspxhome.com/file/2023/8/78508_0s.gif)
Python web如何在IIS发布应用过程解析
关于VSCode 配置使用 PyLint 语法检查器的问题
![](https://img.aspxhome.com/file/2023/0/61430_0s.png)
下一站:HandlerSocket!
PHP实现数组根据某个字段进行水平合并,横向合并案例分析
python os模块在系统管理中的应用
python PyTorch参数初始化和Finetune
![](https://img.aspxhome.com/file/2023/4/75934_0s.png)
ASP 循环导入导出数据处理 不使用缓存
asp截取字符串的两种应用
ASP处理XSLT转换XML的实现
Python字典中的值为列表或字典的构造实例
python中web框架的自定义创建
Firefox 下 innerHTML 的一个 BUG
基于PHP+Ajax实现表单验证的详解
Python真题案例之二分法查找详解
![](https://img.aspxhome.com/file/2023/6/85376_0s.png)
利用Python上传日志并监控告警的方法详解
![](https://img.aspxhome.com/file/2023/7/69477_0s.png)