前言

跳臺階、變態跳臺階、矩形覆蓋其實都和斐波那契數列是一類問題，文中通過示例代碼介紹的非常詳細，下面話不多說了，來一起看看詳細的介紹吧。

跳臺階

問題描述：

一只青蛙一次可以跳上1級臺階，也可以跳上2級。求該青蛙跳上一個n級的臺階總共有多少種跳法。

分析：

初始值很容易得到，當n > 2時，跳上n級臺階最后一步無外乎兩種情況，從第n-1級跳一級跳上來，或是從第n-2級跳2級跳上來，因此很容易得到如下遞歸公式。

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

變態跳臺階

問題描述：

一只青蛙一次可以跳上1級臺階，也可以跳上2級……它也可以跳上n級。求該青蛙跳上一個n級的臺階總共有多少種跳法。

分析：

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

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)

矩形覆蓋

問題描述：

我們可以用2*1的小矩形橫著或者豎著去覆蓋更大的矩形。請問用n個2*1的小矩形無重疊地覆蓋一個2*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

總結

以上就是這篇文章的全部內容了，希望本文的內容對大家的學習或者工作具有一定的參考學習價值，如果有疑問大家可以留言交流，謝謝大家對VEVB武林網的支持。