递归问题闲究——青蛙跳台阶 _跳台阶

知识就是力量，时间就是生命。这篇文章主要讲述递归问题闲究——青蛙跳台阶相关的知识，希望能为你提供帮助。
今天继续来为我的懒狗行为买单。

文章图片

继汉诺塔问题之后，接下来就是青蛙跳台阶问题：?一只青蛙一次可以跳上1级，也可以跳上2级，求该青蛙跳上一个n级的台阶总共有多少种跳法。刚开始感觉像是在算阶乘，因为先后次序不同算不同的结果嘛；细想就发现我格局低了，这题其实很有意思。
那么我们先分析一下，我青蛙只能跳1或2级，一级台阶只有一种；跳二级时，可跳两次一级或跳一次二级；跳3级时，跳一个二级和一个一级，即二级台阶跳法+一级台阶跳法；跳四级时，先跳一级后，剩三级台阶；或先跳两级，剩二级台阶，可能性就是三级台阶跳法＋二级台阶跳法……
（综上所述，当跳n级台阶时，我们就需执行（n-1）级和（n-2）级台阶跳法），最后把这个思路放入递归，如下：

#include< stdio.h>
int Frog(int n)
{
if (n == 1)
{
return 1;
}
if (n == 2)
{
return 2;
}
return Frog(n - 1) + Frog(n - 2);

}

int main()
{
int n = 0;
printf("please input the number of steps:");
scanf("%d", & n);
int num = Frog(n);
printf("%d\\n", num);

return 0;
}

结果如下：
【递归问题闲究——青蛙跳台阶】

文章图片

当然这只是针对的是初识步数对应为n =1或n=2时，我们继续深入思考一下，当n更大时，n=3,4,5，……，m 时又该怎么办呢？这时候我们可以把函数再补充一下。

#include< stdio.h>
int Frog(int n,int m)
{
if (n == 1)
{
return 1;
}
if (n == 2)
{
return 2;
}
if (n == 3)
{
return 4;
}
……
……
if(n==m)
{
return ?；//(跳m级台阶方案)
}
Frog(n-1)+Frog(n-2)+Frog(n-3)+……+Frog(n-m)；
}