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的资料请关注我们其它相关文章!希望大家以后多多支持我们!

时间: 2021-04-14

Python 如何求矩阵的逆

我就废话不多说了,大家还是直接看代码吧~ import numpy as np kernel = np.array([1, 1, 1, 2]).reshape((2, 2)) print(kernel) print(np.linalg.inv(kernel)) 注意,Singular matrix奇异矩阵不可求逆 补充:python+numpy中矩阵的逆和伪逆的区别 定义: 对于矩阵A,如果存在一个矩阵B,使得AB=BA=E,其中E为与A,B同维数的单位阵,就称A为可逆矩阵(或者称A可逆),并称

Python numpy大矩阵运算内存不足如何解决

程序运行,产生如下结果,然后进程终止,导致这一结果的原因很有可能是内存爆炸. 当两个较大的 (e.g., 10000*10000 维)ndarray 做运算(加法,or 乘法)时,很容易出现这样的结果. 解决办法: 大多数情况下,这种大矩阵都是稀疏的.尽可能地利用稀疏计算的方式,例如稀疏矩阵,或者只计算非 0 位置的值. 如果都是整数运算,可以设置 dtype=int,而非 dtype=float, 可以省下不少空间. linux 系统下,使用 top 命令,可以很容易地看到内存(%MEM) 的

Python:合并两个numpy矩阵的实现

numpy是Python用来科学计算的一个非常重要的库,numpy主要用来处理一些矩阵对象,可以说numpy让Python有了Matlab的味道. 如何利用numpy来合并两个矩阵呢?我们可以利用numpy向我们提供的两个函数来进行操作. #hstack()在行上合并 np.hstack((a,b)) #vstack()在列上合并 np.vstack((a,b)) 以上a,b分别为两个numpy矩阵.hstack在行上合并,vstack在列上合并. 这篇Python:合并两个numpy矩阵的实现

python实现由数组生成对称矩阵

在实际应用中,经常会遇上这样的小需求:根据一段给定的数组,生成由这一段数组值构成的对称矩阵. 例如,给定数组[1,2,3,4,5,6,7,8,9,10],要求生成如下的矩阵: [[0,1,2,3,4], [1,0,5,6,7], [2,5,0,8,9], [3,6,8,0,10], [4,7,9,10,0]] 其中,对角元全为0,该类型的矩阵完全由给定的数组决定. 笔者给出实现以上功能的一种python参考代码如下: def semi_to_full(m): import numpy as np

python用分数表示矩阵的方法实例

前言 在机器学习中,我们会经常和矩阵打交道.在矩阵的运算中,python默认的输出是浮点数,但是如果我们想要矩阵的元素以分数的形式显示,可以通过添加一行代码来实现. 1.函数及参数解释 set_printoptions()--控制输出方式 formatter--通用格式化输出 Fraction(x).limit_denominator(y)--返回一个分母不大于y且最接近x的分数 2.代码实现 from fractions import Fraction import numpy as np #

python 如何将两个实数矩阵合并为一个复数矩阵

问题描述: 有时需要把两个实数矩阵,一个作为实部,一个作为虚部,合并为一个复数矩阵,该如何操作? 解决办法: 假如是在第二个维度上进行合并(real: Data[:, 0, :, :] imag: Data[:, 1, :, :]),有两种方法 第一种. result = Data[:, 0, :, :] + 1j*Data[:, 1, :, :] 第二种. result = 1j*Data[:, 1, :, :] result += Data[:, 0, :, :] 第二种方法更节省内存~ 补

Python计算矩阵的和积的实例详解

python的numpy库提供矩阵运算的功能,因此我们在需要矩阵运算的时候,需要导入numpy的包. 一.numpy的导入和使用 from numpy import *;#导入numpy的库函数 import numpy as np; #这个方式使用numpy的函数时,需要以np.开头. 二.矩阵的创建 由一维或二维数据创建矩阵 from numpy import *; a1=array([1,2,3]); a1=mat(a1); 创建常见的矩阵 data1=mat(zeros((3,3)));

对python中矩阵相加函数sum()的使用详解

假如矩阵A是n*n的矩阵 A.sum()是计算矩阵A的每一个元素之和. A.sum(axis=0)是计算矩阵每一列元素相加之和. A.Sum(axis=1)是计算矩阵的每一行元素相加之和. 以上这篇对python中矩阵相加函数sum()的使用详解就是小编分享给大家的全部内容了,希望能给大家一个参考,也希望大家多多支持我们.

对python:循环定义多个变量的实例详解

我们可能会时长碰到这样一个场景,计算得到一个非固定值,需要根据这个值定义相同数量个变量. 实现方式的核心是exec函数,exec函数可以执行我们输入的代码字符串. exec函数的简单例子: >>>exec ('print "hello world"') hello world 可以很清晰的看到,我们给exec传入一个字符串'print "hello world"',exec是执行字符串里面的代码print "hello world&quo

对python while循环和双重循环的实例详解

废话不多说,直接上代码吧! #python中,while语句用于循环执行程序,即在某个条件下,循环执行某段程序,以处理需要重复处理的相同任务. #while是"当型"循环结构. i=1 while i<=20: print(i,end=" ") i+=1 sum=0 i=1 while i<=100: sum+=i i+=1 else: print("\n",sum) print("0+2+...+100=",su

Python中常用的高阶函数实例详解

前言 高阶函数指的是能接收函数作为参数的函数或类:python中有一些内置的高阶函数,在某些场合使用可以提高代码的效率. lambda 当在使用一些函数的时候,我们不需要显式定义函数名称,直接传入lambda匿名函数即可.lambda匿名函数通常和其他函数搭配使用. 比如可以直接使用如下的lambda表达式计算当x=3时,y = x * 3 + 5的函数值. In [1]: (lambda x: x * 3 + 5)(3) Out[1]: 14 map map函数将一个函数和序列/迭代器(可以传

python里使用正则表达式的组嵌套实例详解

python里使用正则表达式的组嵌套实例详解 由于组本身是一个完整的正则表达式,所以可以将组嵌套在其他组中,以构建更复杂的表达式.下面的例子,就是进行组嵌套的例子: #python 3.6 #蔡军生 #http://blog.csdn.net/caimouse/article/details/51749579 # import re def test_patterns(text, patterns): """Given source text and a list of pa

python 读取excel文件生成sql文件实例详解

python 读取excel文件生成sql文件实例详解 学了python这么久,总算是在工作中用到一次.这次是为了从excel文件中读取数据然后写入到数据库中.这个逻辑用java来写的话就太重了,所以这次考虑通过python脚本来实现. 在此之前需要给python添加一个xlrd模块,这个模块是专门用来操作excel文件的. 在mac中可以通过easy_install xlrd命令实现自动安装模块 import xdrlib ,sys import xlrd def open_excel(fil

python文件特定行插入和替换实例详解

python文件特定行插入和替换实例详解 python提供了read,write,但和很多语言类似似乎没有提供insert.当然真要提供的话,肯定是可以实现的,但可能引入insert会带来很多其他问题,比如在插入过程中crash掉可能会导致后面的内容没来得及写回. 不过用fileinput可以简单实现在特定行插入的需求: Python代码 import os import fileinput def file_insert(fname,linenos=[],strings=[]): ""

Python字符串和字典相关操作的实例详解

Python字符串和字典相关操作的实例详解 字符串操作: 字符串的 % 格式化操作: str = "Hello,%s.%s enough for ya ?" values = ('world','hot') print str % values 输出结果: Hello,world.hot enough for ya ? 模板字符串: #coding=utf-8 from string import Template ## 单个变量替换 s1 = Template('$x, glorio

Python基础教程之浅拷贝和深拷贝实例详解

Python基础教程之浅拷贝和深拷贝实例详解            网上关于Python的深拷贝和浅拷贝的文章很多,这里对三种拷贝进行比较并附实例,大家可以参考下 一般的复制 #encoding:utf-8 #定义一个嵌套集合 lista=[1,2,3,[4,5,6,[7,8,9]]] listb=lista #分别打印出 lista和listb的地址值 print id(lista) #4511103096 print id(listb) #4511103096 #修改lista中的内容,li