目錄
- 傳統藝能????
- 過渡區????
- 正片開始????
- 描述????
- 分析????
- 實作????
- 格局打開????
傳統藝能????
小編是大一菜鳥不贅述，歡迎大佬指點江山
此前部落格點我！點我！請搜尋部落客 【知曉天空之藍】點我！點我！請搜尋部落客 【知曉天空之藍】或掃碼進入！
喬喬的gitee代碼庫（打灰人 ）歡迎通路，點我！
(https://blog.51cto.com)感謝支援！
過渡區????
現在是中原標準時間13:03，隻有下午有節英語課，昨晚看遞歸的題看到一點過，
是以早上起來精神狀态不是很好就磨到現在才來寫。今天早上沒有遵守早期條約，把鬧鐘咕了，心情有點五味陳雜……
正片開始????
描述????
繼漢諾塔問題之後，接下來就是青蛙跳台階問題：說一隻青蛙一次可以跳上1級，也可以跳上2級，求該青蛙跳上一個n級的台階總共有多少種跳法。剛開始感覺像是在算階乘，考慮先後次序不同算不同的結果嘛；看完才發現我格局低咯，這題其實蠻有意思。
分析????
不同的結果嘛；細想就發現我格局低了，這題其實很有意思。
那麼我們先分析一下，我青蛙隻能跳1或2級，一級台階隻有一種；跳二級時，可跳兩次一級或跳一次二級；跳3級時，跳一個二級和一個一級，即二級台階跳法+一級台階跳法；跳四級時，先跳一級後，剩三級台階；或先跳兩級，剩二級台階，可能性就是三級台階跳法＋二級台階跳法……
規律出來後其實不難發現和我們之前研究的斐波那契似乎有些淵源，但又有不同，我暫且稱它為特殊斐波那契數列，稍作對比：
斐波那契：
呱太：
實作????
知道原理和模型就不難了解問題的本質，接下來就是銜接與打磨。這裡我們先自義定一個 Frog函數來模拟情景：
#include<stdio.h>
int Frog(int n)
{
if (n == 1)
{
return 1;
}
if (n == 2)
{
return 2;
}
return Frog(n - 1) + Frog(n - 2);//大于2級台階就進入遞歸部分
}
int main()
{
int n = 0;
printf("please input the number of steps:");
scanf("%d", &n);
int num = Frog(n);//傳參開始計算
printf("%d\n", num);
return 0;
} 執行結果如下圖所示：（假設為6級台階）
格局打開????
以上隻是針對的是初始步數對應為n =1或n=2時，我們繼續深入思考一下，n更大時，n=3,4,5，……，m 時又該怎麼辦呢？當n = n 時，共有n種跳的方式，第一次跳出一階後，後面還有Fib(n-1)中跳法； 第一次跳出二階後，後面還有Fib(n-2)中跳法…第一次跳出n階後, 後面還有 Fib(n-n)中跳法.這時候我們可以把函數部分再補充一下如下：
#include<stdio.h>
int Frog(int n,int m)
{
if (n == 1)
{
return 1;
}
if (n == 2)
{
return 2;
}
if (n == 3)
{
return 4;
}
……
……
if(n==m)
{
return ?； //(跳m級台階方案)
}
Frog(n-1)+Frog(n-2)+Frog(n-3)+……+Frog(n-m)；
}