经典递归 – 青蛙跳台阶问题

这是我参加11月更文应战的第13天,活动概况检查:2021最终一次更文应战」


最近,想温习一下C言语,所以笔者将会在每天更新一篇关于C言语的文章! 各位初学C言语的大一重生,以及想要温习C言语/C++常识的不要错过哦! 夯实基础,慢下来便是快!


标题要求:

一只青蛙一次能够跳上1级台阶,也能够跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法(先后次序不同算不同的成果)

->可认为是斐波那契数列


思路

状况1:假如只要一级台阶:显然只要一种跳法
状况2:假如有2级台阶,那么就有两种跳法。一种是分两次跳。每次跳1级,另一种就算一次跳2级
状况3:假如台阶级数大于2,设为n的话。这时咱们把n级台阶时的跳法当作时n的函数,记为f(n) ,第一次跳的时候有两种不同的挑选:一是第一次跳1级,此时的跳法的数目等于后边剩余的n-1级台阶的跳法数目,即为f(n-1),二是第一次跳2级,此时跳法的数目等于后边剩余的n-2级台阶的跳法数目,即为f(n-2),因而n级台阶的不同跳法的总数为:f(n) = f(n-1) + f(n-2),不难看出便是斐波那契数列。


数学函数表达式:

经典递归 - 青蛙跳台阶问题

根据上面的函数,咱们能够很容易写出代码!

#include<stdio.h>
int Frog_Step(int n)
{
    if(n == 0)
    return 0;
    else if(n == 1)
    return 1;
    else if(n == 2)
    return 2;
    else
    return Frog_Step(n-1)+Frog_Step(n-2);
}
int main()
{
    int n = 0;
    scanf("%d",&n);
    int ret = Frog_Step(n);
    printf("%dn",ret);
}

延申1: 一次能够跳3个台阶

首要咱们让青蛙一次能够跳3个台阶
1.当N=1时,有1种办法;
2.当N=2时,有2种办法;
3.当N=3时,青蛙能够挑选第一步先跳1个台阶或许2个台阶或许3个台阶,有(1,1,1),(1,>2),(2,1),(3) 共四种办法;
4.当N=4时,青蛙挑选第一步跳1层时,剩余3个台阶则时n=3时的办法; 青蛙第一步挑选跳2层时,剩>下2个台阶则是n=2时的办法;
青蛙第一步挑选跳3层时,剩余一个台阶则是n=1时的办法;
所以当n=4时的一切办法为: n=3的一切办法 + n=2的一切办法 + n=1的一切办法; 以此类推,当>N=n时,n层台阶的办法为:n-1 层的办法 + n-2 层的办法 + n-3 的办法;



//一次跳3个台阶
#include<stdio.h>
int frog(int n)
{
   if(n == 1)
   {
      return 1;
   }
   if(n == 2)
   {
      return 2;
   }
   if(n==3)
   {
      return 4;
   }
   return frog(n-1) + frog(n-2) + frog(n-3);
}
int main()
{
   int n;
   scanf("%d",&n);
   int ways = frog(n);
   printf("%dn",ways);
   return 0;
}

延申2:一次能够跳k层台阶

咱们再持续向下延申,若青蛙一次能够跳k层台阶呢?

很显然,通过上面的讨论,这个问题已经变得不那么杂乱了,咱们只需要计算出青蛙在跳 1 层台阶一>直到青蛙跳 k 层台阶别离有多少种办法,再利用递归,就会垂手可得的得到成果。

int frog(int n, int k)
{
   if(n == 1)
   {
      return 1;
   }
   if(n == 2)
   {
      return 2;
   }
   .......
   .......
   if(n == k)
   {
      return ?//跳 k 层台阶时的办法
   }
   return frog(n-1) + frog(n-2)+ ........+frog(n-k);
}

今天就先到这吧~感谢你能看到这里!希望对你有所帮助!欢迎老铁们点个关注订阅这个专题! 同时欢迎大佬们批评指正!

发表回复

提供最优质的资源集合

立即查看 了解详情