青蛙跳臺階遞回問題的解釋與延申
題意說明
一只青蛙可以一次跳 1 級臺階或一次跳 2 級臺階,例如:跳上第一級臺階只有一種跳法:直接跳 1 級即可，跳上兩級臺階,有兩種跳法: 每次跳 1 級,跳兩次; 或者一次跳 2 級.問要跳上第 n 級臺階有多少種跳法?
解題思路
我們設臺階數位N;
當N=1時，當然只有1種跳法；
當N=2時，青蛙可以跳2次1層和跳1次2層；
當N=3時，當有3層臺階時，青蛙可以選擇先跳1層，剩下2層臺階，所以此時就是有2層臺階時的跳法，有2種；當青蛙選擇第一次跳2層臺階時，剩下1層臺階，此時有1層臺階時的跳法，所以3層臺階時的方法是：2層臺階的方法 + 1層臺階的方法，
當N=4時，具體跳法為: 1、先跳1層 若先跳1層，則剩下3層，接下來就是3層臺階的跳法， 2、先跳2層 若先跳2層，則剩下2層，接下倆就是2層臺階的跳法，所以4層臺階的方法為：3層臺階的方法+2層臺階的方法，
以此類推，當N=n時，n層臺階的方法為: n-1層臺階的方法+ n-2 層臺階的方法，
#include<stdio.h>
int frog(int n)
{
if(n == 1)
{
return 1;
}
if(n == 2)
{
return 2;
}
return frog(n-1) + frog(n-2);
}
int main()
{
int n;
scanf("%d",&n);
int ways = frog(n);
printf("%d\n",ways);
return 0;
}
問題的延申
接下來，我們把游戲的規則做一點小小的改動，我們讓青蛙一次可以跳多個臺階（大于2），那么這個遞回問題又會變成什么樣呢？
首先我們讓青蛙一次可以跳3個臺階
當N=1時，有1種方法；
當N=2時，有2種方法；
當N=3時，青蛙可以選擇第一步先跳1個臺階或者2個臺階或者3個臺階，有（1，1，1），（1，2），（2，1），（3）四種方法；
當N=4時，青蛙選擇第一步跳1層時，剩下3個臺階則時n=3時的方法；
青蛙第一步選擇跳2層時，剩下2個臺階則是n=2時的方法；青蛙第一步選擇跳3層時，剩下一個臺階則是n=1時的方法；所以當n=4時的所有方法為： n=3的所有方法 + n=2的所有方法 + n=1的所有方法；
以此類推，當N=n時，n層臺階的方法為：n-1 層的方法 + n-2 層的方法 + n-3 的方法；
#include<stdio.h>
int frog(int n)
{
if(n == 1)
{
return 1;
}
if(n == 2)
{
return 2;
}
if(n==3)
{
return 4;
}
return frog(n-1) + frog(n-2) + frog(n-3);
}
int main()
{
int n;
scanf("%d",&n);
int ways = frog(n);
printf("%d\n",ways);
return 0;
}
我們再繼續向下延申，若青蛙一次可以跳k層臺階呢？
很顯然，經過上面的討論，這個問題已經變得不那么復雜了，我們只需要計算出青蛙在跳 1 層臺階一直到青蛙跳 k 層臺階分別有多少種方法，再利用遞回，就會輕而易舉的得到結果，
int frog(int n, int k)
{
if(n == 1)
{
return 1;
}
if(n == 2)
{
return 2;
}
.......
.......
if(n == k)
{
return ?//跳 k 層臺階時的方法
}
return frog(n-1) + frog(n-2)+ ........+frog(n-k);
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/252036.html
標籤：其他
上一篇：杭電oj2021 C++
下一篇：蒜頭君的數字游戲