python 实现fibonacci斐波那契算法

fibonacci斐波那契介绍

斐波那契数列（Fibonacci sequence），又称黄金分割数列，因数学家莱昂纳多·斐波那契（Leonardo Fibonacci）以兔子繁殖为例子而引入，故又称为“兔子数列”，指的是这样一个数列：1、1、2、3、5、8、13、21、34、……这个数列从第3项开始，每一项都等于前两项之和。

斐波那契数列的算法实现有多种方式，下面给出几种常见的实现方法：

1. 递归方法

递归是最直观的解法，但效率很低，因为它重复计算了很多子问题。

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

2. 动态规划方法

使用动态规划可以避免重复计算，提高算法效率。

def fibonacci_dp(n):if n <= 1:return nfib = [0] * (n+1)fib[1] = 1for i in range(2, n+1):fib[i] = fib[i-1] + fib[i-2]return fib[n]

3. 迭代方法

迭代是另一种不使用额外数组空间的动态规划实现方式。

def fibonacci_iterative(n):if n <= 1:return na, b = 0, 1for _ in range(2, n+1):a, b = b, a + breturn b

4. 矩阵快速幂

斐波那契数列也可以使用矩阵快速幂来求解，特别是当n非常大时，这种方法比上述方法都要快。

斐波那契数列可以表示为以下矩阵的幂运算：
$$\left[\begin{array}{c}F(n+1)\\ F(n)\end{array}\right]={\left[\begin{array}{cc}1& 1\\ 1& 0\end{array}\right]}^n\left[\begin{array}{c}F(1)\\ F(0)\end{array}\right]$$

def matrix_multiply(a, b):c = [[0, 0], [0, 0]]for i in range(2):for j in range(2):for k in range(2):c[i][j] += a[i][k] * b[k][j]return cdef fibonacci_matrix_pow(n):if n == 0:return 0F = [[1, 1], [1, 0]]result = [[1, 0], [0, 1]]while n > 0:if n % 2 == 1:result = matrix_multiply(result, F)F = matrix_multiply(F, F)n = n // 2return result[0][0]

以上几种方法各有优缺点，可以根据实际需要选择适合的算法。

fibonacci斐波那契算法python实现样例

可以使用递归或循环的方式来实现Fibonacci斐波那契算法。以下是使用递归方式实现的代码：

def fibonacci_recursive(n):if n <= 0:return 0elif n == 1:return 1else:return fibonacci_recursive(n-1) + fibonacci_recursive(n-2)

下面是使用循环方式实现的代码：

def fibonacci_iterative(n):if n <= 0:return 0a, b = 0, 1for _ in range(n):a, b = b, a + breturn a

可以根据需要选择使用递归或循环的方式来计算Fibonacci数列的第n个元素。以下是示例用法：

n = 10
print(fibonacci_recursive(n))  # 输出：55
print(fibonacci_iterative(n))  # 输出：55