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

题目要求：

一只青蛙一次可以跳上 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);}

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