溫馨提示×
您好，登錄后才能下訂單哦！
點擊 登錄注冊 即表示同意《億速云用戶服務條款》
您好，登錄后才能下訂單哦！
前言
跳臺階、變態(tài)跳臺階、矩形覆蓋其實都和斐波那契數(shù)列是一類問題，文中通過示例代碼介紹的非常詳細，下面話不多說了，來一起看看詳細的介紹吧。
跳臺階
問題描述：
一只青蛙一次可以跳上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
變態(tài)跳臺階
問題描述：
一只青蛙一次可以跳上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
總結
以上就是這篇文章的全部內(nèi)容了，希望本文的內(nèi)容對大家的學習或者工作具有一定的參考學習價值，如果有疑問大家可以留言交流，謝謝大家對億速云的支持。
免責聲明：本站發(fā)布的內(nèi)容（圖片、視頻和文字）以原創(chuàng)、轉載和分享為主，文章觀點不代表本網(wǎng)站立場，如果涉及侵權請聯(lián)系站長郵箱：is@yisu.com進行舉報，并提供相關證據(jù)，一經(jīng)查實，將立刻刪除涉嫌侵權內(nèi)容。
