实现斐波拉契数列的四种方式python代码
2024-08-29 22:31:14
斐波那契数列
1. 斐波拉契数列简介
斐波那契数列(Fibonacci sequence),又称黄金分割数列、因数学家列昂纳多·斐波那契(Leonardoda Fibonacci)以兔子繁殖为例子而引入,故又称为“兔子数列”,指的是这样一个数列:1、1、2、3、5、8、13、21、34、……在数学上,斐波纳契数列以如下被以递归的方法定义:F(1)=1,F(2)=1, F(n)=F(n-1)+F(n-2)(n>=2,n∈N*)在现代物理、准晶体结构、化学等领域,斐波纳契数列都有直接的应用,为此,美国数学会从1963年起出版了以《斐波纳契数列季刊》为名的一份数学杂志,用于专门刊载这方面的研究成果。
其实就是从第三项开始,每项的值等于前两项的和。
下面是在面试中常见的问题:青蛙跳台阶
一只青蛙一次可以跳上1级台阶,也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法。
只有一级台阶时,1;
有两节台阶的时候有两种跳法,11和2;
有三节台阶的时候有三种跳法,111、12、21
有四阶台阶的时候,有五种跳法,1111、112、121、22、211
2. 实现斐波拉契数列生成
2.1 使用匿名函数的方式生成
fib = lambda n: n if n <= 2 else fib(n - 1) + fib(n - 2)
通过执行fib(n)
来输出斐波那契数列前n项的值。
也可以通过listData = [fib(i) for i in range(1,n)]
来生成斐波拉契数列前n项的值,最后通过print listData
可以打印出结果。
2.2 利用装饰器的方式生成
def memo(func):
cache = {}
def wrap(*args):
if args not in cache:
cache[args] = func(*args)
return cache[args]
return wrap
@ memo
def fib(i):
if i < 2:
return 1
return fib(i-1) + fib(i-2)
2.3 定义简单的方法来实现
def fib(n):
a, b = 0, 1
for _ in xrange(n):
a, b = b, a + b
return b
2.4 利用迭代器的方式实现(Python3)
class Fib(object):
def __init__(self):
self.prev = 0
self.curr = 1
def __iter__(self):
return self
def __next__(self):
value = self.curr
self.curr += self.prev
self.prev = value
return value
2.5 利用迭代器的方式实现(Python2)
python2需要修改__next__(self)
:方法,其实生成的是一个无限循环的迭代器,也可以使用 itertools模块把无限迭代器转为有限迭代器。
from itertools import islice
class Fib:
def __init__(self):
self.prev = 0
self.curr = 1
def __iter__(self):
return self
def __next__(self):
value = self.curr
self.curr += self.prev
self.prev = value
return value
>>> f = Fib()
>>> list(islice(f, 0, 10))
[1, 1, 2, 3, 5, 8, 13, 21, 34, 55]
最新文章
- JavaScript中的this陷阱的最全收集
- Mongodb常用命令介绍
- MySQL 半同步复制+MMM架构
- Java---类加载机制,构造方法,静态变量,(静态)代码块,父类,变量加载顺序
- UBUNTU添加新的分辨率
- 从NSGA到 NSGA II
- Ubuntu/Deepin下常用软件汇总(持续更新)
- MySQL常用的操作整理
- [JavaEE] Hibernate ORM
- 对于javascript的词法作用域的思考
- 【转】protobuf2.5.0在<;delete [] elements_;>;crash的问题。
- easyui源码翻译1.32--Droppable(放置)
- 2015 Multi-University Training Contest 2
- Hibernate annotation多对多配置
- 大数据算法设计模式(2) - 左外链接(leftOuterJoin) spark实现
- jemalloc 快速上手攻略
- 一起写框架-Ioc内核容器的实现-基础API的定义(三)
- P3396 哈希冲突
- C#利用Vini.cs操作INI文件
- Cartfile学习参考博客
热门文章
- jquery序列化表单以及回调函数的使用
- android Dialog官方demo
- centos单用户 救援 运行级别 yum,单用户模式,救援模式,inittab :启动级别 e2fsck wetty mingetty 物理终端 /dev/console 虚拟终端 /dev/tty(0,6) 模拟终端 /dev/pts/# grub-md5-crypt 给grub加密码 initrd 第二节课
- Atom预览markdown插件Markdown Preview Enhanced
- CAD和GIS绘制图形分析
- 用tsunami-udp加速网络传输
- django基础之FBV与CBV,ajax序列化补充,Form表单
- (android实战)破解apk
- Educational Codeforces Round 54 (Rated for Div. 2) Solution
- ng-深度学习-课程笔记-7: 优化算法(Week2)