成人国产在线小视频_日韩寡妇人妻调教在线播放_色成人www永久在线观看_2018国产精品久久_亚洲欧美高清在线30p_亚洲少妇综合一区_黄色在线播放国产_亚洲另类技巧小说校园_国产主播xx日韩_a级毛片在线免费

資訊專欄INFORMATION COLUMN

使用js實現(xiàn)斐波那契數(shù)列

alexnevsky / 2161人閱讀

摘要：前言前幾天面試被問到了斐波那契數(shù)列的實現(xiàn)以及優(yōu)化的問題，當(dāng)時現(xiàn)場卡了挺久的，現(xiàn)在進(jìn)行一下總結(jié)使用實現(xiàn)。題目介紹斐波那契數(shù)列又被稱為黃金分割數(shù)列，指的是這樣的一個數(shù)列，它有如下遞推的方法定義是正整數(shù)，請使用實現(xiàn)斐波那契函數(shù)。

前言 
前幾天面試被問到了斐波那契數(shù)列的實現(xiàn)以及優(yōu)化的問題，當(dāng)時現(xiàn)場卡了挺久的，現(xiàn)在進(jìn)行一下總結(jié)（使用js實現(xiàn)）。
題目介紹

??斐波那契數(shù)列又被稱為黃金分割數(shù)列，指的是這樣的一個數(shù)列：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是正整數(shù))，請使用js實現(xiàn)斐波那契函數(shù)。

方法1：遞歸實現(xiàn)

??由題目中的遞推受到啟發(fā)，可以通過遞歸的方式去實現(xiàn)，代碼如下：

function fibonacci(n){
        if(n < 0) throw new Error("輸入的數(shù)字不能小于0");
        if(n==1 || n==2){
            return 1;
        }else{
            return fibonacci1(n-1) + fibonacci1(n-2);
        }
    }

優(yōu)點：代碼比較簡潔易懂；
缺點：當(dāng)數(shù)字太大時，會變得特別慢，原因是在計算F(9)時需要計算F(8)和F(7)，但是在計算F(8)時要計算F(7)和F(6)，這里面就會重復(fù)計算F(7)，每次都重復(fù)計算會造成不必要的浪費，所以這種方法并不是很好。

方法2：使用閉包保存每次的遞歸值

??由方法1可知，使用普通的遞歸，會造成不必要的浪費，所以我們首先想到的應(yīng)該是將每次產(chǎn)生的遞歸值保存下來，下次直接使用就行，代碼如下：

function fibonacci(n){
        if(n < 0) throw new Error("輸入的數(shù)字不能小于0");
        let arr = [0,1];//在外部函數(shù)中定義數(shù)組，內(nèi)部函數(shù)給數(shù)組添加值
        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;//將每次遞歸得到的值放到數(shù)組中保存
            return data;
        }
        return calc(n);
    }
方法3：直接使用數(shù)組實現(xiàn)（動態(tài)規(guī)劃）

??和方法2的思想類似，為了避免后續(xù)的重復(fù)計算，需要將計算過的值保存起來，我們可以直接使用數(shù)組進(jìn)行保存。

function fibonacci(n){
        var a = [0,1,1];
        if(n < 0) throw new Error("輸入的數(shù)字不能小于0");
        if(n >= 3){
            for(var i=3;i<=n;i++){
                a[i] = a[i-1]+a[i-2];
            }
        }
        return a[n];
    }
方法4：直接使用變量實現(xiàn)

??相校于使用數(shù)組的方式去存放，使用變量的方式就不會那么浪費內(nèi)存了，因為總共只會有3個變量，但是也有缺點，它只能保存最后計算的值以及前兩個值，以前的值會被替換掉。

function fibonacci(n){
        var pre = 0;//表示前一個值
        var cur = 1;//表示后一個值
        var data;//表示當(dāng)前值

        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;
    }
總結(jié)

??其實大部分人在求斐波那契數(shù)列時想到的都是遞歸的方法，但是就其事件復(fù)雜度來看，不是一個好的方法，那么我們的優(yōu)化思路可能就是使用空間換換時間了，就是將遞歸產(chǎn)生的值保存下來，以免下次還要重復(fù)計算。

文章版權(quán)歸作者所有，未經(jīng)允許請勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。

轉(zhuǎn)載請注明本文地址：http://systransis.cn/yun/109142.html

相關(guān)文章

  • 太原面經(jīng)分享：如何用js實現(xiàn)返回斐波那契數(shù)列的第n個值的函數(shù)

    摘要：那其實這個問題還可以換個問法實現(xiàn)一個函數(shù)，輸入一個數(shù)字能返回斐波那契數(shù)列的第個值。文章預(yù)告更多的前端面試分享我都會第一時間更新在我的公眾號閏土大叔里面，歡迎關(guān)注 面試攢經(jīng)驗，lets go！ 值此高考來臨之際，閑不住的我又雙叒叕出發(fā)去面試攢經(jīng)驗了，去了公司交待一番流程后，面試官甩給了我一張A4紙，上面寫著一道js算法筆試題（一開始我并不知道這是在考察js算法），上面寫著1、1、2、3、...

    Galence 評論0 收藏0

  • js實現(xiàn)斐波那契數(shù)列

    摘要：實現(xiàn)斐波那契數(shù)列斐波那契數(shù)列最大數(shù)斐波那契數(shù)列由和開始之后的斐波那契數(shù)列系數(shù)就由之前的兩數(shù)相加。換個寫法，用箭頭函數(shù)最大數(shù)斐波那契數(shù)列由和開始 js實現(xiàn)斐波那契數(shù)列 // 斐波那契數(shù)列 let max=10000; // 最大數(shù) let arr=[0,1]; // 斐波那契數(shù)列由 0 和 1 開始 // 之后的斐波那契數(shù)列系數(shù)就由之前的兩數(shù)相加。 ...

    notebin 評論0 收藏0

  • js 實現(xiàn)斐波那契數(shù)列(數(shù)組緩存、動態(tài)規(guī)劃、尾調(diào)用優(yōu)化)

    摘要：根據(jù)該規(guī)則，返回第個斐波那契數(shù)。尾遞歸函數(shù)調(diào)用自身，稱為遞歸。一個前端眼中的斐波那契數(shù)列解斐波那契數(shù)列的實用解法調(diào)用棧尾遞歸和手動優(yōu)化尾調(diào)用優(yōu)化譯我從用寫斐波那契生成器中學(xué)到的令人驚訝的件事 斐波那契數(shù)列是以下一系列數(shù)字： 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, ... 在種子數(shù)字 0 和 1 ...

    趙連江 評論0 收藏0

  • 斐波那契數(shù)列求和的js方案以及優(yōu)化

    摘要：在上做了一道斐波那契數(shù)列求和的題目，做完之后做了一些簡單的優(yōu)化和用另一種方法實現(xiàn)。動態(tài)規(guī)劃解決方案斐波那契數(shù)列求和除了可以用遞歸的方法解決，還可以用動態(tài)規(guī)劃的方法解決。 在codewars上做了一道斐波那契數(shù)列求和的題目，做完之后做了一些簡單的優(yōu)化和用另一種方法實現(xiàn)。 題目 function fibonacci(n) { if(n==0 || n == 1) r...

    xinhaip 評論0 收藏0

  • 算法記錄 >> 斐波那契數(shù)列

    摘要：今天去面試筆試題斐波那契數(shù)列實現(xiàn)，雖然很簡單。回來想想既然算法這么重要那就從這個開始來記錄自己的算法庫吧。在數(shù)學(xué)上，斐波納契數(shù)列以如下被以遞歸的方法定義，，。斐波拉契算法規(guī)律很簡單，，觀察下數(shù)列值就很容易總結(jié)出來了。 一、寫在前面 算法這塊對于大多數(shù)程序員（包括我）來說可能都是一個薄弱的地方，如何彌補(bǔ)尼？ 每個人都知道那就是學(xué)習(xí)、特別是算法沒有任何捷徑可走。 在這記錄平時自己工作和生...

    robin 評論0 收藏0

發(fā)表評論

0條評論

最新活動
閱讀需要支付1元查看
<