Python学习手册

Python实现-斐波那契数列（6种方法）

2020-02-21  本文已影响0人  复苏的兵马俑

斐波那契数列（Fibonacci sequence），又称黄金分割数列，因数学家列昂纳多·斐波那契（Leonardoda Fibonacci）以兔子繁殖为例子而引入，故又称为“兔子数列”，指的是这样一个数列：1、1、2、3、5、8、13、21、34、……在数学上，斐波纳契数列以如下被以递归的方法定义：F(1)=1，F(2)=1, F(n)=F(n-1)+F(n-2)（n>=2，n∈N*）。




斐波那契数列，难点在于算法，还有如果变成生成器generator，就要用for循环去遍历可迭代的generator。
问题1：通过Python代码实现获取第n个斐波那契数列的值。
问题2：通过Python代码实现获取n个元素的斐波那契数列。

实现1（递归法）：
问题1：

def fib(n):
    if n == 1 or n == 2:
        return 1
    return fib(n - 1) + fib(n - 2)

while 1:
    num = input('请输入要获取斐波那契数列的第几个数字：')
    if num.upper() == 'Q':
        print('程序结束！')
        break
    elif int(num) <= 0:
        print('输入错误，请重新输入！')
    else:
        num = int(num)
        print('斐波那契数列的第{}个数字是{}'.format(num,fib(num)))

运行结果：

请输入要获取斐波那契数列的第几个数字：0
输入错误，请重新输入！
请输入要获取斐波那契数列的第几个数字：-1
输入错误，请重新输入！
请输入要获取斐波那契数列的第几个数字：1
斐波那契数列的第1个数字是1
请输入要获取斐波那契数列的第几个数字：2
斐波那契数列的第2个数字是1
请输入要获取斐波那契数列的第几个数字：3
斐波那契数列的第3个数字是2
请输入要获取斐波那契数列的第几个数字：4
斐波那契数列的第4个数字是3
请输入要获取斐波那契数列的第几个数字：5
斐波那契数列的第5个数字是5
请输入要获取斐波那契数列的第几个数字：q
程序结束！

问题2：

def fib(n):
    if n == 1 or n == 2:
        return 1
    return fib(n - 1) + fib(n - 2)

while 1:
    num = input('请输入要获取多少个元素的斐波那契数列（n >= 2）：')
    if num.upper() == 'Q':
        print('程序结束！')
        break
    elif int(num) < 2:
        print('输入错误，请重新输入！')
    else:
        num = int(num)
        lst = []
        for i in range(1,num+1):
            lst.append(fib(i))
        print('生成的斐波那契数列是{}'.format(lst))

运行结果：

请输入要获取多少个元素的斐波那契数列（n >= 2）：1
输入错误，请重新输入！
请输入要获取多少个元素的斐波那契数列（n >= 2）：-1
输入错误，请重新输入！
请输入要获取多少个元素的斐波那契数列（n >= 2）：2
生成的斐波那契数列是[1, 1]
请输入要获取多少个元素的斐波那契数列（n >= 2）：10
生成的斐波那契数列是[1, 1, 2, 3, 5, 8, 13, 21, 34, 55]
请输入要获取多少个元素的斐波那契数列（n >= 2）：20
生成的斐波那契数列是[1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765]
请输入要获取多少个元素的斐波那契数列（n >= 2）：q
程序结束！

如上递归法写法最简洁，采用了双递归调用，但是效率最低，会出现大量的重复计算，时间复杂度O(1.618^n)，而且最深度是1000。

实现2（递归改进法）：
问题1：

def fib(n,lst = [0]):
    lst[0] += 1
    if n == 2 and lst[0] == 1 or n == 1:
        lst[0] -= 1
        return 1
    elif n == 2:
        lst[0] -= 1
        return 1,1
    else:
        a,b = fib(n -1)
        lst[0] -= 1
        if lst[0] == 0:
            return a + b
        return b,a + b

while 1:
    num = input('请输入要获取斐波那契数列的第几个数字（n >= 2）：')
    if num.upper() == 'Q':
        print('程序结束！')
        break
    elif int(num) < 1:
        print('输入错误，请重新输入！')
    else:
        num = int(num)
        print('斐波那契数列的第{}个数字是{}'.format(num,fib(num)))

运行结果：

请输入要获取斐波那契数列的第几个数字（n >= 2）：1
输入错误，请重新输入！
请输入要获取斐波那契数列的第几个数字（n >= 2）：2
斐波那契数列的第2个数字是1
请输入要获取斐波那契数列的第几个数字（n >= 2）：3
斐波那契数列的第3个数字是2
请输入要获取斐波那契数列的第几个数字（n >= 2）：4
斐波那契数列的第4个数字是3
请输入要获取斐波那契数列的第几个数字（n >= 2）：5
斐波那契数列的第5个数字是5
请输入要获取斐波那契数列的第几个数字（n >= 2）：6
斐波那契数列的第6个数字是8
请输入要获取斐波那契数列的第几个数字（n >= 2）：50
斐波那契数列的第50个数字是12586269025
请输入要获取斐波那契数列的第几个数字（n >= 2）：q
程序结束！

问题2：

def fib(n,lst = [0]):
    lst[0] += 1
    if n == 2 and lst[0] == 1 or n == 1:
        lst[0] -= 1
        return 1
    elif n == 2:
        lst[0] -= 1
        return 1,1
    else:
        a,b = fib(n -1)
        lst[0] -= 1
        if lst[0] == 0:
            return a + b
        return b,a + b

while 1:
    num = input('请输入要获取多少个元素的斐波那契数列（n >= 2）：')
    if num.upper() == 'Q':
        print('程序结束！')
        break
    elif int(num) < 2:
        print('输入错误，请重新输入！')
    else:
        num = int(num)
        lst = []
        for i in range(1,num+1):
            lst.append(fib(i))
        print('生成的斐波那契数列是{}'.format(lst))

运行结果：

请输入要获取多少个元素的斐波那契数列（n >= 2）：1
输入错误，请重新输入！
请输入要获取多少个元素的斐波那契数列（n >= 2）：2
生成的斐波那契数列是[1, 1]
请输入要获取多少个元素的斐波那契数列（n >= 2）：10
生成的斐波那契数列是[1, 1, 2, 3, 5, 8, 13, 21, 34, 55]
请输入要获取多少个元素的斐波那契数列（n >= 2）：20
生成的斐波那契数列是[1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765]
请输入要获取多少个元素的斐波那契数列（n >= 2）：50
生成的斐波那契数列是[1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, 10946, 17711, 28657, 46368, 75025, 121393, 196418, 317811, 514229, 832040, 1346269, 2178309, 3524578, 5702887, 9227465, 14930352, 24157817, 39088169, 63245986, 102334155, 165580141, 267914296, 433494437, 701408733, 1134903170, 1836311903, 2971215073, 4807526976, 7778742049, 12586269025]
请输入要获取多少个元素的斐波那契数列（n >= 2）：q
程序结束！

递归改进法，就是将双递归调用改进成单递归调用，时间复杂度是 O(n)，呈线性增长，如果数据量巨大，速度会越拖越慢。

实现3（递推法）：
问题1：

def fib(n):
    a, b = 0, 1
    for i in range(n):
        a, b = b, a + b
    return a

while 1:
    num = input('请输入要获取斐波那契数列的第几个数字（n >= 2）：')
    if num.upper() == 'Q':
        print('程序结束！')
        break
    elif int(num) < 2:
        print('输入错误，请重新输入！')
    else:
        num = int(num)
        print('斐波那契数列的第{}个数字是{}'.format(num,fib(num)))

运行结果

请输入要获取斐波那契数列的第几个数字（n >= 2）：1
输入错误，请重新输入！
请输入要获取斐波那契数列的第几个数字（n >= 2）：2
斐波那契数列的第2个数字是1
请输入要获取斐波那契数列的第几个数字（n >= 2）：3
斐波那契数列的第3个数字是2
请输入要获取斐波那契数列的第几个数字（n >= 2）：4
斐波那契数列的第4个数字是3
请输入要获取斐波那契数列的第几个数字（n >= 2）：5
斐波那契数列的第5个数字是5
请输入要获取斐波那契数列的第几个数字（n >= 2）：6
斐波那契数列的第6个数字是8
请输入要获取斐波那契数列的第几个数字（n >= 2）：q
程序结束！

问题2：

def fib(n):
    a, b = 0, 1
    for i in range(n):
        a, b = b, a + b
    return a

while 1:
    num = input('请输入要获取多少个元素的斐波那契数列（n >= 2）：')
    if num.upper() == 'Q':
        print('程序结束！')
        break
    elif int(num) < 2:
        print('输入错误，请重新输入！')
    else:
        num = int(num)
        lst = []
        for i in range(1,num+1):
            lst.append(fib(i))
        print('生成的斐波那契数列是{}'.format(lst))

运行结果

请输入要获取多少个元素的斐波那契数列（n >= 2）：1
输入错误，请重新输入！
请输入要获取多少个元素的斐波那契数列（n >= 2）：2
生成的斐波那契数列是[1, 1]
请输入要获取多少个元素的斐波那契数列（n >= 2）：3
生成的斐波那契数列是[1, 1, 2]
请输入要获取多少个元素的斐波那契数列（n >= 2）：10
生成的斐波那契数列是[1, 1, 2, 3, 5, 8, 13, 21, 34, 55]
请输入要获取多少个元素的斐波那契数列（n >= 2）：20
生成的斐波那契数列是[1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765]
请输入要获取多少个元素的斐波那契数列（n >= 2）：50
生成的斐波那契数列是[1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, 10946, 17711, 28657, 46368, 75025, 121393, 196418, 317811, 514229, 832040, 1346269, 2178309, 3524578, 5702887, 9227465, 14930352, 24157817, 39088169, 63245986, 102334155, 165580141, 267914296, 433494437, 701408733, 1134903170, 1836311903, 2971215073, 4807526976, 7778742049, 12586269025]
请输入要获取多少个元素的斐波那契数列（n >= 2）：q
程序结束！

递推法，就是递增法，时间复杂度是 O(n)，呈线性增长，如果数据量巨大，速度会越拖越慢。
实现4（生成器）：
问题1：

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

while 1:
    num = input('请输入要获取斐波那契数列的第几个数字（n >= 2）：')
    if num.upper() == 'Q':
        print('程序结束！')
        break
    elif int(num) < 2:
        print('输入错误，请重新输入！')
    else:
        num = int(num)
        for i in fib(num):
            continue
        print('斐波那契数列的第{}个数字是{}'.format(num,i))

运行结果

请输入要获取斐波那契数列的第几个数字（n >= 2）：1
输入错误，请重新输入！
请输入要获取斐波那契数列的第几个数字（n >= 2）：2
斐波那契数列的第2个数字是1
请输入要获取斐波那契数列的第几个数字（n >= 2）：3
斐波那契数列的第3个数字是2
请输入要获取斐波那契数列的第几个数字（n >= 2）：4
斐波那契数列的第4个数字是3
请输入要获取斐波那契数列的第几个数字（n >= 2）：5
斐波那契数列的第5个数字是5
请输入要获取斐波那契数列的第几个数字（n >= 2）：6
斐波那契数列的第6个数字是8
请输入要获取斐波那契数列的第几个数字（n >= 2）：q
程序结束！

问题2：

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

while 1:
    num = input('请输入要获取多少个元素的斐波那契数列（n >= 2）：')
    if num.upper() == 'Q':
        print('程序结束！')
        break
    elif int(num) < 2:
        print('输入错误，请重新输入！')
    else:
        num = int(num)
        lst = []
        for i in fib(num):
            lst.append(i)
        print('生成的斐波那契数列是{}'.format(lst))

运行结果

请输入要获取多少个元素的斐波那契数列（n >= 2）：1
输入错误，请重新输入！
请输入要获取多少个元素的斐波那契数列（n >= 2）：2
生成的斐波那契数列是[1, 1]
请输入要获取多少个元素的斐波那契数列（n >= 2）：3
生成的斐波那契数列是[1, 1, 2]
请输入要获取多少个元素的斐波那契数列（n >= 2）：4
生成的斐波那契数列是[1, 1, 2, 3]
请输入要获取多少个元素的斐波那契数列（n >= 2）：5
生成的斐波那契数列是[1, 1, 2, 3, 5]
请输入要获取多少个元素的斐波那契数列（n >= 2）：10
生成的斐波那契数列是[1, 1, 2, 3, 5, 8, 13, 21, 34, 55]
请输入要获取多少个元素的斐波那契数列（n >= 2）：20
生成的斐波那契数列是[1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765]
请输入要获取多少个元素的斐波那契数列（n >= 2）：50
生成的斐波那契数列是[1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, 10946, 17711, 28657, 46368, 75025, 121393, 196418, 317811, 514229, 832040, 1346269, 2178309, 3524578, 5702887, 9227465, 14930352, 24157817, 39088169, 63245986, 102334155, 165580141, 267914296, 433494437, 701408733, 1134903170, 1836311903, 2971215073, 4807526976, 7778742049, 12586269025]
请输入要获取多少个元素的斐波那契数列（n >= 2）：q
程序结束！

带有yield的函数都被看成生成器，生成器是可迭代对象，且具备__iter__ 和 __next__方法， 可以遍历获取元素。
python要求迭代器本身也是可迭代的，所以我们还要为迭代器实现__iter__方法，而__iter__方法要返回一个迭代器，迭代器自身正是一个迭代器，所以迭代器的__iter__方法返回自身即可。
实现5（类实现内部魔法方法）：
问题1：

class fib(object):
    """斐波那契数列迭代器"""

    def __init__(self, n):
        """
        :param n:int 指 生成数列的个数
        """
        self.n = n
        # 保存当前生成到的数据列的第几个数据，生成器中性质，记录位置，下一个位置的数据
        self.current = 0
        # 两个初始值
        self.a = 0
        self.b = 1

    def __next__(self):
        """当使用next()函数调用时，就会获取下一个数"""
        if self.current < self.n:
            self.a, self.b = self.b, self.a + self.b
            self.current += 1
            return self.a
        else:
            raise StopIteration

    def __iter__(self):
        """迭代器的__iter__ 返回自身即可"""
        return self

while 1:
    num = input('请输入要获取斐波那契数列的第几个数字（n >= 2）：')
    if num.upper() == 'Q':
        print('程序结束！')
        break
    elif int(num) < 2:
        print('输入错误，请重新输入！')
    else:
        num = int(num)
        if __name__ == '__main__':
            for i in fib(num):
                continue
            print('斐波那契数列的第{}个数字是{}'.format(num, i))

运行结果

请输入要获取斐波那契数列的第几个数字（n >= 2）：1
输入错误，请重新输入！
请输入要获取斐波那契数列的第几个数字（n >= 2）：2
斐波那契数列的第2个数字是1
请输入要获取斐波那契数列的第几个数字（n >= 2）：3
斐波那契数列的第3个数字是2
请输入要获取斐波那契数列的第几个数字（n >= 2）：4
斐波那契数列的第4个数字是3
请输入要获取斐波那契数列的第几个数字（n >= 2）：5
斐波那契数列的第5个数字是5
请输入要获取斐波那契数列的第几个数字（n >= 2）：6
斐波那契数列的第6个数字是8
请输入要获取斐波那契数列的第几个数字（n >= 2）：10
斐波那契数列的第10个数字是55
请输入要获取斐波那契数列的第几个数字（n >= 2）：20
斐波那契数列的第20个数字是6765
请输入要获取斐波那契数列的第几个数字（n >= 2）：50
斐波那契数列的第50个数字是12586269025
请输入要获取斐波那契数列的第几个数字（n >= 2）：q
程序结束！

问题2：

class fib(object):
    """斐波那契数列迭代器"""

    def __init__(self, n):
        """
        :param n:int 指 生成数列的个数
        """
        self.n = n
        # 保存当前生成到的数据列的第几个数据，生成器中性质，记录位置，下一个位置的数据
        self.current = 0
        # 两个初始值
        self.a = 0
        self.b = 1

    def __next__(self):
        """当使用next()函数调用时，就会获取下一个数"""
        if self.current < self.n:
            self.a, self.b = self.b, self.a + self.b
            self.current += 1
            return self.a
        else:
            raise StopIteration

    def __iter__(self):
        """迭代器的__iter__ 返回自身即可"""
        return self

while 1:
    num = input('请输入要获取多少个元素的斐波那契数列（n >= 2）：')
    if num.upper() == 'Q':
        print('程序结束！')
        break
    elif int(num) < 2:
        print('输入错误，请重新输入！')
    else:
        num = int(num)
        lst = []
        for i in fib(num):
            lst.append(i)
        print('生成的斐波那契数列是{}'.format(lst))

运行结果

请输入要获取多少个元素的斐波那契数列（n >= 2）：1
输入错误，请重新输入！
请输入要获取多少个元素的斐波那契数列（n >= 2）：2
生成的斐波那契数列是[1, 1]
请输入要获取多少个元素的斐波那契数列（n >= 2）：3
生成的斐波那契数列是[1, 1, 2]
请输入要获取多少个元素的斐波那契数列（n >= 2）：4
生成的斐波那契数列是[1, 1, 2, 3]
请输入要获取多少个元素的斐波那契数列（n >= 2）：5
生成的斐波那契数列是[1, 1, 2, 3, 5]
请输入要获取多少个元素的斐波那契数列（n >= 2）：6
生成的斐波那契数列是[1, 1, 2, 3, 5, 8]
请输入要获取多少个元素的斐波那契数列（n >= 2）：10
生成的斐波那契数列是[1, 1, 2, 3, 5, 8, 13, 21, 34, 55]
请输入要获取多少个元素的斐波那契数列（n >= 2）：20
生成的斐波那契数列是[1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765]
请输入要获取多少个元素的斐波那契数列（n >= 2）：50
生成的斐波那契数列是[1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, 10946, 17711, 28657, 46368, 75025, 121393, 196418, 317811, 514229, 832040, 1346269, 2178309, 3524578, 5702887, 9227465, 14930352, 24157817, 39088169, 63245986, 102334155, 165580141, 267914296, 433494437, 701408733, 1134903170, 1836311903, 2971215073, 4807526976, 7778742049, 12586269025]
请输入要获取多少个元素的斐波那契数列（n >= 2）：q
程序结束！

实现6（矩阵快速幂）：



问题1：
代码A：

import numpy as np
def fib_matrix(n):
    result_list = []
    for i in range(n):
        res = pow((np.matrix([[1, 1], [1, 0]], dtype='int64')), i) * np.matrix([[1], [0]])
        result_list.append(int(res[0][0]))
    return result_list

while 1:
    num = input('请输入要获取斐波那契数列的第几个数字（n >= 2）：')
    if num.upper() == 'Q':
        print('程序结束！')
        break
    elif int(num) < 2:
        print('输入错误，请重新输入！')
    else:
        num = int(num)
        print('斐波那契数列的第{}个数字是{}'.format(num, fib_matrix(num)[-1]))

代码B：

# 使用矩阵计算斐波那契数列
import numpy as np
def Fibonacci_Matrix_tool(n):
    Matrix = np.matrix("1 1;1 0", dtype='int64')
    # 返回是matrix类型
    return np.linalg.matrix_power(Matrix, n)

def Fibonacci_Matrix(n):
    result_list = []
    for i in range(0, n):
        result_list.append(np.array(Fibonacci_Matrix_tool(i))[0][0])
    return result_list

while 1:
    num = input('请输入要获取斐波那契数列的第几个数字（n >= 2）：')
    if num.upper() == 'Q':
        print('程序结束！')
        break
    elif int(num) < 2:
        print('输入错误，请重新输入！')
    else:
        num = int(num)
        print('斐波那契数列的第{}个数字是{}'.format(num, Fibonacci_Matrix(num)[-1]))

运行结果

请输入要获取斐波那契数列的第几个数字（n >= 2）：1
输入错误，请重新输入！
请输入要获取斐波那契数列的第几个数字（n >= 2）：2
斐波那契数列的第2个数字是1
请输入要获取斐波那契数列的第几个数字（n >= 2）：3
斐波那契数列的第3个数字是2
请输入要获取斐波那契数列的第几个数字（n >= 2）：4
斐波那契数列的第4个数字是3
请输入要获取斐波那契数列的第几个数字（n >= 2）：5
斐波那契数列的第5个数字是5
请输入要获取斐波那契数列的第几个数字（n >= 2）：6
斐波那契数列的第6个数字是8
请输入要获取斐波那契数列的第几个数字（n >= 2）：10
斐波那契数列的第10个数字是55
请输入要获取斐波那契数列的第几个数字（n >= 2）：20
斐波那契数列的第20个数字是6765
请输入要获取斐波那契数列的第几个数字（n >= 2）：50
斐波那契数列的第50个数字是12586269025
请输入要获取斐波那契数列的第几个数字（n >= 2）：q
程序结束！

问题2：
代码A：

import numpy as np
def fib_matrix(n):
    result_list = []
    for i in range(n):
        res = pow((np.matrix([[1, 1], [1, 0]], dtype='int64')), i) * np.matrix([[1], [0]])
        result_list.append(int(res[0][0]))
    return result_list

while 1:
    num = input('请输入要获取多少个元素的斐波那契数列（n >= 2）：')
    if num.upper() == 'Q':
        print('程序结束！')
        break
    elif int(num) < 2:
        print('输入错误，请重新输入！')
    else:
        num = int(num)
        print('生成的斐波那契数列是{}'.format(fib_matrix(num)))

代码B：

# 使用矩阵计算斐波那契数列
import numpy as np
def Fibonacci_Matrix_tool(n):
    Matrix = np.matrix("1 1;1 0", dtype='int64')
    # 返回是matrix类型
    return np.linalg.matrix_power(Matrix, n)

def Fibonacci_Matrix(n):
    result_list = []
    for i in range(0, n):
        result_list.append(np.array(Fibonacci_Matrix_tool(i))[0][0])
    return result_list

while 1:
    num = input('请输入要获取多少个元素的斐波那契数列（n >= 2）：')
    if num.upper() == 'Q':
        print('程序结束！')
        break
    elif int(num) < 2:
        print('输入错误，请重新输入！')
    else:
        num = int(num)
        print('生成的斐波那契数列是{}'.format(Fibonacci_Matrix(num)))

运行结果

请输入要获取多少个元素的斐波那契数列（n >= 2）：1
输入错误，请重新输入！
请输入要获取多少个元素的斐波那契数列（n >= 2）：2
生成的斐波那契数列是[1, 1]
请输入要获取多少个元素的斐波那契数列（n >= 2）：3
生成的斐波那契数列是[1, 1, 2]
请输入要获取多少个元素的斐波那契数列（n >= 2）：4
生成的斐波那契数列是[1, 1, 2, 3]
请输入要获取多少个元素的斐波那契数列（n >= 2）：10
生成的斐波那契数列是[1, 1, 2, 3, 5, 8, 13, 21, 34, 55]
请输入要获取多少个元素的斐波那契数列（n >= 2）：20
生成的斐波那契数列是[1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765]
请输入要获取多少个元素的斐波那契数列（n >= 2）：50
生成的斐波那契数列是[1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, 10946, 17711, 28657, 46368, 75025, 121393, 196418, 317811, 514229, 832040, 1346269, 2178309, 3524578, 5702887, 9227465, 14930352, 24157817, 39088169, 63245986, 102334155, 165580141, 267914296, 433494437, 701408733, 1134903170, 1836311903, 2971215073, 4807526976, 7778742049, 12586269025]
请输入要获取多少个元素的斐波那契数列（n >= 2）：q
程序结束！

pow 速度 比 双**号快，np.linalg.matrix_power也是一种方法。
因为幂运算可以使用二分加速，所以矩阵法的时间复杂度为 O(log n)，
用科学计算包numpy来实现矩阵法 O(log n)。

上一篇下一篇

猜你喜欢

热点阅读