C语言如何解决青蛙跳台阶问题

小编给大家分享一下C语言如何解决青蛙跳台阶问题，相信大部分人都还不怎么了解，因此分享这篇文章给大家参考一下，希望大家阅读完这篇文章后大有收获，下面让我们一起去了解一下吧！一只青蛙一次可以跳上 1 级台阶，也可以跳上 2 级。求该青蛙跳上一个 n 级的台阶总共有多少种跳法。诺，就像下面这样其实我一看到这道题，我也是懵的，不知道从哪里着手分析，那我们就从最简单的情况开始分析。假如 n = 1，一共有一级台阶，显然就只有一种跳法一次跳1阶；假如 n = 2，一共有两级台阶，共有两种跳法跳1阶，再跳1阶跳2阶假设n = 3，共有三种跳法。跳1阶，跳1阶，再跳1阶跳1阶，再跳2阶跳2阶, 再跳1阶（注：此过程图是我从网上找的，实在是难得画啦）通过上面的分析，我们可以这样思考问题前往楼梯顶部的最后一步，要么跳1阶，要么跳2阶；先假设f(n)为 n 级台阶的总跳法数；那么第一次如果选择跳一级的话，剩下的 n-1 级台阶的跳法数就为f(n−1)。如果第一次跳两级的话，剩下的 n-2 级台阶的跳法就是f(n−2)；现在青蛙一次只能跳一级或两级，所以我们可以推出以下公式：咦，这玩意儿不就是我们 斐波那契数 吗？只不过有一点不同的是，斐波那契数列一般是以1,1,2,3,5,8,13……开始的；而我们这是以1,2,3,5,8,13……开始的，少了最前面的一个1。上面说到这个过程有点类似于斐波那契数，但又不完全是，所以我们先看主代码部分运行结果但是，我们来看一下计算的过程要计算f(6)，就需要先计算出子问题f(5)和f(4)然后要计算f(5)，又要先算出子问题f(4)和f(3)，以此类推。一直到f(2)和f(1)，递归树才终止。因此，青蛙跳阶，递归解法的时间复杂度 等于O(1) * O(2ⁿ)=O(2ⁿ)你仔细观察这颗递归树，你会发现存在「大量重复计算」；比如f(4)被计算了两次，f(3)被重复计算了3次…所以这个递归算法低效的原因，就是存在大量的重复计算！所以我们可以对代码进行优化递归升级在递归法的基础上，新建一个长度为n的数组，用于在递归时存储f(0)至f(n) 的数字值，重复遇到某数字时则直接从数组取用，避免了重复的递归计算。所以我们设置一个数组，用于存放第一次计算某一个n的jump(n)。当每一次要计算一个jump(n)的时候，就先查看数组中以n为下标的地方是否有值，有的话就可以不调用jump(n)，而直接从数组中取得结果值，否则再计算jump(n)。代码实现运行结果动态规划解法很快我又发现，不必把所有的记录都记起来；假设我有3阶楼梯，我只需要知道跳2阶和跳1阶的方法数是多少就可以算出跳3阶的方法数；因此每次只需要保留n−1阶和n−2阶的方法数。代码实现运行结果一只青蛙一次可以跳上一级台阶，也可以跳上二级台阶……，也可以跳n级，求该青蛙跳上一个n级的台阶总共需要多少种跳法。一只青蛙要想跳到n级台阶，可以从一级，二级……，也就是说可以从任何一级跳到n级当台阶为1级时，f(1)=1；当台阶为2级时，f(2)=1+1=2；当台阶为3级时，f(3)=f(1)+f(2)+1=4；当台阶为4级时，f(4)=f(1)+f(2)+f(3)+1=8；当台阶为5级时，f(5)=f(1)+f(2)+f(3)+f(4)+1=16；所以递推公式我们很容易就能想到:f(n)=f(n−1)+f(n−2)+……+f(2)+f(1)+f(0)最后这个f(0)是可以去掉的，因为0级就相当于没跳，所以f(0)=0然后我们把f(0)去掉再转换一下：f(n−1)=f(n−2)+f(n−3)+……+f(2)+f(1)；推导过程我们列两个等式：①f(n)=f(n−1)+f(n−2)+f(n−3)+…+f(2)+f(1)②f(n−1)=f(n−2)+f(n−3)+…+f(2)+f(1)由①-②得，f(n)=2f(n−1)递归方法代码示例运行结果非递归方法当然这里也可以用非递归的免费云主机域名方式来实现那么非递归怎么去思考呢？可以这样理解：然后使用用函数pow(2,n -1)，需要加头文件但是我们这里可以不用库函数来实现，给大家介绍一种神奇的运算代码示例运行结果我这里选择用
以上是“C语言如何解决青蛙跳台阶问题”这篇文章的所有内容，感谢各位的阅读！相信大家都有了一定的了解，希望分享的内容对大家有所帮助，如果还想学习更多知识，欢迎关注百云主机行业资讯频道！

相关推荐: 共享充电宝小程序开发有哪些优势

本篇内容介绍了“共享充电宝小程序开发有哪些优势”的有关知识，在实际案例的操作过程中，不少人都会遇到这样的困境，接下来就让小编带领大家学习一下如何处理这些情况吧！希望大家仔细阅读，能够学有所成！一、共享充电宝小程序开发的应用场景 1.大型娱乐消费场所：人们在逛街…