資訊專欄INFORMATION COLUMN
摘要：題目題目描述大家都知道斐波那契數(shù)列，現(xiàn)在要求輸入一個整數(shù)，請你輸出斐波那契數(shù)列的第項從開始，第項為。基本思路這道題在劍指中實際是當作遞歸的反例來說的。明顯也符合斐波那契數(shù)列的規(guī)律矩形覆蓋我們可以用的小矩形橫著或者豎著去覆蓋更大的矩形。
題目
題目描述
大家都知道斐波那契數(shù)列，現(xiàn)在要求輸入一個整數(shù)n，請你輸出斐波那契數(shù)列的第n項（從0開始，第0項為0）。
這道題在劍指offer中實際是當作遞歸的反例來說的。
遞歸的本質(zhì)是吧一個問題分解成兩個或者多個小問題，如果多個小問題存在互相重疊的情況，那么就存在重復計算。
f(n) = f(n-1) + f(n-2) 這種拆分使用遞歸是典型的存在重疊的情況，所以會造成非常多的重復計算。
另外，每一次函數(shù)調(diào)用愛內(nèi)存中都需要分配空間，每個進程的棧的容量是有限的，遞歸層次過多，就會造成棧溢出。
遞歸是從最大數(shù)開始，不斷拆解成小的數(shù)計算，如果不去考慮遞歸，我們只需要從小數(shù)開始算起，從底層不斷往上累加就可以了，其實思路也很簡單。
代碼function Fibonacci(n)
{
if(n<=1){
return n;
}
let i = 1;
let pre = 0;
let current = 1;
let result = 0;
while(i++ < n){
result = pre + current;
pre = current;
current = result;
}
return result;
}
擴展
1.跳臺階：
一只青蛙一次可以跳上1級臺階，也可以跳上2級。求該青蛙跳上一個n級的臺階總共有多少種跳法（先后次序不同算不同的結(jié)果）。
找規(guī)律：
跳三級臺階等于跳兩級臺階的跳法+跳一級臺階的跳法。
跳四級臺階等于跳三級臺階的跳法+跳二級臺階的跳法。
明顯也符合斐波那契數(shù)列的規(guī)律
function jumpFloor(n)
{
if(n<=2){
return n;
}
let i = 2;
let pre = 1;
let current = 2;
let result = 0;
while(i++ < n){
result = pre + current;
pre = current;
current = result;
}
return result;
}
3.矩形覆蓋
我們可以用21的小矩形橫著或者豎著去覆蓋更大的矩形。請問用n個21的小矩形無重疊地覆蓋一個2*n的大矩形，總共有多少種方法？
跟上面跳臺階那個題很像。
假設(shè)有8個塊
第1塊豎著放，后面還剩7塊，共f(7)種方法。
第1塊橫著放，后面還剩6塊，共f(6)種方法。
即f(8)=f(6)+f(7)
f(n)=f(n-1)+f(n-2)
function rectCover(n)
{
if(n<=2){
return n;
}
let i = 2;
let pre = 1;
let current = 2;
let result = 0;
while(i++ < n){
result = pre + current;
pre = current;
current = result;
}
return result;
}
3.{{BANNED}}跳臺階
一只青蛙一次可以跳上1級臺階，也可以跳上2級……它也可以跳上n級。求該青蛙跳上一個n級的臺階總共有多少種跳法。
每個臺階都可以選擇跳或者不跳，最后一個臺階必跳。
每個臺階有兩種選擇，n個臺階有2的n次方種選擇。
所以一共有2的n-1次跳法。
使用位運算
function jumpFloorII(number)
{
return 1<<(--number);
}
文章版權(quán)歸作者所有，未經(jīng)允許請勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請注明本文地址：http://systransis.cn/yun/101222.html
摘要：二維數(shù)組中的查找在一個二維數(shù)組中，每一行都按照從左到右遞增的順序排序，每一列都按照從上到下遞增的順序排序。請完成一個函數(shù)，輸入這樣的一個二維數(shù)組和一個整數(shù)，判斷數(shù)組中是否含有該整數(shù)。例如輸入前序遍歷序列和中序遍歷序列，則重建二叉樹并返回。 1.二維數(shù)組中的查找 在一個二維數(shù)組中，每一行都按照從左到右遞增的順序排序，每一列都按照從上到下遞增的順序排序。請完成一個函數(shù)，輸入這樣的一個二維數(shù)...
摘要：二維數(shù)組中的查找在一個二維數(shù)組中，每一行都按照從左到右遞增的順序排序，每一列都按照從上到下遞增的順序排序。解法有兩種，一種是遞歸法，一種是迭代法但是遞歸法計算的時間復雜度是以的指數(shù)的方式遞增的，如果面試中千萬不要用遞歸法，一定要用迭代法。 二維數(shù)組中的查找 在一個二維數(shù)組中，每一行都按照從左到右遞增的順序排序，每一列都按照從上到下遞增的順序排序。請完成一個函數(shù)，輸入這樣的一個二維數(shù)組和...
摘要：正文面試題重建二叉樹題目輸入某二叉樹的前序遍歷和中序遍歷的結(jié)果，請重建出該二叉樹。前序遍歷序列為，中序遍歷序列，。確定了左右子樹后遞歸處理。方法方法面試題在時間刪除鏈表結(jié)點。 寫在前面 本文的題目均來自于劍指offer中的題目，題目序號保持了書中的題目序號，由于某些題目并不適合于javascript這種語言，所以這些題目就沒有寫在本篇博客中，因此會出現(xiàn)題目序號的中斷。 正文 面試題6：...
摘要：今天去面試筆試題斐波那契數(shù)列實現(xiàn)，雖然很簡單?；貋硐胂爰热凰惴ㄟ@么重要那就從這個開始來記錄自己的算法庫吧。在數(shù)學上，斐波納契數(shù)列以如下被以遞歸的方法定義，，。斐波拉契算法規(guī)律很簡單，，觀察下數(shù)列值就很容易總結(jié)出來了。 一、寫在前面 算法這塊對于大多數(shù)程序員（包括我）來說可能都是一個薄弱的地方，如何彌補尼？ 每個人都知道那就是學習、特別是算法沒有任何捷徑可走。 在這記錄平時自己工作和生...
閱讀 2800·2021-11-04 16:15
閱讀 3482·2021-09-29 09:35
閱讀 4076·2021-09-22 15:45
閱讀 1429·2019-08-30 15:55
閱讀 1703·2019-08-30 15:44
閱讀 2746·2019-08-29 12:56
閱讀 2712·2019-08-26 13:30
閱讀 2185·2019-08-23 17:00
