如何使用Python实现斐波那契数列

斐波那契数列（Fibonacci）最早由印度数学家Gopala提出，而第一个真正研究斐波那契数列的是意大利数学家 Leonardo Fibonacci，斐波那契数列的定义很简单，用数学函数可表示为：

数列从0和1开始，之后的数由前两个数相加而得出，例如斐波那契数列的前10个数是：0, 1, 1, 2, 3, 5, 8, 13, 21, 34。

用 Python 实现斐波那契数列常见的写法有三种，各算法的执行效率也有很大差别，在面试中也会偶尔会被问到，通常面试的时候不是让你简单的用递归写写就完了，还会问你时间复杂度怎样，空间复杂度怎样，有没有可改进的地方。

递归法

所谓递归就是指函数的定义中使用了函数自身的方法

def fib_recur(n):
assert n >= 0
if n in (0, 1):
return n
return fib_recur(n - 1) + fib_recur(n - 2)
for i in range(20):
print(fib_recur(i), end=" ")
>>> 0 1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597 2584 4181

递归是一种代码最简洁的方法，但它是效率非常低，因为会出现大量的重复计算，时间复杂度是：O(1.618 ^ n)，1.618是黄金分割。同时受限于 Python 中递归的最大深度是 1000，所以用递归来求解并不是一种可取的办法。

递推法

递推法就是从0和1开始，前两项相加逐个求出第3、第4个数，直到求出第n个数的值

def fib_loop(n):
a, b = 0, 1
for i in range(n):
a, b = b, a + b
return a
for i in range(20):
print(fib_loop(i), end=" ")
>>> 0 1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597 2584 4181

这种算法的时间复杂是O(n)，呈线性增长，如果数据量巨大，速度越到后面会越慢。

上面两种方式都是使用分而治之的思想，就是把一个大的问题化小，然后利用小问题的求解得到目标问题的答案。

矩阵法

《线性代数》是大学计算机专业低年级的课程，这门课教的就是矩阵，那时候觉得这东西学起来很枯燥，没什么用处，工作后你才发现搞机器学习、数据分析、数据建模时大有用处，书到用时方恨少。其实矩阵的本质就是线性方程式。

斐波那契数列中两个相邻的项分别为：F(n) 和 F(n - 1)，如果把这两个数当作一个2行1列的矩阵可表示为：

因为 F(n) = F(n-1)+F(n-2)，所以就有：

通过反推，其实它是两个矩阵的乘积得来的

依此类推：

最后可推出：

因此想要求出F(n)的值，只要能求出右边矩阵的n-1次方的值，最后求得两矩阵乘积，取新矩阵的第一行的第一列的值即可，比如n=3时，

​可以得知F(3)的值2，F(2)的值为1，因为幂运算可以使用二分加速，所以矩阵法的时间复杂度为 O(log n)

我们可以用科学计算包 numpy 来实现矩阵法：

import numpy
def fib_matr(n):
return (numpy.matrix([[1, 1], [1, 0]]) ** (n - 1) * numpy.matrix([[1], [0]]))[0, 0]
for i in range(20):
print(int(fib_matr(i)), end=" ")
>>> 0 1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597 2584 4181

3中不同的算法效率对比：

从上面图可以看出递归法效率惊人的低，矩阵法在数据量比较大的时候才突显出它的优势，递推法随着数据的变大，所花的时间也越来越大。

以上就是本文的全部内容，希望对大家的学习有所帮助，也希望大家多多支持我们。

赞 (0)

相关推荐

  • 详解python使用递归、尾递归、循环三种方式实现斐波那契数列

    在最开始的时候所有的斐波那契代码都是使用递归的方式来写的,递归有很多的缺点,执行效率低下,浪费资源,还有可能会造成栈溢出,而递归的程序的优点也是很明显的,就是结构层次很清晰,易于理解 可以使用循环的方式来取代递归,当然也可以使用尾递归的方式来实现. 尾递归就是从最后开始计算, 每递归一次就算出相应的结果, 也就是说, 函数调用出现在调用者函数的尾部, 因为是尾部, 所以根本没有必要去保存任何局部变量. 直接让被调用的函数返回时越过调用者, 返回到调用者的调用者去.尾递归就是把当前的运算结果(或路

  • Python实现求数列和的方法示例

    本文实例讲述了Python实现求数列和的方法.分享给大家供大家参考,具体如下: 问题: 输入 输入数据有多组,每组占一行,由两个整数n(n<10000)和m(m<1000)组成,n和m的含义如前所述. 输出 对于每组输入数据,输出该数列的和,每个测试实例占一行,要求精度保留2位小数. 样例输入 81 4 2 2 样例输出 94.73 3.41 实现代码: import math while 1: x = raw_input() x = list(x.split(" "))

  • Python基于递归算法实现的汉诺塔与Fibonacci数列示例

    Python基于递归算法实现的汉诺塔与Fibonacci数列示例

    本文实例讲述了Python基于递归算法实现的汉诺塔与Fibonacci数列.分享给大家供大家参考,具体如下: 这里我们通过2个例子,学习python中递归的使用. 1. 找出Fibonacci数列中,下标为 n 的数(下标从0计数) Fibonacci数列的形式是这样的:0,1,1,2,3,5,8,13-- ① 使用while循环,python2代码如下: def fib(n): a,b=0,1 count=0 while count<n: a,b=b,a+b count=count+1 pri

  • python实现斐波那契数列的方法示例

    python实现斐波那契数列的方法示例

    介绍 斐波那契数列,又称黄金分割数列,指的是这样一个数列:0.1.1.2.3.5.8.13.21.--在数学上,斐波纳契数列以如下递归的方法定义: F(0)=0,F(1)=1,F(n)=F(n-1)+F(n-2)(n≥2,n∈N*) . 1. 元组实现 fibs = [0, 1] for i in range(8): fibs.append(fibs[-2] + fibs[-1]) 这能得到一个在指定范围内的斐波那契数列的列表. 2. 迭代器实现 class Fibs: def __init__

  • Python打印斐波拉契数列实例

    本文实例讲述了Python打印斐波拉契数列的方法.分享给大家供大家参考.具体实现方法如下: #打印斐波拉契数列 #!/usr/bin/python def feibolaqi(n): if n == 0 or n == 1: return n else: return feibolaqi(n-1) + feibolaqi(n-2) num = int(raw_input('please input a int:')) if num >= 0: print 'feibolaqi(%d) is %d

  • 如何使用Python实现斐波那契数列

    如何使用Python实现斐波那契数列

    斐波那契数列(Fibonacci)最早由印度数学家Gopala提出,而第一个真正研究斐波那契数列的是意大利数学家 Leonardo Fibonacci,斐波那契数列的定义很简单,用数学函数可表示为: 数列从0和1开始,之后的数由前两个数相加而得出,例如斐波那契数列的前10个数是:0, 1, 1, 2, 3, 5, 8, 13, 21, 34. 用 Python 实现斐波那契数列常见的写法有三种,各算法的执行效率也有很大差别,在面试中也会偶尔会被问到,通常面试的时候不是让你简单的用递归写写就完了,

  • 使用python求斐波那契数列中第n个数的值示例代码

    斐波那契数列(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*) 求斐波那契数列中第n个数的值:1,1,2,3,5,8,13,21,34- 方法一:用for循

  • 利用Python实现斐波那契数列的方法实例

    今天我们来使用Python实现递归算法求指定位数的斐波那契数列 首先我们得知道斐波那契数列是什么? 斐波那契数列又叫兔子数列 斐波那契数列就是一个数列从第三项开始第三项的值是第一项和第二项的和依次类推 其次我们再来看递归算法是什么? 递归就是如果函数(子程序)包含了对其自身的调用,该函数就是递归的 话不多说上案例: 第一种方法:不使用递归算法 #首先定义一个新的列表来储存最后的结果 new_list = [] # 然后让用户输入指定位数 my_put = int(input("请输入使用递归算法

  • Python实现斐波那契数列的多种写法总结

    目录 1.for循环 2.while循环 3.使用递归 4.递归+for循环 5.递归+while循环 6.递归+定义函数+for循环 7.指定列表 趣方程求解 pandas 每日一练 斐波那契数列——经典例子,永不过时!!! 1.for循环 def fibonacci1(n): a, b = 0, 1 for i in range(n): a, b = b, a+b print(a) fibonacci1(3) 或 def fib1(w): a, b = 1, 1 for i in range

  • python求斐波那契数列示例分享

    复制代码 代码如下: def getFibonacci(num): res=[0,1] a=0 b=1 for x in range(0,num):  if x==a+b:   res.append(x)   a,b=b,a+b return res res=getFibonacci(1000)print(res) #递归a=[0,1]qian=0def fibna(num,qian): print(num) he=num+qian if he<1000:  a.append(he)  qian

  • python实现斐波那契递归函数的方法

    本文以一个简单的实例讲述了python实现斐波那契数列数列递归函数的方法,代码精简易懂.分享给大家供大家参考之用. 主要函数代码如下: def fab(n): if n==1: return 1 if n==0: return 0 else: result=int(fab(n-1))+int(fab(n-2)) return result 测试代码如下: for i in range(10): print fab(i) 希望本文所述对大家Python程序设计的学习有所帮助.

  • Python/R语言分别实现斐波那契数列的示例详解

    Python/R语言分别实现斐波那契数列的示例详解

    目录 前言 1.年龄计算 1.1 图解问题 1.2 代码解决 1.3 实验小结 2.斐波那契数列 2.1 图解问题 2.2 代码实现 2.3 实验小结 总结 前言 此专栏为python与R语言对比学习的文章:以通俗易懂的小实验,带领大家深入浅出的理解两种语言的基本语法,并用以实际场景!感谢大家的关注,希望对大家有所帮助. “博观而约取,厚积而薄发!”谨以此言,望诸君共勉 本文将前两个小实验整理拼凑再了一起 :分别是“年龄计算”.“斐波那契数列”.具体的项目介绍见下文. 1.年龄计算 有 5 个人

  • 用Python实现斐波那契（Fibonacci）函数

    Fibonacci斐波那契数列,很简单,就是一个递归嘛,学任何编程语言可能都会做一下这个. 最近在玩Python,在粗略的看了一下Learning Python和Core Python之后,偶然发现网上有个帖子Python程序员的进化写的很有意思.于是打算仿照一篇,那篇帖子用了十余种方法完成一个阶乘函数,我在这里会用九种不同的风格写出一个Fibonacci函数. 要求很简单,输入n,输出第n个Fibonacci数,n为正整数 下面是这九种不同的风格: 1)第一次写程序的Python程序员: de

随机推荐