前言

🎈大家好，我是何小侠🎈

🌀大家可以叫我**小何或者小侠🌀**

🔴我是一名普通的博客写作者🔴

💐希望能通过写博客加深自己对于学习内容的理解💐

🌸也能帮助更多人理解和学习🌸

🍃我的主页:何小侠的主页🍃

这篇博客我们一起来学习青蛙跳台阶问题，也就是递归。希望大家能有所收获。

🍊

青蛙跳台阶（常见版本）🍊

规则：

有一只很厉害的青蛙一次可以跳上 1 级台阶，也可以跳上 2 级台阶。求该青蛙跳上一个 n 级的台阶总共有多少种跳法。

我们遇到这种问题还是需要找规律

很明显，我们能发现一些规律

我们假设 f ( n )就是跳上 n 级阶梯的方法，我们知道青蛙第一步只能跳1级或二级，

那么我们是不是可以推出 f ( n ) = f（n -1 ）+ f (n -2)。

f ( n-1 )就是先跳1级后剩下n-1级的跳法，f ( n-2 )就是先跳2级后剩下n-2级的跳法.

或者说我们也可以得到

当我们的阶数为 n = 3 的时候，也就是 f( 3 ) = f (n - 1) + f (n - 2 ),这样是不是更清楚呢？

所以我们可以得到：

这就是我们最后得出的公式。其实就是一个变种的斐波那契数列。

代码

#include<stdio.h>
int  f(int n)
{
  if (1 == n)
    return 1;
  else if (2 == n)
    return 2;
  else if (n > 2)
  {
    return f(n - 1) + f(n - 2);
  }
}
int main()
{
  int n = 0;
  printf("请输入你想累死青蛙的阶数\n");
  scanf("%d", &n);
  printf("青蛙要跳%d次\n",f(n));
  return 0;
}

青蛙跳台阶（另外版本）🍊

规则：

有一只青蛙，它是青蛙中战斗机，青蛙中的博尔特，它一次可以跳上一级台阶，也可以跳上二级台阶······也可以跳n级，求该青蛙跳上一个n级的台阶总共需要多少种跳法。

这个思路其实要和上面的一般版本青蛙跳结合一下。

我们看到它的第一步跳法如上所示，它既可以跳1级，也可以2级，也可以3级·····甚至直接跳到终点。

假设我们还是设f ( n ) 为 n 跳上n级台阶的跳法。 那么 f ( n ) = f (n -1) + f ( n -2 ) + ······f ( 2 ) + f ( 1 ) +f ( 0 ).

我们在上一个青蛙跳版本说过，如果青蛙一次只能跳1或2级，那么f ( n ) =f ( n -1)+ f (n-2 ),而在这个版本不就是一个思路吗？青蛙的跳越的能力提升了，那么我们的等式也应该变长！

再来看看这个等式 f ( n ) = f (n -1) + f ( n -2 ) + ······f ( 2 ) + f ( 1 ) +f ( 0 ).
如果青蛙第一次跳1级那么剩下的级数就是n-1,
也就是说剩下f ( n-1)种跳法，
那么青蛙如果一次跳n-1级，
那么最后剩下的一级就是n阶级,也就是f (1),
最后f (0)就是我们的青蛙最厉害的时候，直接从地面跳到终点，
那么f (0)当然就==1了；

我们还是把我们的分析写成表格更好大家理解。

因为我们已经换了一直青蛙了，就那4 阶数举例吧。青蛙先跳1级剩下的就是f ( 3 )种跳法，先跳2级就是f ( 2 )，······最后就是直接从地面跳到终点就是 f ( 0 )就是 1种跳法。

最后我们要推出这个递归条件！

我们知道

f ( n ) = f (n -1) + f ( n -2 ) + ······f ( 2 ) + f ( 1 ) +f ( 0 ).

f (n -1 ) = f ( n -2 ) + ······f ( 2 ) + f ( 1 ) +f ( 0 ).

所以

f ( n = f( n -1 ) + f( n -1 ) = 2 * f （n -1）.

代码🍊

#include<stdio.h>
int  f(int n)
{
  if (n < 3)
    return n;
  else if (n > 2)
  {
    return 2 * f(n - 1);
  }
}
int main()
{
  int n = 0;
  printf("请输入你想累死青蛙的阶数\n");
  scanf("%d", &n);
  printf("青蛙要跳%d次\n",f(n));
  return 0;
}

总结🍊

这篇博客我们介绍了斐波那契数列的变种两个青蛙跳问题，我们不仅能从中学到数学思维和表达，也能加强我们的递归理解和能力

最后如果这篇博客有帮助到你,欢迎点赞关注加收藏

如果本文有任何错误或者有疑点欢迎在评论区评论