文章目錄
- 青蛙跳臺階一
- 青蛙跳臺階二
- 青蛙跳臺階三
青蛙跳臺階一
問題描述: 一只青蛙一次可以跳上1級臺階，也可以跳上2級，求該青蛙跳上一個n級的臺階
總共有多少種跳法（先后次序不同算不同的結果）
如果n=1，只有一種跳法，那就是1
如果n=2，那么有兩種跳法，2，[1,1]
如果n=3，那么有三種跳法，[1,1,1],,[1,2],[2,1]
如果n=4，那么有五種跳法，[1,1,1,1],[1,1,2],[1,2,1],[2,1,1],[2,2]
如果n=5，那么有八種跳法，[1,1,1,1,1],[1,1,1,2],[1,1,2,1],[1,2,1,1],[2,1,1,1],[2,2,1],[2,1,2],[1,2,2]
結果為1，2，3，5，8 這不正是斐波那契數列嘛
問題就轉換成了求解斐波那契數列，下面給出遞回和非遞回兩種函式實作.
遞回求解
int jump(int n)
{
if (n == 0 || n == 1 || n == 2)
return n;
else
{
return jump(n - 1) + jump(n - 2);
}
}
非遞回求解
int jump(int n)
{
if (n == 0 || n == 1 || n == 2)
{
return n;
}
int a = 1;
int b = 2;
int c = 3;
while (n > 2)
{
c = a + b;
a = b;
b = c;
n--;
}
return c;
}
青蛙跳臺階二
問題描述: 一只青蛙一次可以跳上1級臺階，也可以跳上2級……它也可以跳上n級，求該青
蛙跳上一個n級的臺階總共有多少種跳法，
問題分析:
f(n) = f(n-1) + f(n-2) + f(n-3) + … + f(n-(n-1)) + f(n-n)= f(0) + f(1) + f(2) + f(3) + … + f(n-2)+f(n-1)
f(n-1) = f(0) + f(1)+f(2)+f(3) + … + f((n-1)-1) = f(0) + f(1) + f(2) + f(3) + … + f(n-2)
so f(n)=2*f(n-1)
函式實作
int jump(int n)
{
if (n == 0 || n == 1 || n == 2)
{
return n;
}
else
{
return 2 * jump(n - 1);
}
}
青蛙跳臺階三
問題描述: 一只青蛙一次可以跳上1級臺階，也可以跳上2級……它也可以跳上m級，求該
青蛙跳上一個n級的臺階總共有多少種跳法
問題分析:
f(n) = f(n-1) + f(n-2) + f(n-3) + … + f(n-m)
f(n-1) = f(n-2) + f(n-3) + … + f(n-m) + f(n-m-1)
化簡得：f(n) = 2f(n-1) - f(n-m-1)
函式實作
int jump(int m,int n)
{
if (n > m)
{
return 2 * jump(m, n - 1) - jump(m, n - m - 1);
}
// n <= m時跟問題二的解法相同
else
{
if (n == 0 || n == 1 || n == 2)
{
return n;
}
else
{
return 2 * jump(m, n - 1);
}
}
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/ruanti/251811.html
標籤：其他
下一篇：C語言編程＞第二十周 ② 下列給定程式中，函式fun的功能是：求出陣列中最大數和次最大數，并把最大數和b[0]中的數對調、次最大數和b[1]中的數對調。