資訊專欄INFORMATION COLUMN
摘要：前言前幾天面試被問到了斐波那契數列的實現以及優化的問題，當時現場卡了挺久的，現在進行一下總結使用實現。題目介紹斐波那契數列又被稱為黃金分割數列，指的是這樣的一個數列，它有如下遞推的方法定義是正整數，請使用實現斐波那契函數。
前言
前幾天面試被問到了斐波那契數列的實現以及優化的問題，當時現場卡了挺久的，現在進行一下總結（使用js實現）。題目介紹
??斐波那契數列又被稱為黃金分割數列，指的是這樣的一個數列：1,1,2,3,5,8,13,21,34....，它有如下遞推的方法定義：F(1)=1,F(2)=1,F(n)=F(n-1)+F(n-2)(n>=2,n是正整數)，請使用js實現斐波那契函數。
方法1：遞歸實現??由題目中的遞推受到啟發，可以通過遞歸的方式去實現，代碼如下：
function fibonacci(n){
if(n < 0) throw new Error("輸入的數字不能小于0");
if(n==1 || n==2){
return 1;
}else{
return fibonacci1(n-1) + fibonacci1(n-2);
}
}
優點：代碼比較簡潔易懂；
缺點：當數字太大時，會變得特別慢，原因是在計算F(9)時需要計算F(8)和F(7)，但是在計算F(8)時要計算F(7)和F(6)，這里面就會重復計算F(7)，每次都重復計算會造成不必要的浪費，所以這種方法并不是很好。
??由方法1可知，使用普通的遞歸，會造成不必要的浪費，所以我們首先想到的應該是將每次產生的遞歸值保存下來，下次直接使用就行，代碼如下：
function fibonacci(n){
if(n < 0) throw new Error("輸入的數字不能小于0");
let arr = [0,1];//在外部函數中定義數組，內部函數給數組添加值
function calc(n){
if(n<2){
return arr[n];
}
if(arr[n] != undefined){
return arr[n];
}
let data = calc(n-1) + calc(n-2);//使用data將每次遞歸得到的值保存起來
arr[n] = data;//將每次遞歸得到的值放到數組中保存
return data;
}
return calc(n);
}
方法3：直接使用數組實現（動態規劃）
??和方法2的思想類似，為了避免后續的重復計算，需要將計算過的值保存起來，我們可以直接使用數組進行保存。
function fibonacci(n){
var a = [0,1,1];
if(n < 0) throw new Error("輸入的數字不能小于0");
if(n >= 3){
for(var i=3;i<=n;i++){
a[i] = a[i-1]+a[i-2];
}
}
return a[n];
}
方法4：直接使用變量實現
??相校于使用數組的方式去存放，使用變量的方式就不會那么浪費內存了，因為總共只會有3個變量，但是也有缺點，它只能保存最后計算的值以及前兩個值，以前的值會被替換掉。
function fibonacci(n){
var pre = 0;//表示前一個值
var cur = 1;//表示后一個值
var data;//表示當前值
if(n < 0) throw new Error("請輸入大于0的值！");
if(n == 0) return 0;
if(n == 1) return 1;
if(n > 2){
for(var i=2;i<=n;i++){
data = pre + cur;
pre = cur;
cur = data;
}
}
return data;
}
總結
??其實大部分人在求斐波那契數列時想到的都是遞歸的方法，但是就其事件復雜度來看，不是一個好的方法，那么我們的優化思路可能就是使用空間換換時間了，就是將遞歸產生的值保存下來，以免下次還要重復計算。
文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。
轉載請注明本文地址：http://specialneedsforspecialkids.com/yun/109142.html
摘要：那其實這個問題還可以換個問法實現一個函數，輸入一個數字能返回斐波那契數列的第個值。文章預告更多的前端面試分享我都會第一時間更新在我的公眾號閏土大叔里面，歡迎關注 面試攢經驗，lets go！ 值此高考來臨之際，閑不住的我又雙叒叕出發去面試攢經驗了，去了公司交待一番流程后，面試官甩給了我一張A4紙，上面寫著一道js算法筆試題（一開始我并不知道這是在考察js算法），上面寫著1、1、2、3、...
摘要：實現斐波那契數列斐波那契數列最大數斐波那契數列由和開始之后的斐波那契數列系數就由之前的兩數相加。換個寫法，用箭頭函數最大數斐波那契數列由和開始 js實現斐波那契數列 // 斐波那契數列 let max=10000; // 最大數 let arr=[0,1]; // 斐波那契數列由 0 和 1 開始 // 之后的斐波那契數列系數就由之前的兩數相加。 ...
摘要：根據該規則，返回第個斐波那契數。尾遞歸函數調用自身，稱為遞歸。一個前端眼中的斐波那契數列解斐波那契數列的實用解法調用棧尾遞歸和手動優化尾調用優化譯我從用寫斐波那契生成器中學到的令人驚訝的件事 斐波那契數列是以下一系列數字： 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, ... 在種子數字 0 和 1 ...
摘要：在上做了一道斐波那契數列求和的題目，做完之后做了一些簡單的優化和用另一種方法實現。動態規劃解決方案斐波那契數列求和除了可以用遞歸的方法解決，還可以用動態規劃的方法解決。 在codewars上做了一道斐波那契數列求和的題目，做完之后做了一些簡單的優化和用另一種方法實現。 題目 function fibonacci(n) { if(n==0 || n == 1) r...
摘要：今天去面試筆試題斐波那契數列實現，雖然很簡單。回來想想既然算法這么重要那就從這個開始來記錄自己的算法庫吧。在數學上，斐波納契數列以如下被以遞歸的方法定義，，。斐波拉契算法規律很簡單，，觀察下數列值就很容易總結出來了。 一、寫在前面 算法這塊對于大多數程序員（包括我）來說可能都是一個薄弱的地方，如何彌補尼？ 每個人都知道那就是學習、特別是算法沒有任何捷徑可走。 在這記錄平時自己工作和生...
閱讀 631·2021-11-22 15:32
閱讀 2720·2021-11-19 09:40
閱讀 2313·2021-11-17 09:33
閱讀 1263·2021-11-15 11:36
閱讀 1864·2021-10-11 10:59
閱讀 1475·2019-08-29 16:41
閱讀 1780·2019-08-29 13:45
閱讀 2150·2019-08-26 13:36
