前言

跳臺(tái)階、變態(tài)跳臺(tái)階、矩形覆蓋其實(shí)都和斐波那契數(shù)列是一類問(wèn)題，文中通過(guò)示例代碼介紹的非常詳細(xì)，下面話不多說(shuō)了，來(lái)一起看看詳細(xì)的介紹吧。

跳臺(tái)階

問(wèn)題描述：

一只青蛙一次可以跳上1級(jí)臺(tái)階，也可以跳上2級(jí)。求該青蛙跳上一個(gè)n級(jí)的臺(tái)階總共有多少種跳法。

分析：

初始值很容易得到，當(dāng)n > 2時(shí)，跳上n級(jí)臺(tái)階最后一步無(wú)外乎兩種情況，從第n-1級(jí)跳一級(jí)跳上來(lái)，或是從第n-2級(jí)跳2級(jí)跳上來(lái)，因此很容易得到如下遞歸公式。

F（0）= 0
F（1）= 1
F（2）= 2
F（n）= F（n-1）+ F（n-2）（n > 2）

代碼：

def jump_floor(number): if number <= 2:  return number prev, curr = 1, 2 for _ in range(3, number+1):  prev, curr = curr, prev+curr return curr

變態(tài)跳臺(tái)階

問(wèn)題描述：

一只青蛙一次可以跳上1級(jí)臺(tái)階，也可以跳上2級(jí)……它也可以跳上n級(jí)。求該青蛙跳上一個(gè)n級(jí)的臺(tái)階總共有多少種跳法。

分析：

相比上一個(gè)跳臺(tái)階，這次可以從任意臺(tái)階跳上第n級(jí)臺(tái)階，也可以直接跳上第n級(jí)。因此其遞歸公式為各個(gè)臺(tái)階之和再加上直接跳上去的一種情況。

F（0）= 0
F（1）= 1
F（2）= 2
F（n）= F（n-1）+ F（n-2）+ … + F（2）+ F（1）+ 1 = 2 **（n-1）

代碼：

def jump_floor(number): if number == 0:  return 0 return 2**(number-1)

矩形覆蓋

問(wèn)題描述：

我們可以用2*1的小矩形橫著或者豎著去覆蓋更大的矩形。請(qǐng)問(wèn)用n個(gè)2*1的小矩形無(wú)重疊地覆蓋一個(gè)2*n的大矩形，總共有多少種方法？

分析：

仔細(xì)分析這個(gè)問(wèn)題實(shí)際上就是普通的跳臺(tái)階問(wèn)題。

F（0）= 0
F（1）= 1
F（2）= 2
F（n）= F（n-1）+ F（n-2）（n > 2）

代碼：

def jump_floor(number): if number <= 2:  return number prev, curr = 1, 2 for _ in range(3, number+1):  prev, curr = curr, prev+curr return curr

總結(jié)

以上就是這篇文章的全部?jī)?nèi)容了，希望本文的內(nèi)容對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值，如果有疑問(wèn)大家可以留言交流，謝謝大家對(duì)武林站長(zhǎng)站的支持。