C语言 递归解决青蛙跳台阶问题

目录
  • 前言
  • 一、求解思路
  • 二、代码实现
    • 1.参考代码
    • 2.运行结果
  • 总结

前言

一只青蛙一次可以跳1级或2级台阶,求当台阶数为n时青蛙有多少种跳法。

一、求解思路

台阶的数量为n。

当 n = 1 时，青蛙有一种跳法，即跳1级台阶。

当 n = 2 时，青蛙有两种跳法，即跳两次1级台阶或跳一次2级台阶。

当 n = 3 时，青蛙可以先跳2级台阶再跳1级台阶，也可以选择先跳1级台阶再跳2级台阶，或者是跳三次1级台阶。依次类推，我们就能知道台阶数为n时青蛙的跳法。

但是，这样子是不是很麻烦呢，再仔细想一下。

还是当 n = 3 时，我们选择先跳1级台阶，剩下的2级台阶的跳法，是不是就是当 n = 2 时青蛙的跳法；我们选择先跳2级台阶，剩下的1级台阶的跳法，是不是就是当 n = 1 时青蛙的跳法。

由此可知，n = 3 时青蛙的跳法为 n = 1 时的跳法加上 n = 2 时的跳法。

当 n = N 时，N个台阶的跳法为 N-1 的跳法加上 N-2 的跳法。

乍一看，是不是感觉和斐波那契数列有点像，当然，还是有一丢丢不一样的，不过我们可以用同样的数学思想来解决这个问题。

二、代码实现

1.参考代码

#define _CRT_SECURE_NO_WARNINGS 1
#include <stdio.h>

int flog(int n)
{
	if (n == 1)
		return 1;
	else if (n == 2)
		return 2;
	else
		return flog(n - 1) + flog(n - 2);
}
int  main()
{
	int n = 0;
    int ways = 0;
	printf("请输入台阶的数量：");
	scanf("%d", &n);
	ways = flog(n);
	printf("青蛙有%d种跳法",ways);
	return 0;
}

2.运行结果

总结

孤寡 孤寡 孤寡

到此这篇关于C语言 递归解决青蛙跳台阶问题的文章就介绍到这了,更多相关C语言 递归内容请搜索我们以前的文章或继续浏览下面的相关文章希望大家以后多多支持我们！

赞 (0)

相关推荐

  • C语言函数的基本使用和递归小结

    C语言函数的基本使用和递归小结

    本章目标 秃头侠们好呀,今天我们一起学习函数! 目标: 本章主要掌握函数的基本使用和递归 函数是什么 数学中我们常见到函数的概念.但是你了解C语言中的函数吗? 维基百科中对函数的定义:子程序 在计算机科学中,子程序(英语:Subroutine, procedure, function, routine, method,subprogram, callable unit),是一个大型程序中的某部分代码, 由一个或多个语句块组成.它负责完成某项特定任务,而且相较于其他代 码,具备相对的独立性. 一般

  • C语言学好递归看这一篇就够了

    C语言学好递归看这一篇就够了

    前言 在一定的时间.空间限制下,人的体力有限,思维力也有限,递归思维对实践最有用的指导,就是把脑力集中于定义问题这个关键点上,不用去找解题的过程.定义(问题)即解决(问题),定义即解决! 让大问题变成规模更小的问题并立即获得解决,以此作为基础,让我们轻松解决函数本身定义的问题.所以,递归在编程中同样是很重要的一个知识点. 提示:以下是本篇文章正文内容 一.递归是什么? 先来看一下定义: 程序调用自身的编程技巧称为递归( recursion). 简单来说,就是在一个函数里面调用函数自己本身. 举个

  • C语言递归系列的深入总结

    C语言递归系列的深入总结

    递归 什么是递归 递归简而言之就是函数自己调用自己 如图所示 但是递归并不是简简单单的自己调用自己的过程 它分为 传递 和 回归,传递就是橙色箭头 回归则是黑色箭头 这就是递归 以 计算阶乘为例,假设我们输入6 计算6的阶乘为例 #define _CRT_SECURE_NO_WARNINGS #include<stdio.h> int factorial(int x) //递归体函数 { if (x == 1) { return 1; } return x * (factorial(x - 1

  • C语言中递归的实际应用与经典问题

    C语言中递归的实际应用与经典问题

    目录 一.什么是递归 二.递归模板 三.递归的实际应用 1.阶乘递归 2.斐波那契数列 四.递归的经典问题 汉诺塔问题 青蛙跳台阶 总结 一.什么是递归 递归简单的来说就是在函数中调用自己 它通常把一个大型复杂的问题层层转化为一个与原问题相似的规模较小的问题来求解,递归策略只需少量的程序就可描述出解题过程所需要的多次重复计算,大大地减少了程序的代码量. 递归的两个必要条件: 存在限制条件,当满足这个限制条件的时候,递归便不再继续. 每次递归调用之后越来越接近这个限制条件. 二.递归模板 void

  • C语言递归实现扫雷游戏

    C语言递归实现扫雷游戏

    前言 首先要实现扫雷原理上同三子棋,都是通过一个二维数组来实现游戏主题功能那么这里有几个值得注意的点 1.初级扫雷我们知道是九乘九数组实现,那么在这里我们创建的是11乘11的数组,目的是方便后续判断周围九个格子的雷的数量! 2.而且我们需要创建两个数组,一个用来存放字符1和0(1表示有雷,随机数生成:0表示没雷,初始化时自动全放0): 另一个用来根据上边的数组输出显示玩家是否被炸死,以及玩家选择的坐标周围雷的数量 3.需要注意排雷时候如果附近没有雷需要递归展开!!! 4.我们这里需要两个源文件t

  • C语言函数的基本使用和递归详解

    C语言函数的基本使用和递归详解

    目录 本章目标 函数是什么 C语言中函数的分类 库函数 如何学会使用库函数? 自定义函数 函数的参数 函数的调用: 函数的嵌套调用和链式访问 嵌套调用 链式访问 函数的声明和定义 函数递归 什么是递归? 递归的两个必要条件 递归与迭代 总结 本章目标 秃头侠们好呀,今天我们一起学习函数! 目标: 本章主要掌握函数的基本使用和递归 函数是什么 数学中我们常见到函数的概念.但是你了解C语言中的函数吗? 维基百科中对函数的定义:子程序 在计算机科学中,子程序(英语:Subroutine, proced

  • C语言递归之汉诺塔和青蛙跳台阶问题

    C语言递归之汉诺塔和青蛙跳台阶问题

    递归就是一个函数执行过程中调用自己,在c语言中有很多关于递归的经典问题,例如:斐波那契数列问题.汉诺塔问题等,在研究递归问题时我们要注意三点: 1.递归的结束条件 2.递归在每次进行过程中,都得离条件越来越近 3.相邻两次递归调用之间的关联关系 汉诺塔问题: 有三根杆子A, B, C.A杆上有N个(N > 1)穿孔圆盘, 盘的尺寸由下到上依次变小.要求按下列规则将所有圆盘移至C杆: 1.每次只能移动一个圆盘: 2.大盘不能叠在小盘上面,可将圆盘临时置于B杆, 也可将从A杆移出的圆盘重新移回A杆,

  • C语言 递归解决青蛙跳台阶问题

    C语言 递归解决青蛙跳台阶问题

    目录 前言 一.求解思路 二.代码实现 1.参考代码 2.运行结果 总结 前言 一只青蛙一次可以跳1级或2级台阶,求当台阶数为n时青蛙有多少种跳法. 一.求解思路 台阶的数量为n. 当 n = 1 时,青蛙有一种跳法,即跳1级台阶. 当 n = 2 时,青蛙有两种跳法,即跳两次1级台阶或跳一次2级台阶. 当 n = 3 时,青蛙可以先跳2级台阶再跳1级台阶,也可以选择先跳1级台阶再跳2级台阶,或者是跳三次1级台阶.依次类推,我们就能知道台阶数为n时青蛙的跳法. 但是,这样子是不是很麻烦呢,再仔细

  • C语言解决青蛙跳台阶问题(升级版)

    C语言解决青蛙跳台阶问题(升级版)

    目录 1. 基础问题 题目描述 解题思路 代码实现 2. 问题升级 题目描述 解题思路 代码实现 3. 特性总结 1. 基础问题 题目描述 一只青蛙一次可以跳上 1 级台阶,也可以跳上 2 级.求该青蛙跳上一个 n 级的台阶总共有多少种跳法. 诺,就像下面这样 解题思路 其实我一看到这道题,我也是懵的,不知道从哪里着手分析,那我们就从最简单的情况开始分析. 假如 n = 1,一共有一级台阶,显然就只有一种跳法 一次跳1阶: 假如 n = 2,一共有两级台阶,共有两种跳法 跳1阶,再跳1阶 跳2阶

  • C 语言基础实现青蛙跳台阶和汉诺塔问题

    C 语言基础实现青蛙跳台阶和汉诺塔问题

    目录 一.青蛙跳台阶 题目 思路 分析 1. 从跳法次数分析 2. 从过程分析 二.青蛙跳台阶变式1 题目 分析 三.青蛙跳台阶变式2 题目 分析 四.汉诺塔问题(求步数) 题目 思路 分析 五.汉诺塔问题(求移动过程) 题目 思路 分析 一.青蛙跳台阶 题目 一只青蛙一次可以跳上1级台阶,也可以跳上2级台阶.求该青蛙跳上一个 n 级的台阶总共有多少种跳法 思路 遇见题目我们可以在纸上先动手画画,把最简单的几种方式列出来,作比较,找规律. 分析 按照上面表格可以从跳法次数,过程,或者两者结合找规

  • Java解决青蛙跳台阶问题流程

    Java解决青蛙跳台阶问题流程

    1.问题描述 一只青蛙一次可以跳上1阶台阶,也可以跳上2阶台阶,求该青蛙跳上一个n阶台阶总共有多少种跳法? 2.画图分析  3.问题讲解  一只青蛙,要么1次跳2个台阶,要么1次跳1个台阶. 假设3个台阶为例:如果1次跳1个台阶,那剩下几种跳法?我们来仔细地想一下: 跳了一个台阶之后,剩下的台阶就相当于3 -1个台阶剩下2个台阶,2个台阶的跳法如上图就是2种跳法. 如果一次跳2个台阶,剩下的台阶就相当于3 - 2个台阶剩下1个台阶,1个台阶的跳法如上图是1种跳法.那么加起来就是3种跳法. 所以说

  • Java青蛙跳台阶问题的解决思路与代码

    Java青蛙跳台阶问题的解决思路与代码

    问题描述 一只青蛙一次可以跳上1级台阶,也可以一次跳上2级台阶,请问跳上n级台阶,该请娃一共有多少种跳法? 解决思路 ①如果只有1级台阶,那显然只有一种跳法. ②如果有2级台阶,那么就有2种跳法,一种是分2次跳.每次跳1级,另一种就是一次跳2级. ③如果台阶级数大于2,设为n的话,这时我们把n级台阶时的跳法看成n的函数,记为,第一次跳的时候有2种不同的选择:一是第一次跳一级,此时跳法的数目等于后面剩下的n-1级台阶的跳法数目,即为,二是第一次跳二级,此时跳法的数目等于后面剩下的n-2级台阶的跳法

  • 手把手带你用java搞定青蛙跳台阶

    手把手带你用java搞定青蛙跳台阶

    目录 问题描述 问题剖析 n=1 n=2 n=3 n=4 小结 Java代码示例 附:C语言实现青蛙跳台阶 总结 问题描述 一只青蛙一次可以跳上 1 级台阶,也可以跳上2 级.求该青蛙跳上一个n 级的台阶总共有多少种跳法 问题剖析 n=1 此时有一种跳法. n=2 此时有两种跳法. n=3 此时有三种跳法. n=4 此时有五种跳法. 小结 当有n级台阶时,青蛙可以跳1级,也可以跳2级.如果它跳1级,那么还剩下n-1级台阶:如果它跳2级,那么还剩下n-2级台阶.因此n级台阶的跳法等于n-1级台阶跳

  • php中青蛙跳台阶的问题解决方法

    一只青蛙一次可以跳上1级台阶,也可以跳上2级.求该青蛙跳上一个n级的台阶总共有多少种跳法(先后次序不同算不同的结果). 思路: 1.找规律 f(1)=1 f(2)=2 f(3)=3 f(4)=5 f(n)=f(n-1)+f(n-2)这是一个斐波那契数列 2.因为调到第n个台阶时,倒数第一个台阶可以一步跳过来,倒数第二个台阶也可以一步就跳过来 非递归版本: JumpFloor(target) if target==1 || target==2 return target jumpSum=0 jum

  • 利用简洁的C语言代码解决跳台阶问题与约瑟夫环问题

    跳台阶问题 题目: 一个台阶总共有 n 级,如果一次可以跳 1 级,也可以跳 2 级. 求总共有多少总跳法,并分析算法的时间复杂度. 分析: 也是比较基础的题目,通过递归可以方便的求解 代码实现如下(GCC编译通过): #include "stdio.h" #include "stdlib.h" int function(int n); int main(void) { int tmp; tmp = function(5); printf("%3d\n&q

  • 使用C++递归求解跳台阶问题

    使用C++递归求解跳台阶问题

    题目: 一个台阶总共有 n 级,如果一次可以跳 1 级,也可以跳 2 级.求总共有多少总跳法? 分析: 也是比较基础的题目,通过递归可以方便的求解. 用Fib(n)表示青蛙跳上n阶台阶的跳法数,青蛙一次性跳上n阶台阶的跳法数1(n阶跳),设定Fib(0) = 1:        当n = 1 时, 只有一种跳法,即1阶跳:Fib(1) = 1;        当n = 2 时, 有两种跳的方式,一阶跳和二阶跳:Fib(2) = Fib(1) + Fib(0) = 2;        当n = 3

随机推荐