摘要：描述斐波那契数列由列昂纳多斐波那契以兔子繁殖为例子而引入，故又称为兔子数列。这个数列从第项开始，每一项都等于前两项之和。递归版本递归版本使用传参及默认参数，减少冗余元算的同时也减少了函数调用。
描述
斐波那契数列：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）
文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。
转载请注明本文地址：https://www.ucloud.cn/yun/41444.html
摘要：上一篇数据结构与算法集合字典一递归学习树离不开递归。先序遍历的一种应用是打印一个结构化的文档下面的图描绘了先序遍历方法的访问路径后序遍历后序遍历则是先访问节点的后代节点，再访问节点本身。 上一篇：JS数据结构与算法_集合&字典 一、递归 学习树离不开递归。 1.1 介绍 递归是一种解决问题的方法，它解决问题的各个小部分，直到解决最初的大问题。递归通常涉及函数调用自身。 通俗的解释：年级...
摘要：今天去面试笔试题斐波那契数列实现，虽然很简单。回来想想既然算法这么重要那就从这个开始来记录自己的算法库吧。在数学上，斐波纳契数列以如下被以递归的方法定义，，。斐波拉契算法规律很简单，，观察下数列值就很容易总结出来了。 一、写在前面 算法这块对于大多数程序员（包括我）来说可能都是一个薄弱的地方，如何弥补尼？ 每个人都知道那就是学习、特别是算法没有任何捷径可走。 在这记录平时自己工作和生...
摘要：采用的生成非波拉契数列提供了原生的支持，语法非常有特色，关键字后面紧跟一个星号。的详细介绍参考官网先看如何用这个黑科技重新实现非波拉契树立的生成。在这个内部，我们定义了一个无限循环，用于计算非波拉契数列。 程序员面试系列 Java面试系列-webapp文件夹和WebContent文件夹的区别？ 程序员面试系列：Spring MVC能响应HTTP请求的原因？ Java程序员面试系列-什么...
摘要：任何程序设计语言在讲解递归特性时，基本都会举汉诺塔斐波拉契数列的例子。没错，请你对比一下斐波拉契数列和定义的相似之处递归完成后产生值的过程就是的过程。 Rx*(Observable.combineLatest)方法 方法定义 Rx.Observable.combineLatest(...args, [resultSelector]) 作用 通过处理函数总是将指定的可观察对象序列中最新发...
摘要：那其实这个问题还可以换个问法实现一个函数，输入一个数字能返回斐波那契数列的第个值。文章预告更多的前端面试分享我都会第一时间更新在我的公众号闰土大叔里面，欢迎关注 面试攒经验，lets go！ 值此高考来临之际，闲不住的我又双叒叕出发去面试攒经验了，去了公司交待一番流程后，面试官甩给了我一张A4纸，上面写着一道js算法笔试题（一开始我并不知道这是在考察js算法），上面写着1、1、2、3、...
阅读 2356·2023-04-25 18:13
阅读 542·2021-11-22 12:10
阅读 2816·2021-11-22 11:57
阅读 1994·2021-11-19 11:26
阅读 1890·2021-09-22 15:40
阅读 1295·2021-09-03 10:28
阅读 2539·2019-08-30 15:53
阅读 1775·2019-08-30 15:44
