亚洲中字慕日产2020,大陆极品少妇内射AAAAAA,无码av大香线蕉伊人久久,久久精品国产亚洲av麻豆网站

資訊專欄INFORMATION COLUMN

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

alexnevsky / 2218人閱讀

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

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

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

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

??由題目中的遞推受到啟發(fā)，可以通過遞歸的方式去實(shí)現(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)點(diǎn)：代碼比較簡潔易懂；
缺點(diǎn)：當(dāng)數(shù)字太大時(shí)，會(huì)變得特別慢，原因是在計(jì)算F(9)時(shí)需要計(jì)算F(8)和F(7)，但是在計(jì)算F(8)時(shí)要計(jì)算F(7)和F(6)，這里面就會(huì)重復(fù)計(jì)算F(7)，每次都重復(fù)計(jì)算會(huì)造成不必要的浪費(fèi)，所以這種方法并不是很好。

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

??由方法1可知，使用普通的遞歸，會(huì)造成不必要的浪費(fèi)，所以我們首先想到的應(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ù)組實(shí)現(xiàn)（動(dòng)態(tài)規(guī)劃）

??和方法2的思想類似，為了避免后續(xù)的重復(fù)計(jì)算，需要將計(jì)算過的值保存起來，我們可以直接使用數(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：直接使用變量實(shí)現(xiàn)

??相校于使用數(shù)組的方式去存放，使用變量的方式就不會(huì)那么浪費(fèi)內(nèi)存了，因?yàn)榭偣仓粫?huì)有3個(gè)變量，但是也有缺點(diǎn)，它只能保存最后計(jì)算的值以及前兩個(gè)值，以前的值會(huì)被替換掉。

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

        if(n < 0) throw new Error("請(qǐng)輸入大于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í)大部分人在求斐波那契數(shù)列時(shí)想到的都是遞歸的方法，但是就其事件復(fù)雜度來看，不是一個(gè)好的方法，那么我們的優(yōu)化思路可能就是使用空間換換時(shí)間了，就是將遞歸產(chǎn)生的值保存下來，以免下次還要重復(fù)計(jì)算。

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

轉(zhuǎn)載請(qǐng)注明本文地址：http://www.ezyhdfw.cn/yun/109142.html

相關(guān)文章

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

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

    Galence 評(píng)論0 收藏0

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

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

    notebin 評(píng)論0 收藏0

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

    摘要：根據(jù)該規(guī)則，返回第個(gè)斐波那契數(shù)。尾遞歸函數(shù)調(diào)用自身，稱為遞歸。一個(gè)前端眼中的斐波那契數(shù)列解斐波那契數(shù)列的實(shí)用解法調(diào)用棧尾遞歸和手動(dòng)優(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 ...

    趙連江 評(píng)論0 收藏0

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

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

    xinhaip 評(píng)論0 收藏0

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

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

    robin 評(píng)論0 收藏0

發(fā)表評(píng)論

0條評(píng)論

最新活動(dòng)
閱讀需要支付1元查看
<