首页 > 代码库 > 斐波那契数列多种实现方法
斐波那契数列多种实现方法
问题
费波那契数列(意大利语:Successione di Fibonacci),又译费波拿契数、斐波那契数列、斐波那契数列、黄金分割数列。
在数学上,费波那契数列是以递归的方法来定义:
F0 = 0 (n=0) F1 = 1 (n=1) Fn = F[n-1]+ F[n-2](n=>2)
关于Fibonacci的精彩解释,请看下列视频:
TED-神奇的斐波那契数列:http://v.163.com/movie/2014/2/N/O/M9HKRT25D_M9HNA0UNO.html,这个视频是我看到过的对Fibonacci数列最精彩的讲授,向各位推荐。
如果要查看文字解释,请看维基百科词条:斐波那契数列
思路说明
几乎所有的高级语言都要拿Fibonacci数列为例子,解释递归、循环等概念。这里,我要用Python来演示一下,各种不同的写法,供参考。
解决(python)
递归——按照定义直接写
这种方法不是一个好方法,因为它的开销太大,比如计算fib1(100),就需要耐心等待较长一段时间了。所以,这是一种不实用的方法。但是,因为思路直接简单,列为第一种。
def fib1(n): if n==0: return 0 elif n==1: return 1 else: return fib1(n-1) + fib1(n-2)
递归,进行初始化
fib1的慢,就是因为每次都要计算前面已经算过的项目.这里将上述算法进行稍微改进。速度快了很多。
memo = {0:0, 1:1} def fib2(n): if not n in memo: memo[n] = fib2(n-1)+fib2(n-2) return memo[n]
迭代
这也不失为一种简单直接的方法
def fib3(n): a, b = 0, 1 for i in range(n): a, b = b, a+b return a
直接用数学结论
在维基百科的词条 里面,已经列出了不同形式的Fibonacci数列的数学结果,可以直接将这些结果拿过来,通过程序计算,得到斐波那契数。此类程序,本文略。
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。