斐波那契序列

# 斐波那契数列

斐波那契数列，又称黄金分割数列，因数学家莱昂纳多·斐波那契以兔子繁殖为例引入，故而又称为“兔子数列”。

通俗的说，就是除了第一个和第二个数字外，其他的数字都是起两个数字之和：0,1,1,2,3,5,8,13,21,...

故而可用公式求得：fib(n) = fib(n-1) + fib(n-2) (n>2)

# 第一次尝试

看到了公式，我们可以很快的写出Python函数

def fib1(n: int) -> int:
    if n < 2:
        return n
    return fib1(n-1) + fib1(n-2)


if __name__ == '__main__':
    for i in range(1, 10):
        print(i, fib1(i))

1
2
3
4
5
6
7
8
9
10

看似我们解决了这个问题，但是当尝试调用fib1(40)的时候，就能很明显的察觉出运行速度的缓慢。因此我们需要对上述代码进行优化。

为什么会变慢？我们来调用fib1(4)来看看实际运行：

cnt = 0

def fib1(n: int) -> int:
    global cnt
    cnt += 1
    if n < 2:
        return n
    return fib1(n-1) + fib1(n-2)

if __name__ == '__main__':
    print(fib1(4))
    print(cnt)

1
2
3
4
5
6
7
8
9
10
11
12
13

可以看出，fib(4)就需要调用9次自身函数来使用， fib(5) 需要15次调用，而当到第20个元素的时候，就需要调用21891次，调用次数会随着n的增大而进行的指数型增大。

# 用结果缓存优化

结果缓存是一种缓存技术，即在每次计算任务完成后就把结果保存下来，这样下次需要使用的时候即可直接检索出结果，而不是需要进行重复计算。

memo = {0: 0, 1: 1 }
cnt = 0

def fib2(n: int) -> int:
    global cnt
    cnt += 1
    if n not in memo:
        memo[n] = fib2(n-1) + fib2(n-2)
    return memo[n]

if __name__ == '__main__':
    # print(fib1(4))
    print(fib2(50))
    print(cnt)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

我们发现fib(50)的结果很快就计算出来了，为12586269025，且发现调用次数为99次，大幅度的降低了执行次数。

还有没有可以对该代码进行简化呢？

# 自动化的结果缓存

python有一个自带的内置装饰器，可以为任何函数缓存结果：

from functools import lru_cache

cnt = 0

@lru_cache(maxsize=None)
def fib3(n: int) -> int:
    global cnt
    cnt += 1
    if n < 2:
        return n
    return fib3(n-1) + fib3(n-2)

if __name__ == '__main__':
    # print(fib1(4))
    print(fib3(50))
    print(cnt)

# 结果
# 12586269025
# 51

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

我们发现此时fib3()函数的写法和fib1()的函数体部分是相同的。但是结果会比fib2()的调用次数还少45次

笔记

# lru_cache的实现

我们会好奇lru_cache实现

关于LRU的算法，将在后续进行说明

# 迭代法

def fib4(n: int) -> int:
    if n == 0: return n
    last: int = 0
    next: int =1
    for _ in range(1, n):
        last,next = next, last+next
    return next


if __name__ == '__main__':
    # print(fib1(4))
    print(fib4(50))
    print(cnt)

1
2
3
4
5
6
7
8
9
10
11
12
13

递归解决方案是反向求解，而迭代解决方案是正向求解。递归有时是比较直观的问题，但是也会伴随着巨大的性能损耗。

提示

因此，能用递归方式求解的问题，也能用迭代式来求解。

# 生成器生成

以上的函数只能输出斐波那契序列的单个值，如果要输出某个值之前的整个序列输出呢？

from typing import Generator

def fib5(n: int) -> Generator[int, None, None]:
    print(n)
    yield 0
    if n > 0: yield 1
    last: int = 0
    next: int = 1
    for _ in range(1, n):
        last, next = next, last + next
        yield next


if __name__ == '__main__':
    for i in fib5(50):
        print(i)