【2019.06.13】python 实现斐波那契数列的几种方式

女爷i 2022-01-15 13:59 90阅读 0赞

# 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 使用匿名函数 lambda 方式生成 ##

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可以打印出结果。

![9635b5851a11180632eaa7b64d2d7851.png][]

## 2.2 利用装饰器的方式生成 ##

def memo(func):
        cache = {}
        def wrap(*args):
            if args not in cache:
                cache[args] = func(*args)
            return cache[args]
        return wrap
    
    
    @ memodef 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

[9635b5851a11180632eaa7b64d2d7851.png]: