MENU

fibonacci 的四种解法-python版

August 27, 2018 • Read: 763 • 算法练习阅读设置

虽然 Fabonacci 不是 LeetCode 中的题,但是也是一道比较经典的题目,好久不看就会忘掉,今天总结一下四种实现 Fibonacci 数列的方法,编程语言为 Python

Fabonacci 公式

$$f(n) = \begin{cases}0,& n = 0; \\ 1,& n = 1; \\ f(n-1) + f(n-2),&n>1.\end{cases}$$

第一种:递归

递归思想最大的优点就是逻辑简单清晰,但是它在 python 中也会引起 递归深度 问题,毕竟递归深度越深对系统资源的占用也越大,很容易导致栈溢出。python 的默认最大递归深度为 1000,修改的方法如下:

import sys
sys.setrecursionlimit(1000000)

所以即使递归思想很重要,也不太提倡使用。

下面为递归解法:

def fibonacci_tool(n):
    #1. 设定递归基线条件
    if n <= 0:
        return 0
    elif n == 1:
        return 1
    #2. 设定递归条件
    else:
        return fibonacci_tool(n - 1) + fibonacci_tool(n - 2)
def fibonacci(n):
    for i in range(1,n+1):
        print(fibonacci_tool(i))

但是有一个问题我们很容易发现,那就是在计算 $f(n) = f(n-1) + f(n-2)$ 的时候,为了计算得到 $f(n)$ 我们每次都要计算之前的所有值,这样造成了极大的资源浪费,最好的解决办法就是循环。

第二种:循环

def fibonacci_(n):
    a = 0
    b = 1
    i = 0
    while i < n:
        print(a)
        a,b = b,a+b
        i += 1

循环对于 fibonacci 而言是一种相对简单的解法,不会出现递归带来的大量资源浪费现象。

第三种:迭代

在使用 递归 方法时由于会出现大量的重复计算(如下图所示),这样的重复计算随着 n 的逐渐增大而急剧增加,造成大量的资源浪费。

                  f(10)
               /        \
            f(9)         f(8)
          /     \       /    \
       f(8)     f(7)  f(7)   f(6)
      /   \     /   \ 
   f(7)  f(6)  f(6) f(5)

但是迭代的思想就是不断地用变量的旧值递推新值的过程。迭代法相对于递归效率要高,因为节省了重复计算。
代码如下:

def fibonacci(n):
    list_fibo = [0,1]
    for i in range(n - 2):
        list_fibo.append(list_fibo[-2] + list_fibo[-1])
    return list_fibo

第四种:矩阵

还有一种方法就是将计算公式转到矩阵运算上来,在 python 中可以利用 numpy 加速矩阵运算,具体的实现方式有点类似求多项式的通项公式,详细如下:

首先:$f(0) = 0;f(1) = 1$;我们将相邻的两项转换成 2x1 的矩阵:

$\begin{bmatrix}f_{n}\\f_{n-1}\end{bmatrix}$ = $\begin{bmatrix}f_{n-1} + f_{n-2}\\f_{n-1}\end{bmatrix}$ = $\begin{bmatrix}1\times f_{n-1} + 1 \times f_{n-2}\\1 \times f_{n-1} + 0 \times f_{n-2}\end{bmatrix}$ = $\begin{bmatrix}1&1\\1&0\end{bmatrix}$ $\times$ $\begin{bmatrix}f_{n-1}\\f_{n-2}\end{bmatrix}$ = $\begin{bmatrix}1&1\\1&0\end{bmatrix}^{n-1} \times \begin{bmatrix}f_{1}\\f_{0}\end{bmatrix}$
= $\begin{bmatrix}1&1\\1&0\end{bmatrix}^{n-1} \times \begin{bmatrix}1\\0\end{bmatrix}$

求F(n)等于求二阶矩阵的n - 1次方,结果取矩阵第一行第一列的元素。

代码如下:

import numpy as np

def fibonacci(n):
    Matrix = np.matrix("1 1;1 0")
    results = []
    for i in range(0,n):
        results.append(np.array(pow(Matrix,i))[0][0])
    return results
Last Modified: January 7, 2019
Archives Tip
QR Code for this page
Tipping QR Code