C語言解決青蛙跳臺階問題(升級版)
1. 基礎問題
題目描述
一隻青蛙一次可以跳上 1 級臺階，也可以跳上 2 級。求該青蛙跳上一個 n 級的臺階總共有多少種跳法。
諾，就像下面這樣
解題思路
其實我一看到這道題，我也是懵的，不知道從哪裡著手分析，那我們就從最簡單的情況開始分析。
假如 n = 1，一共有一級臺階，顯然就隻有一種跳法
一次跳1階；
假如 n = 2，一共有兩級臺階，共有兩種跳法
跳1階，再跳1階
跳2階
假設n = 3，共有三種跳法。
跳1階，跳1階，再跳1階
跳1階，再跳2階
跳2階, 再跳1階
（註：此過程圖是我從網上找的，實在是難得畫啦）
通過上面的分析，我們可以這樣思考問題
前往樓梯頂部的最後一步，要麼跳1階，要麼跳2階；
先假設f(n)為 n 級臺階的總跳法數；
那麼第一次如果選擇跳一級的話，剩下的 n-1 級臺階的跳法數就為f(n−1)。
如果第一次跳兩級的話，剩下的 n-2 級臺階的跳法就是f(n−2)；
現在青蛙一次隻能跳一級或兩級，所以我們可以推出以下公式：
咦，這玩意兒不就是我們 斐波那契數 嗎？
隻不過有一點不同的是，斐波那契數列一般是以1,1,2,3,5,8,13……開始的；
而我們這是以1,2,3,5,8,13……開始的，少瞭最前面的一個1。
代碼實現
上面說到這個過程有點類似於斐波那契數，但又不完全是，所以我們先看主代碼部分
#include <stdio.h>
int jump(int n)
{
if (n < 3)
{
//假設n的范圍是[0, 3]
return n;
}
else
{
//n>3的時候
return jump(n - 1) + jump(n - 2);
}
}
int main()
{
int num = 0;
printf("請輸入一個臺階數:> ");
scanf("%d", &num);
int ret = jump(num);
printf("小青蛙有 %d種 跳法\n", ret);
return 0;
}
運行結果
但是，我們來看一下計算的過程
要計算f(6)，就需要先計算出子問題f(5)和f(4)
然後要計算f(5)，又要先算出子問題f(4)和f(3)，以此類推。
一直到f(2)和f(1)，遞歸樹才終止。
因此，青蛙跳階，遞歸解法的時間復雜度 等於O(1) * O(2ⁿ)=O(2ⁿ)
你仔細觀察這顆遞歸樹，你會發現存在「大量重復計算」；
比如f(4)被計算瞭兩次，f(3)被重復計算瞭3次…所以這個遞歸算法低效的原因，就是存在大量的重復計算！
所以我們可以對代碼進行優化
遞歸升級
在遞歸法的基礎上，新建一個長度為n的數組，用於在遞歸時存儲f(0)至f(n) 的數字值，重復遇到某數字時則直接從數組取用，避免瞭重復的遞歸計算。
所以我們設置一個數組，用於存放第一次計算某一個n的jump(n)。
當每一次要計算一個jump(n)的時候，就先查看數組中以n為下標的地方是否有值，有的話就可以不調用jump(n)，而直接從數組中取得結果值，否則再計算jump(n)。
代碼實現
#include <stdio.h>
long int f[1000]={0};
int jump(int n){
//當隻有一階臺階的時候，隻有一種上臺階的方式。
//當有2階臺階的時候，有2種上臺階的方式，一種是一次上一階，還有一種是一次上2個臺階。
//現在設有n階臺階,如果n>2,那種應該有（先跳一階）+（先跳2階）的方式
//如果先跳一階，那麼就有jump(n-1)中方式。如果先跳2階，那麼就有jump(n-2)中方式。
//因此可以知道共有jump(n-1) + jump(n-2)種方式。
if(n==1)
{
f[1]=1;
return f[1];
}
if(n==0)
{
f[0]=1;
return f[0];
}
if(n==2)
{
f[2]=2;
return f[2];
}
else
{
if(f[n-1]!=0)
{
if(f[n-2]!=0)
{
return (f[n-1]+f[n-2]);
}
else
{
f[n-2]=jump(n-2);
return (f[n-1]+f[n-2]);
}
}
else
{
if(f[n-2]!=0)
{
f[n-1]=jump(n-1);
return (f[n-1]+f[n-2]);
}
else
{
f[n-1]=jump(n-1);
f[n-2]=jump(n-2);
return (f[n-1]+f[n-2]);
}
}
}
}
int main()
{
int num = 0;
printf("請輸入一個臺階數:> ");
scanf("%d", &num);
int ret = jump(num);
printf("小青蛙有 %d種 跳法\n", ret);
return 0;
}
運行結果
動態規劃解法
很快我又發現，不必把所有的記錄都記起來；
假設我有3階樓梯，我隻需要知道跳2階和跳1階的方法數是多少就可以算出跳3階的方法數；
因此每次隻需要保留n−1階和n−2階的方法數。
代碼實現
#include <stdio.h>
int jump(int n)
{
//n=0、1、2的時候,直接返回n即可
if (n < 3)
{
return n;
}
//第一個數為1
int one = 1;
//第二個數為2
int two = 2;
//用於存放前兩個數之和
int sum = 0;
while (n > 2)
{
sum = one + two;
one = two;
two = sum;
n--;
}
return sum;
}
int main()
{
int num = 0;
printf("請輸入一個臺階數:> ");
scanf("%d", &num);
int ret = jump(num);
printf("小青蛙有 %d種 跳法\n", ret);
return 0;
}
運行結果
2. 問題升級
題目描述
一隻青蛙一次可以跳上一級臺階，也可以跳上二級臺階……，也可以跳n級，求該青蛙跳上一個n級的臺階總共需要多少種跳法。
解題思路
一隻青蛙要想跳到n級臺階，可以從一級，二級……，也就是說可以從任何一級跳到n級
當臺階為1級時，f(1)=1；
當臺階為2級時，f(2)=1+1=2；
當臺階為3級時，f(3)=f(1)+f(2)+1=4；
當臺階為4級時，f(4)=f(1)+f(2)+f(3)+1=8；
當臺階為5級時，f(5)=f(1)+f(2)+f(3)+f(4)+1=16；
所以遞推公式我們很容易就能想到:f(n)=f(n−1)+f(n−2)+……+f(2)+f(1)+f(0)
最後這個f(0)是可以去掉的，因為0級就相當於沒跳，所以f(0)=0
然後我們把f(0)去掉再轉換一下：f(n−1)=f(n−2)+f(n−3)+……+f(2)+f(1)；
推導過程
我們列兩個等式：
①f(n)=f(n−1)+f(n−2)+f(n−3)+…+f(2)+f(1)
②f(n−1)=f(n−2)+f(n−3)+…+f(2)+f(1)
由①-②得，f(n)=2f(n−1)
代碼實現
遞歸方法
代碼示例
int jump(int n)
{
if (n == 1)
{
return 1;
}
else
{
return 2 * jump(n - 1);
}
}
int main()
{
int num = 0;
printf("請輸入一個臺階數:> ");
scanf("%d", &num);
int ret = jump(num);
printf("小青蛙有 %d種 跳法\n", ret);
return 0;
}
運行結果
非遞歸方法
當然這裡也可以用非遞歸的方式來實現
那麼非遞歸怎麼去思考呢？
可以這樣理解：
然後使用用函數pow(2,n -1)，需要加頭文件<math.h>
但是我們這裡可以不用庫函數來實現，給大傢介紹一種神奇的運算
代碼示例
int jump(int n)
{
if (n == 1)
{
return 1;
}
else
{
return 1 << (n-1);
}
}
int main()
{
int num = 0;
printf("請輸入一個臺階數:> ");
scanf("%d", &num);
int ret = jump(num);
printf("小青蛙有 %d種 跳法\n", ret);
return 0;
}
運行結果
我這裡選擇用<<左移操作符來計算
3. 特性總結
其實這道算法題的本質可以說就是斐波那契數的衍生；
反言之，對於算法，我的理解：算法本質就是數學的解題過程
以上就是C語言解決青蛙跳臺階問題(升級版)的詳細內容，更多關於C語言青蛙跳臺階的資料請關註WalkonNet其它相關文章！