python实现斐波拉契数列

Corwien 发布于2019-07-30 16:02 / 1041人阅读

摘要：描述斐波那契数列由列昂纳多斐波那契以兔子繁殖为例子而引入，故又称为兔子数列。这个数列从第项开始，每一项都等于前两项之和。递归版本递归版本使用传参及默认参数，减少冗余元算的同时也减少了函数调用。

描述

斐波那契数列：1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, ...
由列昂纳多·斐波那契（Leonardoda Fibonacci）以兔子繁殖为例子而引入，故又称为“兔子数列”。

这个数列从第3项开始，每一项都等于前两项之和。
如果设F(n）为该数列的第n项（n∈N*），那么这句话可以写成如下形式：:F(n)=F(n-1)+F(n-2)

递归版本

通过这个公式，容易想到第一个递归版本

    def f(n):
        """递归版本 1"""
        return 1 if n <= 2 else f(n - 1) + f(n - 2)

递归版本 1 简单明了，但是存在很多冗余运算，导致运行效果堪忧。

    def f(n):
        """递归版本 2"""
        cache = {1: 1, 2: 1}
        s = lambda n: cache.get(n) or cache.setdefault(n, s(n - 1) + s(n - 2))
        return s(n)

递归版本 2 通过字典避免了冗余元算，但是存在大量函数调用的开销。

    def f(n, a=1, b=1):
        """递归版本 3"""
        return a if n <= 1 else f(n - 1, b, a + b)

递归版本 3 使用传参及默认参数，减少冗余元算的同时也减少了函数调用。

迭代版本

有递归版本，怎么少的了迭代版本

    def f(n):
        """迭代版本 1"""
        lst = [1, 1]
        for i in range(2, n):
            lst.append(lst[i - 2] + lst[i - 1])
        return lst[-1]

迭代版本 1 通过一个列表存储了每次运算的结果，也很直观

    def f(n):
        """迭代版本 2"""
        dct = {1: 1, 2: 1}
        for i in range(3, n + 1):
            dct[i] = dct[i - 1] + dct[i - 2]
        return dct[n]

迭代版本 2 和迭代版本 1 类似，使用字典而不是列表存储，占用空间更大

    def f(n):
        """迭代版本 3"""
        a, b = 1, 1
        for _ in range(n - 2):
            a, b = b, a + b
        return b

迭代版本 3 较前面2个迭代版本，通过交换技巧，节省了空间，效率有了提升

公式版本

这个数列有通项公式，所以还可以来个公式版本

    def f(n):
        """公式版本"""
        sqf = math.sqrt(5)
        return int(sqf / 5 * (math.pow(((1 + sqf) / 2), n) - math.pow(((1 - sqf) / 2), n)))

提示

python递归版本重新设置递归层数限制

import sys
sys.setrecursionlimit(1000000)

公式版本n较大时会引发溢出

OverflowError: math range error

总结

又想了个递归版本，利用了python中一个令人诟病的写法（可变类型作为默认参数）提升效率

    def f(n, cache={1: 1, 2: 1}):
        """递归版本完全体"""
        return cache.get(n) or cache.setdefault(n, f(n - 2, cache) + f(n - 1, cache))

n=1000 时，千次执行时间（s）

GPU云服务器云服务器斐波拉契 java中斐波拉契非波拉契斐波纳契

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/41444.html

JS数据结构与算法_树

摘要：上一篇数据结构与算法集合字典一递归学习树离不开递归。先序遍历的一种应用是打印一个结构化的文档下面的图描绘了先序遍历方法的访问路径后序遍历后序遍历则是先访问节点的后代节点，再访问节点本身。上一篇：JS数据结构与算法_集合&字典一、递归学习树离不开递归。 1.1 介绍递归是一种解决问题的方法，它解决问题的各个小部分，直到解决最初的大问题。递归通常涉及函数调用自身。通俗的解释：年级...

tabalt 2019-08-26 13:35 评论0 收藏0
算法记录 >> 斐波那契数列

摘要：今天去面试笔试题斐波那契数列实现，虽然很简单。回来想想既然算法这么重要那就从这个开始来记录自己的算法库吧。在数学上，斐波纳契数列以如下被以递归的方法定义，，。斐波拉契算法规律很简单，，观察下数列值就很容易总结出来了。一、写在前面算法这块对于大多数程序员（包括我）来说可能都是一个薄弱的地方，如何弥补尼？每个人都知道那就是学习、特别是算法没有任何捷径可走。在这记录平时自己工作和生...

robin 2019-08-16 17:52 评论0 收藏0
使用JavaScript ES6的新特性计算Fibonacci（非波拉契数列）

摘要：采用的生成非波拉契数列提供了原生的支持，语法非常有特色，关键字后面紧跟一个星号。的详细介绍参考官网先看如何用这个黑科技重新实现非波拉契树立的生成。在这个内部，我们定义了一个无限循环，用于计算非波拉契数列。程序员面试系列 Java面试系列-webapp文件夹和WebContent文件夹的区别？程序员面试系列：Spring MVC能响应HTTP请求的原因？ Java程序员面试系列-什么...

yanbingyun1990 2019-08-23 12:29 评论0 收藏0
RxJS API解析（四）

摘要：任何程序设计语言在讲解递归特性时，基本都会举汉诺塔斐波拉契数列的例子。没错，请你对比一下斐波拉契数列和定义的相似之处递归完成后产生值的过程就是的过程。 Rx*(Observable.combineLatest)方法方法定义 Rx.Observable.combineLatest(...args, [resultSelector]) 作用通过处理函数总是将指定的可观察对象序列中最新发...

cheng10 2019-08-19 17:28 评论0 收藏0
太原面经分享：如何用js实现返回斐波那契数列的第n个值的函数

摘要：那其实这个问题还可以换个问法实现一个函数，输入一个数字能返回斐波那契数列的第个值。文章预告更多的前端面试分享我都会第一时间更新在我的公众号闰土大叔里面，欢迎关注面试攒经验，lets go！值此高考来临之际，闲不住的我又双叒叕出发去面试攒经验了，去了公司交待一番流程后，面试官甩给了我一张A4纸，上面写着一道js算法笔试题（一开始我并不知道这是在考察js算法），上面写着1、1、2、3、...

Galence 2019-08-26 12:01 评论0 收藏0