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

斐波那契数列（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)。

最后编辑于 ：
©著作权归作者所有,转载或内容合作请联系作者
  • 人面猴
    序言：七十年代末，一起剥皮案震惊了整个滨河市，随后出现的几起案子，更是在滨河造成了极大的恐慌，老刑警刘岩，带你破解...
    沈念sama阅读 212,686评论 6赞 492
  • 死咒
    序言：滨河连续发生了三起死亡事件，死亡现场离奇诡异，居然都是意外死亡，警方通过查阅死者的电脑和手机，发现死者居然都...
    沈念sama阅读 90,668评论 3赞 385
  • 救了他两次的神仙让他今天三更去死
    文/潘晓璐 我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
    开封第一讲书人阅读 158,160评论 0赞 348
  • 道士缉凶录：失踪的卖姜人
    文/不坏的土叔 我叫张陵，是天一观的道长。 经常有香客问我，道长，这世上最难降的妖魔是什么？ 我笑而不...
    开封第一讲书人阅读 56,736评论 1赞 284
  • 港岛之恋（遗憾婚礼）
    正文 为了忘掉前任，我火速办了婚礼，结果婚礼上，老公的妹妹穿的比我还像新娘。我一直安慰自己，他们只是感情好，可当我...
    茶点故事阅读 65,847评论 6赞 386
  • 恶毒庶女顶嫁案：这布局不是一般人想出来的
    文/花漫 我一把揭开白布。 她就那样静静地躺着，像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上，一...
    开封第一讲书人阅读 50,043评论 1赞 291
  • 城市分裂传说
    那天，我揣着相机与录音，去河边找鬼。 笑死，一个胖子当着我的面吹牛，可吹牛的内容都是我干的。 我是一名探鬼主播，决...
    沈念sama阅读 39,129评论 3赞 410
  • 双鸳鸯连环套：你想象不到人心有多黑
    文/苍兰香墨 我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
    开封第一讲书人阅读 37,872评论 0赞 268
  • 万荣杀人案实录
    序言：老挝万荣一对情侣失踪，失踪者是张志新（化名）和其女友刘颖，没想到半个月后，有当地人在树林里发现了一具尸体，经...
    沈念sama阅读 44,318评论 1赞 303
  • 护林员之死
    正文 独居荒郊野岭守林人离奇死亡，尸身上长有42处带血的脓包…… 初始之章·张勋 以下内容为张勋视角 年9月15日...
    茶点故事阅读 36,645评论 2赞 327
  • 白月光启示录
    正文 我和宋清朗相恋三年，在试婚纱的时候发现自己被绿了。 大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
    茶点故事阅读 38,777评论 1赞 341
  • 活死人
    序言：一个原本活蹦乱跳的男人离奇死亡，死状恐怖，灵堂内的尸体忽然破棺而出，到底是诈尸还是另有隐情，我是刑警宁泽，带...
    沈念sama阅读 34,470评论 4赞 333
  • 日本核电站爆炸内幕
    正文 年R本政府宣布，位于F岛的核电站，受9级特大地震影响，放射性物质发生泄漏。R本人自食恶果不足惜，却给世界环境...
    茶点故事阅读 40,126评论 3赞 317
  • 男人毒药：我在死后第九天来索命
    文/蒙蒙 一、第九天 我趴在偏房一处隐蔽的房顶上张望。 院中可真热闹，春花似锦、人声如沸。这庄子的主人今日做“春日...
    开封第一讲书人阅读 30,861评论 0赞 21
  • 一桩弑父案，背后竟有这般阴谋
    文/苍兰香墨 我抬头看了看天上的太阳。三九已至，却和暖如春，着一层夹袄步出监牢的瞬间，已是汗流浃背。 一阵脚步声响...
    开封第一讲书人阅读 32,095评论 1赞 267
  • 情欲美人皮
    我被黑心中介骗来泰国打工， 没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留，地道东北人。 一个月前我还...
    沈念sama阅读 46,589评论 2赞 362
  • 代替公主和亲
    正文 我出身青楼，却偏偏与公主长得像，于是被迫代替她去往敌国和亲。 传闻我的和亲对象是个残疾皇子，可洞房花烛夜当晚...
    茶点故事阅读 43,687评论 2赞 351