Python 实现斐波那契数列方法及其优化总结

斐波那契数列的相关题目是面试常见的，所以我看了些资料总结记录一下这些小的知识点。

1. 元组实现

代码：

fibs = [0, 1]
for i in range(8):
    fibs.append(fibs[-2] + fibs[-1])
print(fibs)

输出：

[0, 1, 1, 2, 3, 5, 8, 13, 21, 34]

2. 迭代器实现

class Fibs:
    def __init__(self):
        self.a = 0
        self.b = 1

    def next(self):
        self.a, self.b = self.b, self.a + self.b
        return self.a

    def __iter__(self):
        return self

这将得到一个无穷的数列， 可以采用如下方式访问：

fibs = Fibs()
for f in fibs:
    if f > 1000:
        print(f)
        break
    else:
        print(f)

3. 通过定制类实现

class Fib(object):
    def __getitem__(self, n):
        if isinstance(n, int):
            a, b = 1, 1
            for x in range(n):
                a, b = b, a + b
            return a
        elif isinstance(n, slice):
            start = n.start
            stop = n.stop
            a, b = 1, 1
            L = []
            for x in range(stop):
                if x >= start:
                    L.append(a)
                a, b = b, a + b
            return L
        else:
            raise TypeError("Fib indices must be integers")

这样可以得到一个类似于序列的数据结构，可以通过下标来访问数据：

f = Fib()
print (f[0:10])

4.Python实现比较简易的斐波那契数列示例

i, j = 0, 1
while i < 10000:
 print( i,j, = j, i+j)

最后展示运行结果：

0 1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597 2584 4181 6765

5.列表生成式实现

def fib(n):
    if n == 1 or n == 0:
        return 1
    else:
        return fib(n - 2) + fib(n - 1)
print([fib(n) for n in range(10)])

这个计算斐波那契数列前n项很简单，但是从下面的图可以看出这个计算花费的时间较多因为会重复计算很多值。

Paste_Image.png
这个时候我需要修改一下，加入缓存机制。

def fib(n, cache=None):
    if cache is None:
        cache = {}
    if n in cache:
        return cache[n]
    if n == 1 or n == 0:
        return 1
    else:
        cache[n] = fib(n - 2, cache) + fib(n - 1, cache)
        return cache[n]
print([fib(n) for n in range(999)])

这样即使是n的值很大也能很快的计算很出来。