跳臺階問題

　　題目：一個臺階總共有n級，如果一次可以跳1級，也可以跳2級。求總共有多少總跳法，并分析算法的時間復(fù)雜度。

　　分析：這道題最近經(jīng)常出現(xiàn)，包括MicroStrategy等比較重視算法的公司都曾先后選用過個這道題作為面試題或者筆試題。

　　首先我們考慮最簡單的情況。如果只有1級臺階，那顯然只有一種跳法。如果有2級臺階，那就有兩種跳的方法了：一種是分兩次跳，每次跳1級;另外一種就是一次跳2級。

　　現(xiàn)在我們再來討論一般情況。我們把n級臺階時的跳法看成是n的函數(shù)，記為f(n)。當(dāng)n>2時，第一次跳的時候就有兩種不同的選擇：一是第一次只跳1級，此時跳法數(shù)目等于后面剩下的n-1級臺階的跳法數(shù)目，即為f(n-1);另外一種選擇是第一次跳2級，此時跳法數(shù)目等于后面剩下的n-2級臺階的跳法數(shù)目，即為f(n-2)。因此n級臺階時的不同跳法的總數(shù)f(n)=f(n-1)+(f-2)。

　　我們把上面的分析用一個公式總結(jié)如下：

　　/ 1 n=1

　　f(n)= 2 n=2

　　\ f(n-1)+(f-2) n>2

　　分析到這里，相信很多人都能看出這就是我們熟悉的Fibonacci序列。至于怎么求這個序列的第n項，請參考本面試題系列第16題，這里就不在贅述了。

　　相關(guān)推薦：

　　2015年軟考信息技術(shù)處理員考前知識點總結(jié)匯總

　　2015年軟件水平考試《程序員》提高練習(xí)題匯總

　　2015軟件水平考試《程序員》知識點總結(jié)匯總