经典递归 - 青蛙跳台阶问题

最近，想复习一下C语言，所以笔者将会在掘金每天更新一篇关于C语言的文章！ 各位初学C语言的大一新生，以及想要复习C语言/C++知识的不要错过哦！ 夯实基础，慢下来就是快！

题目要求：

一只青蛙一次可以跳上1级台阶,也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法(先后次序不同算不同的结果)

->可认为是斐波那契数列

思路

情况1：如果只有一级台阶：显然只有一种跳法
情况2：如果有2级台阶，那么就有两种跳法。一种是分两次跳。每次跳1级，另一种就算一次跳2级
情况3：如果台阶级数大于2，设为n的话。这时我们把n级台阶时的跳法看成时n的函数，记为f(n)
，第一次跳的时候有两种不同的选择：一是第一次跳1级，此时的跳法的数目等于后面剩下的n-1级台阶的跳法数目，即为f(n-1)，二是第一次跳2级，此时跳法的数目等于后面剩下的n-2级台阶的跳法数目，即为f(n-2)，因此n级台阶的不同跳法的总数为：f(n) = f(n-1) + f(n-2)，不难看出就是斐波那契数列。

数学函数表达式：

根据上面的函数，我们可以很容易写出代码！

#include<stdio.h>
int Frog_Step(int n)
{
    if(n == 0)
    return 0;
    else if(n == 1)
    return 1;
    else if(n == 2)
    return 2;
    else
    return Frog_Step(n-1)+Frog_Step(n-2);
}
 
int main()
{
    int n = 0;
    scanf("%d",&n);
    int ret = Frog_Step(n);
    printf("%d\n",ret);
}

延申1： 一次可以跳3个台阶

首先我们让青蛙一次可以跳3个台阶
1.当N=1时，有1种方法；
2.当N=2时，有2种方法；
3.当N=3时，青蛙可以选择第一步先跳1个台阶或者2个台阶或者3个台阶，有（1，1，1），（1，>2），（2，1），（3） 共四种方法；
4.当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 的方法；

//一次跳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;
}

延申2：一次可以跳k层台阶

我们再继续向下延申，若青蛙一次可以跳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);
}

今天就先到这吧~感谢你能看到这里！希望对你有所帮助！欢迎老铁们点个关注订阅这个专题！ 同时欢迎大佬们批评指正！