​费波那契数列(意大利语:Successione di Fibonacci),又译为费波拿契数、斐波那契数列、费氏数列、黄金分割数列。在数学上,费波那契数列是以递归的方法来定义:
用文字来说,就是费波那契数列由0和1开始,之后的费波那契系数就是由之前的两数相加而得出。首几个费波那契系数是:
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233……
下图是以费波那契数为边的正方形拼成的近似的黄金矩形:
根据高德纳(Donald Ervin Knuth)的《计算机程序设计艺术》(The Art of Computer Programming),1150年印度数学家Gopala和金月在研究箱子包装物件长宽刚好为1和2的可行方法数目时,首先描述这个数列。在西方,最先研究这个数列的人是比萨的列奥那多(意大利人斐波那契Leonardo Fibonacci),他描述兔子生长的数目时用上了这数列:
第一个月初有一对刚诞生的兔子
第二个月之后(第三个月初)它们可以生育
每月每对可生育的兔子会诞生下一对新兔子
兔子永不死去
假设在n月有兔子总共a对,n+1月总共有b对。在n+2月必定总共有a+b对:因为在n+2月的时候,前一月(n+1月)的b对兔子可以存留至第n+2月(在当月属于新诞生的兔子尚不能生育)。而新生育出的兔子对数等于所有在n月就已存在的a对。
JavaScript迭代版
function fib(n) {
var fib_n
= function(curr, next, n) {
if (n
== 0) {
return curr; }
else {
return fib_n(next, curr
+next, n
-1); } }
return fib_n(
0,
1, n);
}
alert(fib(
40));
长按下图二维码添加公众号"STEAM解密",获得更多有价值信息。