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

这个问题经常在各类面试中看到。一只青蛙一次可以跳上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)数

斐波那契数代码
#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;
}#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……虽说规律相同,但是不一样!!!
有什么问题各位大佬评论谢谢!!!
