首页
学习
活动
专区
圈层
工具
发布
社区首页 >专栏 >【C语言】函数递归例子2青蛙跳台阶问题

【C语言】函数递归例子2青蛙跳台阶问题

作者头像
用户11290673
发布于 2024-09-25 11:40:07
发布于 2024-09-25 11:40:07
5480
举报
文章被收录于专栏:学习学习

 接下来我们来看一下第二个例子青蛙跳台阶

青蛙跳台阶问题

 这个问题经常在各类面试中看到。一只青蛙一次可以跳上1级台阶,也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法。是实践函数递归的典型问题


分析问题

我们先假设有n个台阶,如果n=1,那么只有一种跳法,如果n=2,那么就有两种跳法。如果n=3,若第一次跳一阶,那么第二次跳二阶,若第一次跳二阶,那么第二次跳一阶,有两种情况,因此跳三个台阶时相当于先分类再相加前两种情况

即跳三个台阶跳法=跳一个台阶跳法+跳两个台阶跳法。

所以当有n个台阶时,假如青蛙第一次跳了1个台阶,那么剩下了n-1个台阶;假如青蛙第一次跳了2个台阶,那么剩下了n-2个台阶

那我们是不是可以这么想跳n个台阶的跳法=跳n-1个台阶跳法+跳n-2个台阶跳法


近似斐波那契数

综上,我们可以把这种问题看成斐波那契数。

第n个数=第(n-1)数+第(n-2)数

斐波那契数代码

代码语言:javascript
复制
#define _CRT_SECURE_NO_WARNINGS 1
#include <stdio.h>
int run(int x)
{
	if (x <=2)
		return 1;
	else
	{
		return run(x- 1) + run(x - 2);
	}
}
int main()
{
	int n = 0;
	int m = 0;
	scanf("%d", &n);
	m=run(n);
	printf("%d", m);

	return 0;
}

青蛙跳台阶代码

代码语言:javascript
复制
#define _CRT_SECURE_NO_WARNINGS 1
#include <stdio.h>
int tiao(int n)
{
	if (n == 1)
	{
		return 1;
	}
	else if (n == 2)
	{
		return 2;
	}
	else if (n > 2)
	{
		return tiao(n - 1) + tiao(n - 2);//递归
	}

}
int main()
{
	printf("青蛙要跳几个台阶=>");
	int a = 0;
	scanf("%d", &a);
	printf("青蛙会有几种跳法=>");
	printf("%d", tiao(a));

}

注意:虽然斐波那契数和青蛙跳台阶很相似,但当n=2时,斐波那契数是1,而青蛙跳台阶是2种跳法,所以,从这里开始斐波那契数列是1,1,2,3……而青蛙跳台阶跳法排序是1,2,3,5……虽说规律相同,但是不一样!!!

有什么问题各位大佬评论谢谢!!! 

本文参与 腾讯云自媒体同步曝光计划,分享自作者个人站点/博客。
原始发表:2024-04-03,如有侵权请联系 cloudcommunity@tencent.com 删除
目录
  • 青蛙跳台阶问题
    • 分析问题
    • 近似斐波那契数
    • 青蛙跳台阶代码
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档