資訊專欄INFORMATION COLUMN
摘要：一個小青蛙可以一次跳兩節(jié)樓梯也可以一次跳一節(jié)樓梯請問他如果要跳節(jié)樓梯一共有幾種跳法方案問題的描述很簡單看到這個題目的時候我首先想到的就是舉例分析一波比如當(dāng)?shù)臅r候有幾種方案當(dāng)?shù)臅r候有幾種方案等等我們首先分析一波當(dāng)?shù)臅r候這個時候小青蛙只有一種跳
一個小青蛙,可以一次跳兩節(jié)樓梯,也可以一次跳一節(jié)樓梯,請問他如果要跳101節(jié)樓梯,一共有幾種跳法方案?
問題的描述很簡單,看到這個題目的時候,我首先想到的就是舉例分析一波,比如當(dāng)n=1的時候有幾種方案,當(dāng)n=2的時候有幾種方案等等….
我們首先分析一波,當(dāng)n=1的時候,這個時候小青蛙只有一種跳法,就是跳上臺階1,然后結(jié)束,當(dāng)然這并不能幫助我們歸納總結(jié),然后我們繼續(xù)分析
當(dāng)n=2的時候,這個時候,小青蛙可以跳上臺階1,也可以跳上臺階2結(jié)束,然后臺階1呢,也可以跳上臺階2然后結(jié)束,我們發(fā)現(xiàn),如果光靠想象的話,很難發(fā)現(xiàn)其中的規(guī)律,這個時候我們需要借助圖形來幫助我們.
下圖是我自己用筆畫的圖形,建議在這種時候還是用筆在紙上寫寫畫畫來幫助我們
靈魂畫手!!!
經(jīng)過舉例我們發(fā)現(xiàn),得到的結(jié)果組成的數(shù),特別像菲波納斯數(shù)列,從n=3開始,每一項都等于前兩項的和,為了驗證一下我們的結(jié)論,我們可以在推導(dǎo)一下n=5的時候,一共有幾種情況,很顯然我們的結(jié)論是正確的.這就是一個求菲波納斯數(shù)列的題,那么好,這個時候有人可能會說了,菲波納斯數(shù)列是啥?能吃么?好,那我就從另外一個角度去分析這個題目
假如說,小青蛙現(xiàn)在已經(jīng)跳上了第4個臺階,那么它上一個臺階是那一個呢?要想回答這個問題,我們還需要在看一下題目的介紹,題目說,小青蛙一次只能跳一個臺階或者跳兩個臺階,那么這個答案很簡單了,如果他現(xiàn)在在4,那么它的上一個臺階一定是3或者是2.
然后我們在思考.如果他現(xiàn)在處在第3個臺階呢,那么它的上一個臺階一定是2或者是1.
那你也許會有疑問了,知道了這個他的上一個臺階有啥用呢,我給大家舉一個栗子大家就明白了
請問,1+1等于多少呢?如果我在問你,1+1+1的結(jié)果呢,很顯而易見,我要告訴大家的不是這個等式的結(jié)果是多少,我想告訴大家的是算的過程,我們在算出來1+1之后,如果在算1+1+1,我們只需要將1+1的結(jié)果在加上1就好,反過來我們理解一下,如果你想算出來1+1+1,那我們是不是只需要算出1+1的結(jié)果呢,
類比到我們的這個算法,如果你想算出來小青蛙跳上第4個臺階一共有幾種情況,那我們只需要算出來小青蛙跳上第3個的種類加上跳上第2個臺階的種類即可歸納出來的數(shù)學(xué)公式就是f(n)=f(n-1)+f(n-2).
我們把這個思路由代碼實現(xiàn)出來,很簡單,我們首先用遞歸去做.
function jump(n) {
if (n === 1 || n=== 2) {
return n
}
return jump(n - 1) + jump(n - 2)
}
代碼很簡單,但是有一個很大的問題想算出來n=101,根本算不出來,瀏覽器執(zhí)行的時間太長,當(dāng)然,如果你愿意等,瀏覽器還是可以算出來的.
其實這個代碼有一個很大的弊端就是,他會一直重復(fù)性的去計算,假設(shè)說我們已經(jīng)算出來f(4)了,但是當(dāng)我們在算f(5)的時候,這個函數(shù)又會從新去算一遍f(4),根據(jù)這個思路我們可以優(yōu)化一下,我們通過一個數(shù)組去記錄f(n),這樣就不會重復(fù)性的去計算.
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]
}
改善后的代碼,可以’ 秒’算出來結(jié)果了,但是我們的追求不能止步于此,我們在優(yōu)化一下代碼,這個代碼是通過遞歸去做的,其實遞歸是很消耗性能的,我們直接通過循環(huá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]
}
最終我們對比通過循環(huán)代碼和優(yōu)化后的遞歸算法執(zhí)行的時間,我們計算當(dāng)n = 1000的時候的結(jié)果
結(jié)果顯而易見.
最后分享給大家一句話: 大佬不是一天練成的!!!加油,咸魚總有翻身的一天,就算翻身還是咸魚,那它也是一條會翻身的咸魚!!!
文章版權(quán)歸作者所有，未經(jīng)允許請勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請注明本文地址：http://www.ezyhdfw.cn/yun/93390.html
摘要：動態(tài)規(guī)劃算法通?；谝粋€遞推公式及一個或多個初始狀態(tài)。動態(tài)規(guī)劃有三個核心元素最優(yōu)子結(jié)構(gòu)邊界狀態(tài)轉(zhuǎn)移方程我們來看一到題目題目有一座高度是級臺階的樓梯，從下往上走，每跨一步只能向上級或者級臺階。 概念 動態(tài)規(guī)劃(dynamic programming)是運(yùn)籌學(xué)的一個分支，是求解決策過程(decision process)最優(yōu)化的數(shù)學(xué)方法。動態(tài)規(guī)劃算法通?；谝粋€遞推公式及一個或多個初始狀態(tài)...
摘要：有一類算法問題類似斐波那契數(shù)列，而且解決辦法基本差不多。不了解斐波那契套路的可以看刷算法斐波那契數(shù)列跳臺階問題題目描述一只青蛙一次可以跳上級臺階，也可以跳上級。給定整數(shù)，求年后牛的數(shù)量。分析設(shè)為年后牛的數(shù)量，則第年牛的來源有兩個。 有一類算法問題類似斐波那契數(shù)列，而且解決辦法基本差不多。不了解斐波那契套路的可以看【刷算法】斐波那契數(shù)列 跳臺階問題 題目描述一只青蛙一次可以跳上1級臺階，...
摘要：題目假設(shè)你正在爬樓梯。需要階你才能到達(dá)樓頂。你有多少種不同的方法可以爬到樓頂呢注意給定是一個正整數(shù)。示例輸入輸出解釋有兩種方法可以爬到樓頂。階階階階階階階題解這個題目只要模擬一下基本就能想到是，狀態(tài)方程寫出來就是斐波那契數(shù)列。 題目 假設(shè)你正在爬樓梯。需要 n 階你才能到達(dá)樓頂。 每次你可以爬 1 或 2 個臺階。你有多少種不同的方法可以爬到樓頂呢？ 注意：給定 n 是一個正整數(shù)。 示...
摘要：題目假設(shè)你正在爬樓梯。需要階你才能到達(dá)樓頂。你有多少種不同的方法可以爬到樓頂呢注意給定是一個正整數(shù)。示例輸入輸出解釋有兩種方法可以爬到樓頂。階階階階階階階題解這個題目只要模擬一下基本就能想到是，狀態(tài)方程寫出來就是斐波那契數(shù)列。 題目 假設(shè)你正在爬樓梯。需要 n 階你才能到達(dá)樓頂。 每次你可以爬 1 或 2 個臺階。你有多少種不同的方法可以爬到樓頂呢？ 注意：給定 n 是一個正整數(shù)。 示...
閱讀 3407·2021-11-25 09:43
閱讀 3083·2021-10-15 09:43
閱讀 2037·2021-09-08 09:36
閱讀 3029·2019-08-30 15:56
閱讀 814·2019-08-30 15:54
閱讀 2752·2019-08-30 15:54
閱讀 3067·2019-08-30 11:26
閱讀 1316·2019-08-29 17:27
