一只青蛙一次可以最多跳2級臺階，求青蛙跳上n級臺階有多種跳法？
當 n=1時，青蛙只有一種跳法；
當n=2時，青蛙有兩種跳法；
當n=3時，有三種跳法，我們可以先跳一級再跳1級；先跳1級，再跳1級；一級一級的跳；共三種跳法；
當n=4時，我們可以先跳一級臺階，再跳3級臺階；還有一種跳法是先跳2級臺階，再跳2級臺階；因為跳三級臺階有三種跳法，所以2+3=5；
當n=5時，我們可以先跳1級臺階，再跳4級臺階；先跳2級臺階，再跳3級臺階；總跳法為3級臺階+4級臺階的跳法；
當n=m的時候，總跳法為（n-1）級臺階的跳法+（n-2）級臺階的跳法；
得到公式：f(n)=f(n-1)+f(n-2)
代碼實作：
int Jump(int n)
{
if (n == 1)
{
return 1;
}
else if (n == 2)
{
return 2;
}
else
{
return Jump(n - 1) + Jump(n - 2);
}
}
int main()
{
int get = 0;
scanf("%d", &get);
int method=Jump(get);
printf("%d", method);
return 0;
}進階：一只青蛙一次可以最多跳m級臺階，求青蛙跳上n級臺階有多種跳法？
由第一個問題其實我們已經知道了這種問題的規律
假設m=3，那么當n>3時，f(n)=f(n-1)+f(n-2)+f(n-3);
假設m=h，那么當m>h時，f(n)=f(n-1)+f(n-2)+f(n-3)+，，，+f(n-h);
假設m=5，n=10；那么我們就要求臺階1到5的不同跳法，當n=3時，青蛙最多可以跳3級，當n=4時，青蛙做多可以跳4級臺階，那么對于求這些有個規律，n^2-1; 那么我們就可以更簡便的求結果了；
代碼實作：
int add(int n, int m)
{
int num = 0;
for (int i = 1; i <= m; i++)
{
if (n == i)
{
return pow(2, i- 1);
}
}
for (int i = 1; i <= m; i++)
{
num += add(n - i, m);
}
return num;
}
int main()
{
int n = 0;
int m = 0;
scanf("%d %d", &n, &m);
printf("%d", add(n, m));
return 0;
}代碼優化：
上述解法是用遞回的問題解決的，但是，使用遞回的辦法來解決效率不高，因為會有重復計算的問題，
因此我們可以用加法+迭代的方式進行計算，但是原理和上述解法一樣
代碼實作：
int main()
{
int get[101] = { 0 };
int a = 0;
int b = 0;
scanf("%d %d", &a, &b);
for (int i = 1; i <= b; i++)
{
*(get+i)=pow(2,i - 1);
}
for (int i = b+1; i <= a; i++)
{
for (int n = i-b; n <i; n++)
{
get[i] += get[n];
}
}
printf("%d", get[a]);
return 0;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/ruanti/413955.html
標籤：其他
上一篇：【Java資料結構】堆疊和佇列