一个小青蛙,可以一次跳两节楼梯,也可以一次跳一节楼梯,请问他如果要跳101节楼梯,一共有几种跳法方案

fsmStudy 发布于2019-08-22 15:20 / 957人阅读

摘要：一个小青蛙可以一次跳两节楼梯也可以一次跳一节楼梯请问他如果要跳节楼梯一共有几种跳法方案问题的描述很简单看到这个题目的时候我首先想到的就是举例分析一波比如当的时候有几种方案当的时候有几种方案等等我们首先分析一波当的时候这个时候小青蛙只有一种跳

一个小青蛙,可以一次跳两节楼梯,也可以一次跳一节楼梯,请问他如果要跳101节楼梯,一共有几种跳法方案?

问题的描述很简单,看到这个题目的时候,我首先想到的就是举例分析一波,比如当n=1的时候有几种方案,当n=2的时候有几种方案等等….

我们首先分析一波,当n=1的时候,这个时候小青蛙只有一种跳法,就是跳上台阶1,然后结束,当然这并不能帮助我们归纳总结,然后我们继续分析
当n=2的时候,这个时候,小青蛙可以跳上台阶1,也可以跳上台阶2结束,然后台阶1呢,也可以跳上台阶2然后结束,我们发现,如果光靠想象的话,很难发现其中的规律,这个时候我们需要借助图形来帮助我们.

下图是我自己用笔画的图形,建议在这种时候还是用笔在纸上写写画画来帮助我们

灵魂画手!!!

经过举例我们发现,得到的结果组成的数,特别像菲波纳斯数列,从n=3开始,每一项都等于前两项的和,为了验证一下我们的结论,我们可以在推导一下n=5的时候,一共有几种情况,很显然我们的结论是正确的.这就是一个求菲波纳斯数列的题,那么好,这个时候有人可能会说了,菲波纳斯数列是啥?能吃么?好,那我就从另外一个角度去分析这个题目

假如说,小青蛙现在已经跳上了第4个台阶,那么它上一个台阶是那一个呢?要想回答这个问题,我们还需要在看一下题目的介绍,题目说,小青蛙一次只能跳一个台阶或者跳两个台阶,那么这个答案很简单了,如果他现在在4,那么它的上一个台阶一定是3或者是2.
然后我们在思考.如果他现在处在第3个台阶呢,那么它的上一个台阶一定是2或者是1.

那你也许会有疑问了,知道了这个他的上一个台阶有啥用呢,我给大家举一个栗子大家就明白了
请问,1+1等于多少呢?如果我在问你,1+1+1的结果呢,很显而易见,我要告诉大家的不是这个等式的结果是多少,我想告诉大家的是算的过程,我们在算出来1+1之后,如果在算1+1+1,我们只需要将1+1的结果在加上1就好,反过来我们理解一下,如果你想算出来1+1+1,那我们是不是只需要算出1+1的结果呢,

类比到我们的这个算法,如果你想算出来小青蛙跳上第4个台阶一共有几种情况,那我们只需要算出来小青蛙跳上第3个的种类加上跳上第2个台阶的种类即可归纳出来的数学公式就是f(n)=f(n-1)+f(n-2).

我们把这个思路由代码实现出来,很简单,我们首先用递归去做.

function jump(n) {
        if (n === 1 || n=== 2) {
            return n
        }
        return jump(n - 1) + jump(n - 2)
    }

代码很简单,但是有一个很大的问题想算出来n=101,根本算不出来,浏览器执行的时间太长,当然,如果你愿意等,浏览器还是可以算出来的.
其实这个代码有一个很大的弊端就是,他会一直重复性的去计算,假设说我们已经算出来f(4)了,但是当我们在算f(5)的时候,这个函数又会从新去算一遍f(4),根据这个思路我们可以优化一下,我们通过一个数组去记录f(n),这样就不会重复性的去计算.

function jump(n, memory = []) {
        if (n === 1 || n=== 2) {
            memory[n] = n
        }
        if (memory[n] !== undefined) {
            return memory[n]
        } else {
            memory[n] = jump(n - 1, memory) + jump(n - 2, memory)
        }
        return memory[n]
    }

改善后的代码,可以’ 秒’算出来结果了,但是我们的追求不能止步于此,我们在优化一下代码,这个代码是通过递归去做的,其实递归是很消耗性能的,我们直接通过循环去做
function jump(n) {

    let arr = [1, 2]
    for (let i = 2; i< n; i++) {
        arr [i] = arr[i - 1] + arr[i - 2]
    }
    return arr[n - 1]
}

最终我们对比通过循环代码和优化后的递归算法执行的时间,我们计算当n = 1000的时候的结果

结果显而易见.

最后分享给大家一句话: 大佬不是一天练成的!!!加油,咸鱼总有翻身的一天,就算翻身还是咸鱼,那它也是一条会翻身的咸鱼!!!

云服务器 GPU云服务器楼梯爬楼梯兔子上楼梯c语言一次性可以备案多少个域名

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/93390.html

动态规划入门（以爬楼梯为例）

摘要：动态规划算法通常基于一个递推公式及一个或多个初始状态。动态规划有三个核心元素最优子结构边界状态转移方程我们来看一到题目题目有一座高度是级台阶的楼梯，从下往上走，每跨一步只能向上级或者级台阶。概念动态规划(dynamic programming)是运筹学的一个分支，是求解决策过程(decision process)最优化的数学方法。动态规划算法通常基于一个递推公式及一个或多个初始状态...

cyixlq 2019-08-23 10:52 评论0 收藏0
【刷算法】我知道的所有类似斐波那契数列的问题

摘要：有一类算法问题类似斐波那契数列，而且解决办法基本差不多。不了解斐波那契套路的可以看刷算法斐波那契数列跳台阶问题题目描述一只青蛙一次可以跳上级台阶，也可以跳上级。给定整数，求年后牛的数量。分析设为年后牛的数量，则第年牛的来源有两个。有一类算法问题类似斐波那契数列，而且解决办法基本差不多。不了解斐波那契套路的可以看【刷算法】斐波那契数列跳台阶问题题目描述一只青蛙一次可以跳上1级台阶，...

NotFound 2019-08-22 18:10 评论0 收藏0
【Leetcode】70. 爬楼梯

摘要：题目假设你正在爬楼梯。需要阶你才能到达楼顶。你有多少种不同的方法可以爬到楼顶呢注意给定是一个正整数。示例输入输出解释有两种方法可以爬到楼顶。阶阶阶阶阶阶阶题解这个题目只要模拟一下基本就能想到是，状态方程写出来就是斐波那契数列。题目假设你正在爬楼梯。需要 n 阶你才能到达楼顶。每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？注意：给定 n 是一个正整数。示...

raoyi 2019-07-24 10:49 评论0 收藏0
【Leetcode】70. 爬楼梯

摘要：题目假设你正在爬楼梯。需要阶你才能到达楼顶。你有多少种不同的方法可以爬到楼顶呢注意给定是一个正整数。示例输入输出解释有两种方法可以爬到楼顶。阶阶阶阶阶阶阶题解这个题目只要模拟一下基本就能想到是，状态方程写出来就是斐波那契数列。题目假设你正在爬楼梯。需要 n 阶你才能到达楼顶。每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？注意：给定 n 是一个正整数。示...

187J3X1 2019-06-26 17:49 评论0 收藏0