一個小青蛙,可以一次跳兩節樓梯,也可以一次跳一節樓梯,請問他如果要跳101節樓梯,一共有幾種跳法方案

fsmStudy 發布于2019-08-22 15:20 / 958人閱讀

摘要：一個小青蛙可以一次跳兩節樓梯也可以一次跳一節樓梯請問他如果要跳節樓梯一共有幾種跳法方案問題的描述很簡單看到這個題目的時候我首先想到的就是舉例分析一波比如當的時候有幾種方案當的時候有幾種方案等等我們首先分析一波當的時候這個時候小青蛙只有一種跳

一個小青蛙,可以一次跳兩節樓梯,也可以一次跳一節樓梯,請問他如果要跳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語言一次性可以備案多少個域名

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://specialneedsforspecialkids.com/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