首页
学习
活动
专区
圈层
工具
发布
首页
学习
活动
专区
圈层
工具
MCP广场
社区首页 >专栏 >递归之青蛙跳台阶

递归之青蛙跳台阶

作者头像
凤年徐
发布2025-08-28 13:16:09
发布2025-08-28 13:16:09
10000
代码可运行
举报
文章被收录于专栏:代码飞升代码飞升
运行总次数:0
代码可运行

递归之青蛙跳台阶问题

1.递归思想

把⼀个⼤型复杂问题层层转化为⼀个与原问题相似,但规模较⼩的⼦问题来求解;直到⼦问题不能再 被拆分,递归就结束了。所以递归的思考⽅式就是把⼤事化⼩的过程。

2.递归限制

• 递归存在限制条件,当满⾜这个限制条件的时候,递归便不再继续。

• 每次递归调⽤之后越来越接近这个限制条件。 在下⾯的例⼦中,我们逐步体会这2个限制条件。

3.什么是青蛙跳台阶问题

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

4.思路分析

我们先从n=1开始分析,不难得到以下表格

n

跳法数

1

1

2

2

3

3

4

5

能否从中看出一些规律呢,如果不好观察,那请看下表

n

跳法数

1

1

2

2

3

3

=1+2

4

5

=2+3

当n=4时,青蛙第一次可以跳一次也可以跳两次

在这里插入图片描述
在这里插入图片描述

青蛙跳一次时,可以把此当作新的起点,那么在该条件下就有3种跳法

同理青蛙跳两次时,就有两种跳法

总共是2+3,也就是五种

由此我们可以得出递推关系:

在这里插入图片描述
在这里插入图片描述

其实就是斐波那契数列

5.代码实现

代码语言:javascript
代码运行次数:0
运行
复制
#include<stdio.h>
int Jump(int n)
{
 if(n==1)
 return 1;
 else if(n==2)
 return 2;
 else
  return Jump(n-1)+Jumo(n-2);
}
int main()
{
    int m = 0;
    scanf("%d", &m);
    int ret = Jump(m);
    printf("%d", ret);
    return 0;
}

结语

⭐️各位看官,你们的点赞就是我最大的动力,下一篇讲汉诺塔问题

本文参与 腾讯云自媒体同步曝光计划,分享自作者个人站点/博客。
原始发表:2025-04-09,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • 递归之青蛙跳台阶问题
    • 1.递归思想
    • 2.递归限制
    • 3.什么是青蛙跳台阶问题
    • 4.思路分析
    • 5.代码实现
  • 结语
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档