使用Python实现求解斐波那契数列第n项的多种求法
- 后端
- 猿友
- 0
斐波那契数列作为一个非常经典的数学问题，在我们学习编程语言递归思想的时候，这个问题经常被拿来应用。下面我将为大家介绍使用Python求解斐波那契数列第n项的多种算法。
斐波那契数列
首先我们来定义一下斐波那契数列：
即数列的第0项：
算法一：递归
递归计算的节点个数是O(2ⁿ)的级别的，效率很低，存在大量的重复计算。
比如：
f(10) = f(9) + f(8)
f(9) = f(8) + f(7) 重复 8
f(8) = f(7) + f(6) 重复 7
时间复杂度是O(2ⁿ),极慢
def F1(n):
if n <= 1: return max(n, 0) # 前两项
return F1(n-1)+F1(n-2) # 递归算法二：记忆化搜索
开一个大数组记录中间结果，如果一个状态被计算过，则直接查表，否则再递归计算。
总共有 n 个状态，计算每个状态的复杂度是 O(1)，所以时间复杂度是 O(n)。但由于是递归计算，递归层数太多会爆栈。
res = [None]*100000
def F2(n):
if n <= 1: return max(n, 0)
if res[n]: return res[n] # 如果已存在则直接查找返回结果
res[n] = F2(n-1)+F2(n-2) # 不存在则计算
return res[n]
算法三：递推
开一个大数组，记录每个数的值。用循环递推计算。
总共计算 n 个状态，所以时间复杂度是 O(n)。但需要开一个长度是 n 的数组，内存将成为瓶颈。
def F3(n):
if n <= 1: return max(n, 0)
res = [0, 1]
for i in range(2,n+1):
res.append(res[i-1]+res[i-2])
return res[n]
算法四：递归+滚动变量
比较优秀的一种解法。仔细观察我们会发现，递推时我们只需要记录前两项的值即可，没有必要记录所有值，所以我们可以用滚动变量递推。
时间复杂度还是 O(n)，但空间复杂度变成了O(1)。
def F4(n):
if n <= 1: return max(n, 0)
fn, f0, f1 = 0, 1, 0 # fn为最终结果，f0为第0项，f1为第一项，
for i in range(2, n+1):
fn = f0 + f1 # 前两项和
f0, f1 = f1, fn # 递推变量
return fn
算法五：矩阵乘法+快速幂
利用矩阵运算的性质将通项公式变成幂次形式，然后用平方倍增（快速幂）的方法求解第 n 项。
先说通式：
利用数学归纳法证明：
这里的a0,a1,a2是对应斐波那契的第几项
证毕。
所以我们想要的得到An，只需要求得Aⁿ，然后取第一行第二个元素即可。
如果只是简单的从0开始循环求n次方，时间复杂度仍然是O(n)，并不比前面的快。我们可以考虑乘方的如下性质，即快速幂：
这样只需要 logn 次运算即可得到结果，时间复杂度为 O(logn)
def mul(a, b): # 首先定义二阶矩阵乘法运算
c = [[0, 0], [0, 0]] # 定义一个空的二阶矩阵，存储结果
for i in range(2): # row
for j in range(2): # col
for k in range(2): # 新二阶矩阵的值计算
c[i][j] += a[i][k] * b[k][j]
return c
def F5(n):
if n <= 1: return max(n, 0)
res = [[1, 0], [0, 1]] # 单位矩阵，等价于1
A = [[1, 1], [1, 0]] # A矩阵
while n:
if n & 1: res = mul(res, A) # 如果n是奇数，或者直到n=1停止条件
A = mul(A, A) # 快速幂
n >>= 1 # 整除2，向下取整
return res[0][1]总的来说，按照文章看下来操作一遍会发现解斐波那契数列问题其实也不是很难，难得是自己独立写的时候是否有那种编程思维。本篇文章供大家学习参考，想要了解更多关于 Python 其他资料请关注W3Cschool其它相关文章！希望大家以后多多支持我们！
免责申明：本站发布的内容（图片、视频和文字）以转载和分享为主，文章观点不代表本站立场，如涉及侵权请联系站长邮箱：xbc-online@qq.com进行反馈，一经查实，将立刻删除涉嫌侵权内容。
