青蛙跳台阶(递归)

简介: 青蛙跳台阶(递归)

首先考虑最简单的情景


青蛙一次可跳一个或两个台阶 台阶总数用N表示


当N=1时,

此时只有一种跳法,只能跳一个台阶


当N=2时,

此时有两种跳法,一次跳两个台阶或者跳两次一个台阶


当N=3时,

1.先跳一个台阶,接下来就是N=2的跳法;

2.先跳两个台阶,接下来就是N=1的跳法。

跳法总数:(N=1)+(N=2)


当N=4时,

1.先跳一个台阶,接着就是N=3的跳法;

2.先跳两个台阶,接着就是N=2的跳法

跳法总数:(N=3)+(N=2)



以此类推

当N=n时,

1.先跳一个台阶,接着就是N=n-1的跳法;

2.先跳两个台阶,接着就是N=n-2的跳法

跳法总数:(N=n-1)+(N=n-2)

#include<stdio.h>
int my_jumpsteps(int n)
{
  //先进行台阶数的判断
  if (1 == n)
  {
    return 1;
  }
  if (2 == n)
  {
    return 2;
  }
  if (n > 2)
  {
    //进行递归
    return my_jumpsteps(n - 1) + my_jumpsteps(n - 2);
  }
}
int main()
{
  //台阶总数
  int n = 0;
  scanf("%d", &n);
  //调用函数
  int ret = my_jumpsteps(n);
  printf("%d\n", ret);
  return 0;
}


情景变得复杂一些时,青蛙一次可跳三个台阶时


当N=1时,

此时只有一种跳法,只能跳一个台阶


当N=2时,

此时有两种跳法,一次跳两个台阶或者跳两次一个台阶。

跳法总数:2


当N=3时,

1.先跳一个台阶,接下来就是N=2的跳法;

2.先跳两个台阶,接下来就是N=1的跳法;

3.可一次跳三个台阶

跳法总数:(N=2)+(N=1) + 1=4


当N=4时,

1.先跳一个台阶,接着就是N=3的跳法;

2.先跳两个台阶,接着就是N=2的跳法;

3.先跳三个台阶,接着就是N=1的跳法;

跳法总数:(N=3)+(N=2)+(N=1)


当N=5时

1.先跳一个台阶,接着就是N=4的跳法;

2.先跳两个台阶,接着就是N=3的跳法;

3.先跳三个台阶,接着就是N=2的跳法;

跳法总数:(N=4)+(N=3)+(N=2);



以此类推

当N=n时

1.先跳一个台阶,接着就是N=n-1的跳法;

2.先跳两个台阶,接着就是N=n-2的跳法;

3.先跳三个台阶,接着就是N=n-3的跳法;

跳法总数:(N=n-1)+(N=n-2)+(N=n-3)

#include<stdio.h>
int my_jumpsteps(int n)
{
  //先进行台阶数的判断
  if (1 == n)
  {
    return 1;
  }
  if (2 == n)
  {
    return 2;
  }
  if (3 == n)
  {
    return 4;
  }
  if (n > 3)
  {
    //进行递归
    return my_jumpsteps(n - 1) + my_jumpsteps(n - 2) + my_jumpsteps(n - 3);
  }
}
int main()
{
  //台阶总数
  int n = 0;
  scanf("%d", &n);
  //调用函数
  int ret = my_jumpsteps(n);
  printf("%d\n", ret);
  return 0;
}


情景更加复杂时

青蛙一次可跳m个台阶

当N=1时,

此时只有一种跳法,只能跳一个台阶


当N=2时,

此时有两种跳法,一次跳两个台阶或者跳两次一个台阶。

跳法总数:2


当N=3时,

1.先跳一个台阶,接下来就是N=2的跳法;

2.先跳两个台阶,接下来就是N=1的跳法;

3.可一次跳三个台阶

跳法总数:(N=2)+(N=1) + 1=4


当N=4时,

1.先跳一个台阶,接着就是N=3的跳法;

2.先跳两个台阶,接着就是N=2的跳法;

3.先跳三个台阶,接着就是N=1的跳法;

4.可一次跳四个台阶

跳法总数:(N=3)+(N=2)+(N=1)+1



当N=m+1时

跳法总数:(N=m)+(N=m-1)…+(N=1)



当N=n时

跳法总数:(N=n-1)+(N=n-2)+…+(N=n-m)


#include<stdio.h>
int my_jumpsteps(int n)
{
  //先进行台阶数的判断
  if (1 == n)
  {
  return 1;
  }
  if (2 == n)
  {
  return 2;
  }
  .......
  if (n > k)
  {
  //进行递归
  return my_jumpsteps(n - 1) + my_jumpsteps(n - 2) + my_jumpsteps(n - 3) + .... + my_jumpsteps(n - k);
  }
}
int main()
{
  //台阶总数
  int n = 0;
  scanf("%d", &n);
  //调用函数
  int ret = my_jumpsteps(n);
  printf("%d\n", ret);
  return 0;
}

目录
相关文章
|
6月前
|
Java Python
汉诺塔递归问题,递归思路详解
汉诺塔递归问题,递归思路详解
92 0
汉诺塔 递归问题
汉诺塔 递归问题
82 0
递归问题的实际运用:汉诺塔问题
递归问题的实际运用:汉诺塔问题
109 0
递归问题的实际运用:汉诺塔问题
|
机器学习/深度学习 算法 C语言
函数递归+青蛙跳台阶——“C”
函数递归+青蛙跳台阶——“C”
|
C语言
你是真的“C”——函数递归详解青蛙跳台阶
手把手教学——函数递归详解汉诺塔+青蛙跳台阶问题
109 0
你是真的“C”——函数递归详解青蛙跳台阶
|
C语言
【C】青蛙跳台阶和汉诺塔问题(递归)
【C】青蛙跳台阶和汉诺塔问题(递归)
122 0
【C】青蛙跳台阶和汉诺塔问题(递归)
【递归】青蛙跳台阶的变式题你还会吗?
【递归】青蛙跳台阶的变式题你还会吗?
123 0
【递归】青蛙跳台阶的变式题你还会吗?