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