使用C++遞歸求解跳臺(tái)階問(wèn)題
題目：
一個(gè)臺(tái)階總共有 n 級(jí)，如果一次可以跳 1 級(jí)，也可以跳 2 級(jí)。求總共有多少總跳法？
分析：
也是比較基礎(chǔ)的題目，通過(guò)遞歸可以方便的求解。
用Fib(n)表示青蛙跳上n階臺(tái)階的跳法數(shù)，青蛙一次性跳上n階臺(tái)階的跳法數(shù)1(n階跳)，設(shè)定Fib(0) = 1；
當(dāng)n = 1 時(shí)， 只有一種跳法，即1階跳：Fib(1) = 1;
當(dāng)n = 2 時(shí)， 有兩種跳的方式，一階跳和二階跳：Fib(2) = Fib(1) + Fib(0) = 2;
當(dāng)n = 3 時(shí)，有三種跳的方式，第一次跳出一階后，后面還有Fib(3-1)中跳法； 第一次跳出二階后，后面還有Fib(3-2)中跳法；第一次跳出三階后，后面還有Fib(3-3)中跳法
Fib(3) = Fib(2) + Fib(1)+Fib(0)=4;
當(dāng)n = n 時(shí)，共有n種跳的方式，第一次跳出一階后，后面還有Fib(n-1)中跳法； 第一次跳出二階后，后面還有Fib(n-2)中跳法..........................第一次跳出n階后，后面還有 Fib(n-n)中跳法.
Fib(n) = Fib(n-1)+Fib(n-2)+Fib(n-3)+..........+Fib(n-n)=Fib(0)+Fib(1)+Fib(2)+.......+Fib(n-1)
又因?yàn)镕ib(n-1)=Fib(0)+Fib(1)+Fib(2)+.......+Fib(n-2)
兩式相減得：Fib(n)-Fib(n-1)=Fib(n-1) =====》 Fib(n) = 2*Fib(n-1) n >= 2
遞歸等式如下：
代碼實(shí)現(xiàn)如下（GCC編譯通過(guò)）：
#include "stdio.h"
#include "stdlib.h"
int function(int n);
int main(void)
{
int tmp;
tmp = function(5);
printf("%3d\n",tmp);
return 0;
}
int function(int n)
{
if(n == 1)
return 1;
else if(n == 2)
return 2;
else
return function(n-1) + function(n-2);
}
相關(guān)文章
C++11/14 線程中使用Lambda函數(shù)的方法
這篇文章主要介紹了C++11/14 線程中使用Lambda函數(shù)的方法，小編覺(jué)得挺不錯(cuò)的，現(xiàn)在分享給大家，也給大家做個(gè)參考。一起跟隨小編過(guò)來(lái)看看吧2019-01-01
今天小編就為大家分享一篇關(guān)于劍指offer之判斷鏈表是否包含環(huán)，小編覺(jué)得內(nèi)容挺不錯(cuò)的，現(xiàn)在分享給大家，具有很好的參考價(jià)值，需要的朋友一起跟隨小編來(lái)看看吧2019-02-02
MATLAB全網(wǎng)最全的colormap的使用教程詳解
眾所周知，MATLAB中的colormap只有少得可憐的幾種，有很多應(yīng)用在很特殊的圖形中的colormap幾乎都沒(méi)有，而每次寫(xiě)代碼都要去找顏色的圖屬實(shí)太麻煩。所以本文將包全部集成了進(jìn)來(lái)，終于有了這套包含200個(gè)colormap的工具函數(shù)，希望對(duì)大家有所幫助2023-02-02
這篇文章主要介紹了C++三元表達(dá)式，文章圍繞C++三元表達(dá)式的相關(guān)資料展開(kāi)詳細(xì)內(nèi)容,需要的朋友可以參考一下，希望多你有所幫助2021-11-11
基于C語(yǔ)言掃雷游戲的設(shè)計(jì)與實(shí)現(xiàn)
大家好，本篇文章主要講的是基于C語(yǔ)言掃雷游戲的設(shè)計(jì)與實(shí)現(xiàn)，感興趣的同學(xué)趕快來(lái)看一看吧，對(duì)你有幫助的話記得收藏一下，方便下次瀏覽2021-12-12
本篇文章是對(duì)uCOS中全局變量的使用進(jìn)行了詳細(xì)的分析介紹，需要的朋友參考下2013-05-05
C語(yǔ)言隨機(jī)數(shù)生成教程(rand和srand用法)
這篇文章主要介紹了C語(yǔ)言隨機(jī)數(shù)生成教程(rand和srand用法)，文中通過(guò)示例代碼介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值，需要的朋友們下面隨著小編來(lái)一起學(xué)習(xí)學(xué)習(xí)吧2021-01-01
用C語(yǔ)言實(shí)現(xiàn)簡(jiǎn)單的三子棋
這篇文章主要為大家詳細(xì)介紹了用C語(yǔ)言實(shí)現(xiàn)三子棋，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下2022-06-06
這篇文章主要介紹了詳解C++中的菱形繼承問(wèn)題,在多繼承結(jié)構(gòu)中，存在著很多問(wèn)題，比如從不同基類中繼承了同名成員，派生類中也定義了同名成員，這種二義性問(wèn)題很好解決，加上要訪問(wèn)的基類的類名限制就可以了,需要的朋友可以參考下2023-08-08
這篇文章主要介紹了如何利用Matlab實(shí)現(xiàn)山脊圖的繪制，文中的示例代碼講解詳細(xì)，對(duì)我們學(xué)習(xí)Matlab有一定的幫助，需要的可以參考一下2022-05-05