青蛙跳台阶(递归)

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

首先考虑最简单的情景


青蛙一次可跳一个或两个台阶 台阶总数用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
汉诺塔递归问题,递归思路详解
汉诺塔递归问题,递归思路详解
81 0
汉诺塔 递归问题
汉诺塔 递归问题
81 0
递归问题的实际运用:汉诺塔问题
递归问题的实际运用:汉诺塔问题
104 0
递归问题的实际运用:汉诺塔问题
|
机器学习/深度学习 算法 C语言
函数递归+青蛙跳台阶——“C”
函数递归+青蛙跳台阶——“C”
|
C语言
【C】青蛙跳台阶和汉诺塔问题(递归)
【C】青蛙跳台阶和汉诺塔问题(递归)
122 0
【C】青蛙跳台阶和汉诺塔问题(递归)
|
C语言
你是真的“C”——函数递归详解青蛙跳台阶
手把手教学——函数递归详解汉诺塔+青蛙跳台阶问题
109 0
你是真的“C”——函数递归详解青蛙跳台阶
【递归】青蛙跳台阶的变式题你还会吗?
【递归】青蛙跳台阶的变式题你还会吗?
122 0
【递归】青蛙跳台阶的变式题你还会吗?
汉诺塔(递归+ 非递归版)
汉诺塔问题(又称为河内塔问题),是一个大家熟知的问题。在A,B,C三根柱子上, 有n个不同大小的圆盘(假设半径分别为1-n吧),一开始他们都叠在我A上(如图所示),你的目标是在最少的合法移动步数内将所有盘子从A塔移动到C塔。 游戏中的每一步规则如下:
234 1
汉诺塔(递归+ 非递归版)
|
算法 Java
【递归与回溯算法】汉诺塔与八皇后问题详解
文章目录 1 汉诺塔问题 1.1 汉诺塔问题概述 1.2 思路分析 1.3 代码实现(Java) 1.4 结果验证 2 八皇后问题 2.1 八皇后问题概述 2.2 思路分析 2.2.1 问题划分与分析 2.2.2 涉及到的数据结构分析 2.2.3 上下对角线与行列的关系 2.3 代码实现(Java) 2.4 结果验证
【递归与回溯算法】汉诺塔与八皇后问题详解