美文网首页Python学习手册
Python实现-斐波那契数列（6种方法）

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

作者: 复苏的兵马俑 | 来源:发表于2020-02-21 14:57 被阅读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)。

    相关文章

      网友评论

        本文标题：Python实现-斐波那契数列（6种方法）

        本文链接：https://www.haomeiwen.com/subject/iplcqhtx.html

        延伸阅读

        深度阅读

        • 您也可以注册成为美文阅读网的作者，发表您的原创作品、分享您的心情！

        栏目导航

        热点阅读

        Python学习手册

        关于我们|服务条款|联系我们|Python实现-斐波那契数列（6种方法）|投稿指南|网站地图|RSS订阅|排版工具|手机版

        提供经典美文摘抄,优美散文欣赏,现代诗歌精选,短篇小说,心情随笔,表白情书范文,故事会在线阅读欣赏

        Copyright © 2014-2023 Haomeiwen.com All Rights Reserved. 好美文阅读网 版权所有

        备案信息：桂公网安备 45052102000051号 · 桂ICP备13007215号-3

        本站所收录作品、热点评论等信息部分来源互联网，目的只是为了系统归纳学习和传递资讯

        所有作品版权归原创作者所有，与本站立场无关，如不慎侵犯了你的权益，请联系我们告知，我们将做删除处理！