【C语言】青蛙跳台阶(两种青蛙跳)

简介: 【C语言】青蛙跳台阶(两种青蛙跳)

前言

🎈大家好,我是何小侠🎈

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

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

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

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

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


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

🍊

青蛙跳台阶(常见版本)🍊

规则:

有一只很厉害的青蛙一次可以跳上 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;
}

总结🍊

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

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

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


目录
相关文章
|
2月前
|
存储 编译器 C语言
爱上C语言:函数递归,青蛙跳台阶图文详解
爱上C语言:函数递归,青蛙跳台阶图文详解
|
8月前
|
C语言
【C语言刷题】青蛙跳台阶
【C语言刷题】青蛙跳台阶
109 1
|
9月前
|
C语言
【C语言实现青蛙跳台阶问题】
【C语言实现青蛙跳台阶问题】
24 0
|
28天前
|
算法 C语言
C语言实现青蛙跳台阶问题
C语言实现青蛙跳台阶问题
26 5
|
2月前
|
C语言
C语言递归问题【青蛙跳台阶】和【汉诺塔】
C语言递归问题【青蛙跳台阶】和【汉诺塔】
|
2月前
|
C语言
【C语言】青蛙跳台阶 —— 详解
【C语言】青蛙跳台阶 —— 详解
|
2月前
|
C语言 索引
【C语言】C语言⻘蛙跳台阶问题--递归问题
【C语言】C语言⻘蛙跳台阶问题--递归问题
|
4天前
|
存储 缓存 C语言
【C语言】字符函数,字符串函数,内存函数
C语言中的字符串函数和内存函数
11 0
【C语言】字符函数,字符串函数,内存函数
|
10天前
|
C语言
C语言5 字符输出函数和格式输出函数
C语言5 字符输出函数和格式输出函数
15 1
|
12天前
|
算法 编译器 C语言
深入浅出C语言—【函数】下
深入浅出C语言—【函数】下