Python 斐波那契数列的几种实现

先说下，什么是斐波那契数列？

斐波那契（Fibonacci）数列，又称黄金分割数列，因数学家列昂纳多·斐波那契（Leonardo Fibonacci）以兔子繁殖为例子而引入，故又称为“兔子数列”，指的是这样一个数列：
1、1、2、3、5、8、13、21、34……

简单来讲就是：数列中某一项的值，等于它的前一项加上前前一项的和。

1. 递归

在编程教程中提到斐波那契数列，通常都是用来讲解递归函数。当一个关于 N 的问题可以转换为关于 N - k 的同样问题时，它就可以尝试用递归的思路来解决。

def fib_1(n):
  if n <= 1:
      return 1
  return fib_1(n-1) + fib_1(n-2)

for i in range(20):
    print(fib_1(i), end=' ')

2. 循环

但斐波那契并非一定要用递归实现。事实上，所有递归都可以用循环来实现

def fib_2(n):
    a, b = 0, 1
    for i in range(n):
        print(b, end=' ')

        a, b = b, a + b

fib_2(20)

3.生成器

用生成器的思路本质来说和上面的循环一样的，只是实现的时候用 yield

def fib_3(n):
    a, b = 0, 1
    while n > 0:
        yield b
        a, b = b, a + b
        n -= 1

for i in fib_3(20):
    print(i, end=' ')

4. 矩阵相乘

此方法的原理是利用二阶矩阵的相乘：

image.png

import numpy as np

def fib_4(n):
    for i in range(n):
        res = pow(np.matrix([[1, 1], [1, 0]], dtype='int64'), i) * np.matrix([[1], [0]])
        print(int(res[0][0]), end=' ')

fib_4(20)

上述 4 种方法的输出结果都是：
1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597 2584 4181 6765

斐波那契数列的实现方法并不仅这 4 种。如果你有其他的实现，欢迎在留言中补充。

看完记得点赞哦，笔芯