C语言解决青蛙跳台阶问题(递归与非递归)

简介: 一只青蛙可以一次跳1级台阶或一次跳2级台阶,例如:跳上第一级台阶只有一种跳法:直接跳1级即可。跳上两级台阶,有两种跳法:每次跳1级,跳两次;或者一次跳2级.问要跳上第级台阶有多少种跳法?

青蛙跳台阶问题

题目描述

问题分析

递归解法

非递归解法

题目描述


一只青蛙可以一次跳1级台阶或一次跳2级台阶,例如:跳上第一级台阶只有一种跳法:直接跳1级即可。跳上两级台阶,有两种跳法:每次跳1级,跳两次;或者一次跳2级.问要跳上第级台阶有多少种跳法?


问题分析


有一个台阶时:青蛙只能一级台阶,跳法一种


93e000765127487cacddcef0c6977c83.png

有2个台阶时:青蛙可以一次跳2级台阶,也可以跳2次一级台阶,所以跳法两种:

fcde734ef6c741b9aa6847aedf654a1e.png


当有三级台阶时,如果青蛙第一次跳一级台阶,那么之后它就有两级台阶需要跳;如果第一次跳2级台阶,那么那之后就有1级台阶需要跳。这就把问题抛到了跳一级台阶和跳两级台阶的问题上,所以有3种跳法


第一次跳1级:



559b2f05e84e474e9d4b57dc86200a15.png


第一次跳2级:




c2ba9d4761364567af597792adad1ba0.png


所以,当有n级台阶时,就可以把问题抛到n-1级台阶和n-2级台阶问题中,而这两个问题还可以细分,所以我们自然而然容易想到递归

第一次跳1级:


5f9e113144224ea6ab2de48743db6f76.png



第一次跳2级:

f8d809acf60140a99633e69d6324a56c.png





设跳n级台阶跳法为f(n)次

n = 1时,f(n) = 1;

n = 2时,f(n) = 2;

n>=3时,f(n) = f(n-1)+f(n-2);


递归解法

代码:


#include <stdio.h>
int times(int n)
{
  if (n == 1)
  {
  return 1;
  }
  else if (n ==2)
  {
  return 2;
  }
  else
  {
  return times(n - 1) + times(n - 2);
  }
}
int main()
{
  int n = 0;
  scanf("%d", &n);
  int time = times(n);
  printf("跳%d个台阶,需要%d次\n", n, time);
  return 0;
}



非递归解法

在前面的分析可以发现,n>=3时,f(n) = f(n-1)+f(n-2),也就是前n阶的前两种情况

所以完全可以使用非递归的循环语句解决这个问题


int times2(int n)
{
  if (n == 1)
  {
  return 1;
  }
  if (n == 2)
  {
  return 2;
  }
  else
  {
  int a = 1;   //一阶台阶有1中跳法
  int b = 2;   //二阶台阶有2种跳法
  int c = 0;  
  while (n > 2)
  {
    c = a + b;  
    a = b;
    b = c;
    n--;
  }
  return c;
  }
}
int main()
{
  int n = 0;
  scanf("%d", &n);
  int time2 = times2(n);
  printf("跳%d个台阶,需要%d次\n", n, time2);
  return 0;
}



这里用动图解释过程

07f26a2ee6af4afe8a298bceb4f219ae.gif

全部代码


#include <stdio.h>
int times(int n)
{
  if (n == 1)
  {
  return 1;
  }
  else if (n ==2)
  {
  return 2;
  }
  else
  {
  return times(n - 1) + times(n - 2);
  }
}
int times2(int n)
{
  if (n == 1)
  {
  return 1;
  }
  if (n == 2)
  {
  return 2;
  }
  else
  {
  int a = 1;
  int b = 2;
  int c = 0;
  while (n > 2)
  {
    c = a + b;
    a = b;
    b = c;
    n--;
  }
  return c;
  }
}
int main()
{
  int n = 0;
  scanf("%d", &n);
  int time = times(n);
  printf("递归:跳%d个台阶,需要%d次\n", n, time); 
  int time2 = times2(n);
  printf("非递归:跳%d个台阶,需要%d次\n", n, time2);
  return 0;
}


测试结果:

——————————————8293b0cade2c450cb73bd94791d91a1a.png

Jambo!
+关注
目录
打赏
0
0
0
0
15
分享
相关文章
|
15天前
|
【C语言程序设计——函数】递归求斐波那契数列的前n项(头歌实践教学平台习题)【合集】
本关任务是编写递归函数求斐波那契数列的前n项。主要内容包括: 1. **递归的概念**:递归是一种函数直接或间接调用自身的编程技巧,通过“俄罗斯套娃”的方式解决问题。 2. **边界条件的确定**:边界条件是递归停止的条件,确保递归不会无限进行。例如,计算阶乘时,当n为0或1时返回1。 3. **循环控制与跳转语句**:介绍`for`、`while`循环及`break`、`continue`语句的使用方法。 编程要求是在右侧编辑器Begin--End之间补充代码,测试输入分别为3和5,预期输出为斐波那契数列的前几项。通关代码已给出,需确保正确实现递归逻辑并处理好边界条件,以避免栈溢出或结果
51 16
【c语言】一篇文章搞懂函数递归
本文详细介绍了函数递归的概念、思想及其限制条件,并通过求阶乘、打印整数每一位和求斐波那契数等实例,展示了递归的应用。递归的核心在于将大问题分解为小问题,但需注意递归可能导致效率低下和栈溢出的问题。文章最后总结了递归的优缺点,提醒读者在实际编程中合理使用递归。
101 7
|
3月前
|
c语言回顾-函数递归(上)
c语言回顾-函数递归(上)
56 2
|
3月前
|
c语言回顾-函数递归(下)
c语言回顾-函数递归(下)
63 0
【C语言篇】递归详细介绍(基础概念习题及汉诺塔等进阶问题)
要保持最小的步数,每一次汉诺塔问题(无论是最初还是递归过程中的),如果此时初始柱盘子数为偶数,我们第一步是把最上面的盘子移动到中转柱,如果为奇数,我们第一步则是将其移动到目标柱。
131 0
【C语言篇】递归详细介绍(基础概念习题及汉诺塔等进阶问题)
|
5月前
|
C语言中的递归
C语言中的递归
|
19天前
|
【C语言程序设计——函数】素数判定(头歌实践教学平台习题)【合集】
本内容介绍了编写一个判断素数的子函数的任务,涵盖循环控制与跳转语句、算术运算符(%)、以及素数的概念。任务要求在主函数中输入整数并输出是否为素数的信息。相关知识包括 `for` 和 `while` 循环、`break` 和 `continue` 语句、取余运算符 `%` 的使用及素数定义、分布规律和应用场景。编程要求根据提示补充代码,测试说明提供了输入输出示例,最后给出通关代码和测试结果。 任务核心:编写判断素数的子函数并在主函数中调用,涉及循环结构和条件判断。
55 23
|
19天前
|
【C语言程序设计——函数】利用函数求解最大公约数和最小公倍数(头歌实践教学平台习题)【合集】
本文档介绍了如何编写两个子函数,分别求任意两个整数的最大公约数和最小公倍数。内容涵盖循环控制与跳转语句的使用、最大公约数的求法(包括辗转相除法和更相减损术),以及基于最大公约数求最小公倍数的方法。通过示例代码和测试说明,帮助读者理解和实现相关算法。最终提供了完整的通关代码及测试结果,确保编程任务的成功完成。
47 15
|
19天前
|
【C语言程序设计——函数】亲密数判定(头歌实践教学平台习题)【合集】
本文介绍了通过编程实现打印3000以内的全部亲密数的任务。主要内容包括: 1. **任务描述**:实现函数打印3000以内的全部亲密数。 2. **相关知识**: - 循环控制和跳转语句(for、while循环,break、continue语句)的使用。 - 亲密数的概念及历史背景。 - 判断亲密数的方法:计算数A的因子和存于B,再计算B的因子和存于sum,最后比较sum与A是否相等。 3. **编程要求**:根据提示在指定区域内补充代码。 4. **测试说明**:平台对代码进行测试,预期输出如220和284是一组亲密数。 5. **通关代码**:提供了完整的C语言代码实现
56 24

热门文章

最新文章

AI助理

你好,我是AI助理

可以解答问题、推荐解决方案等