斐波那契數(shù)列-爬樓梯算法

爬樓梯算法

有n級(jí)樓梯，有2種爬法，1次1級(jí)，或1次2級(jí)，問(wèn)，n級(jí)樓梯有多少種爬法？

遞歸求解

首先，當(dāng)只有一階樓梯的時(shí)候，很顯然只有一種走法；有兩階樓梯的時(shí)候，也很顯然的知道有兩種走法。就會(huì)有下面這句判斷語(yǔ)句。

if (n == 1 || n == 2) {  return n}

一階二階的思想就出來(lái)了，那如果當(dāng)階數(shù)是三階四階甚至n階的時(shí)候呢?

當(dāng) n > 2 時(shí)，第一次跳一級(jí)還是兩級(jí)，決定了后面剩下的臺(tái)階的跳法數(shù)目的不同：如果第一次只跳一級(jí)，則后面剩下的 n-1 級(jí)臺(tái)階的跳法數(shù)目為 f(n-1)；如果第一次跳兩級(jí)，則后面剩下的n-2 級(jí)臺(tái)階的跳法數(shù)目為 f(n-2)。所以，得出遞歸方程，f(n) = f(n-1) + f(n-2)。問(wèn)題本質(zhì)是斐波那契數(shù)列。

聊著聊著我們的代碼就出來(lái)了。

var climbStairs = function (n) {  if (n == 1 || n == 2) {    return n  }  else {    return climbStairs(n - 2) + climbStairs(n - 1)  }}

斐波那契數(shù)列

斐波那契數(shù)列（Fibonacci sequence），又稱黃金分割數(shù)列，因數(shù)學(xué)家萊昂納多·斐波那契（Leonardo Fibonacci）以兔子繁殖為例子而引入，故又稱為“兔子數(shù)列”，指的是這樣一個(gè)數(shù)列：0、1、1、2、3、5、8、13、21、34、……在數(shù)學(xué)上，斐波那契數(shù)列以如下被以遞推的方法定義：F(0)=0，F(xiàn)(1)=1, F(n)=F(n - 1)+F(n - 2)（n ≥ 2，n ∈ N*）

我們現(xiàn)在回到兔子問(wèn)題。

假設(shè)一對(duì)初生兔子要一個(gè)月才到成熟期，而一對(duì)成熟兔子每月會(huì)生一對(duì)兔子，那么，由一對(duì)初生兔子開(kāi)始，12 個(gè)月后會(huì)有多少對(duì)兔子呢？

我們按照規(guī)則，畫(huà)出了1-7月份兔子的繁殖情況。我們發(fā)現(xiàn)1-7月份兔子的數(shù)量分別為1, 1, 2, 3, 5, 8, 13對(duì)。為了更清晰一點(diǎn)，我們作出下面的示意圖。

顯然在圖中，我們的黑點(diǎn)表示的是成熟兔子，白點(diǎn)表示的是小兔子。我們夠仔細(xì)的話能夠發(fā)現(xiàn)，右邊這一列數(shù)字是有規(guī)律的。第一個(gè)數(shù)和第二個(gè)數(shù)為1，之后的每一個(gè)數(shù)為之前兩個(gè)數(shù)之和。比如，六月份的兔子數(shù)量為四月份和五月份兔子數(shù)量之和，即8=5+3。

var climbStairs = function (n) {  if (n == 1 || n == 2) {    return 1  }  else {    return climbStairs(n - 2) + climbStairs(n - 1)  }}

因此，兔子問(wèn)題得以解決，答案為144對(duì)。以上數(shù)列，即“斐波那契數(shù)列”。

總結(jié)

斐波那契數(shù)列的自身特性：0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233……

第一項(xiàng)和第二項(xiàng)是1，之后的每一項(xiàng)為之前兩項(xiàng)的和。即：

a1=a2=1

an=an-1+an-2 （n為正整數(shù)）