斐波纳契数列的计算是一个很老的话题了,出现在各种算法书中。今天写这篇博文的出发点是在网上看了MIT 6.00的公开课,正好把一些思路理清一些,毕竟有些东西,自己实践过后才有深刻的认识。
普通的递归计算
这是最简单的算法了,根据斐波纳契数列的定义就可以得出来:fib(n) = fib(n - 1) + fib(n - 2),具体的代码如下。(需要说明的是代码中都省略了对参数的检查,在实际的代码中是需要的)。
function fib(n) {
return (n === 0 || n === 1) ? 1 : fib(n - 1) + fib(n - 2);
}
使用查找表的递归计算
普通的递归计算会执行很多重复计算,通过查找表就可以获取到之前已经计算过的fib(k)的值,从而避免重复计算。代码如下:
function fib_m(n) {
var f = arguments.callee, m = f._m || (f._m = {0:1, 1:1});
return m[n] || (m[n] = f(n-1) + f(n-2));
}
在这里,把查找表作为JavaScript方法对象的一个属性。
迭代计算
更加简单的做法是使用迭代来计算,代码如下:
function fib_i(n) {
if (n === 0 || n === 1) { return 1; }
var a = 1, b = 1, c;
for (var i = 2; i <= n; i++) {
c = a + b;
b = a;
a = c;
}
return c;
}
这里用了3个变量,a和b分别表示f(n-1)和f(n-2),c表示f(n)。
分享到:
相关推荐
c# 斐波纳契数列求和算法 的实现。
斐波纳契数列通常做法是用递归实现,当然还有其它的方法。这里现学现卖,用PHP的迭代器来实现一个斐波纳契数列,几乎没有什么难度,只是把类里的next()方法重写了一次。注释已经写到代码中,也是相当好理解的。
The Fibonacci numbers Fn are defined as follows: F0 is 1, F1 is 1, and Fi+2 = Fi + Fi+1 , where i = 0, 1, 2, . . . . In other words, each number is the sum of the previous two numbers. The first few ...
矩阵快速幂的模板 ,采用矩阵转移的方法求斐波纳契数列的第n项。
斐波那契数列,又称黄金分割数列,指的是这样一个数列:0、1、1、2、3、5、8、13、21、……在数学上,斐波纳契数列以如下被以递归的方法定义:F0=0,F1=1,Fn=F(n-1)+F(n-2)(n>=2,n∈N*)在现代物理、准晶体结构、...
斐波那契数列java的简单实现,很简单明了
使用C++语言编程解决斐波那契数列问题,一共使用了三种方法:递归函数法、动态数组法、非递归函数法
数列
写一个斐波纳契数列: 其中代码 a, b = b, a+b 的计算方式为先计算右边表达式,然后同时赋值给左边,等价于: 执行结果: 这个例子介绍了几个新特征。 第一行包含了一个复合赋值:变量 a 和 b 同时得到新值 0 和 ...
斐波那契数列(Fibonacci sequence),又称黄金分割数列,由于是被数学家列昂纳多·斐波那契(Leonardoda Fibonacci)以兔子繁殖为例子而引入,故又称为“兔子数列”。 数学上,斐波那契数列以递归的形式进行定义: ...
在数学上,斐波纳契数列以如下被以递推的方法定义:F(1)=1,F(2)=1, F(n)=F(n-1)+F(n-2)(n>=3,n∈N*)// 方法一:int F
本篇文章是对打印菱形及斐波纳契数列的几种解法进行了详细的分析介绍,需要的朋友参考下
它按斐波纳契数列计算数字并递归分解,并在一个小巧,干净且美观的用户界面上显示它们。 该应用程序可以按以下方式运行: javac interfaceUtilsateur.java # compile java interfaceUtilsateur # run --- 法语 ...
斐波那契数列,又称黄金分割数列,指的是这样一个数列: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. 元组...
主要介绍了Python打印斐波拉契数列的方法,实例分析了基于Python实现斐波那契数列的实现技巧,具有一定参考借鉴价值,需要的朋友可以参考下
又称黄金分割数列、因数学家列昂纳多·斐波那契(Leonardoda Fibonacci)以兔子繁殖为例子而引入,故又称为“兔子数列”,指的是这样一个数列:1、1、2、3、5、8、13、21、34、……在数学上,斐波纳契数列以如下被以...
复制代码 代码如下:class Fibonacci implements Iterator { private $previous = 1; private $current = 0; private $key = 0; public function current() { return $this->current; } public function key() { ...
斐波那契数列,又称黄金分割数列,指的是这样一个数列:0、1、1、2、3、5、8、13、21、……在数学上,斐波纳契数列以如下被以递归的方法定义:F0=0,F1=1,Fn=F(n-1)+F(n-2)(n>=2,n∈N*)在现代物理、准晶体结构、...
该斐波那契时钟就是依照这种方式来计算时间的,现在就来详细讲解一下它的计算方式:钟面上有5个正方形色块,长度分别为斐波那契数列里的前五个数1、1、2、3、5,代表着时间的数值;红色代表小时;绿色代表分钟;而...
斐波纳契数列以如下被以递归的方法定义:F0=0,F1=1,Fn=F(n-1)+F(n-2)(n>=2,n∈N*) c语言 循环队列的算法