js如何計算斐波那契數(shù)列第n項的值

更新時間：2023年01月17日 14:42:47 作者：淡定如斯

這篇文章主要介紹了js如何計算斐波那契數(shù)列第n項的值問題，具有很好的參考價值，希望對大家有所幫助。如有錯誤或未考慮完全的地方，望不吝賜教

js計算斐波那契數(shù)列第n項的值

function myFibonacci(n) {
	if(n < 0){return;}
	if(n === 0){ return 0;}
	if(n === 1){ return 1;}
	if(n > 1){
		return myFibonacci(n-1) + myFibonacci(n-2);
	}
}

js求斐波那契數(shù)列Fibonacci中的第n個數(shù)是多少？

// **3 求斐波那契數(shù)列Fibonacci中的第n個數(shù)是多少？**
    // > 1 1 2 3 5 8 13 21...
    // > f(n)=f(n-1)+f(n-2)
    // >
    // > f(1)=f(2)=1
        function getFib(n) {
            var n1 = 1;//儲存f-2
            var n2 = 1;//儲存f-1
            var n3 = 0;//儲存取得值
            //i=2,因為第一個算的就是第三個的值
            for(var i = 2; i < n; i++) {
                n3 = n1 + n2;
                //為取下一個值做準備，原來的n-1變成n-2，當前取出的值變成了下一個的n-1
                n1 = n2;
                n2 = n3;
            }
            return n3;

js實現(xiàn)斐波那契數(shù)列求項及優(yōu)化

斐波那契數(shù)列

相信每一個接觸算法的人都會遇到一道經(jīng)典的算法問題，斐波那契數(shù)列。

斐波那契數(shù)列的規(guī)律也很簡單，就是第一第二項值為1，第三項開始每一項值為該項前兩項的和；實現(xiàn)起來也并不難。

function fib(n){
    if (n===1 || n===2){//判斷項所在位置，如果為第一第二項，返回1
        return 1;
    } else{
        return fib(n-1)+fib(n-2);//位置在第三項及以后，返回前兩項和
    }
}
console.log(fib(5));

這個就是在JS里面簡單實現(xiàn)求斐波那契數(shù)列某一項值的一個代碼；

但是這個代碼的缺陷也是很明顯的，時空復雜度太高；我們可以定義一個變量 i 來看一下

let =0;
function fib(n){
    i++;
    if (n===1 || n===2){//判斷項所在位置，如果為第一第二項，返回1
        return 1;
    } else{
        return fib(n-1)+fib(n-2);//位置在第三項及以后，返回前兩項和
    }
}
console.log(fib(5));
console.log(i);

在這個圖片里面我們可以看到，當n的值為40的時候，i 的值是204668309，也就是說我們求斐波那契第40項的時候函數(shù)被調用的次數(shù)；

因為字符串的不可變特征只要還沒找到函數(shù)出口前就會一直在棧上開辟新空間去存儲數(shù)據(jù)，這個也是棧溢出最主要的原因。

優(yōu)化

有問題那么我們就要去優(yōu)化，最主要的性能問題就是數(shù)據(jù)存儲上會不斷開辟新空間造成空間復雜度的提升，解決方法也很簡單：定義一個空數(shù)組存儲斐波那契數(shù)列項。因為數(shù)組是一個復雜類型存儲在堆里面，而且需要new的時候才會去創(chuàng)建一個新的存儲空間，我們只需要在棧上建立一個索引去訪問該數(shù)組就可以。

//定義存儲斐波那契數(shù)列項數(shù)組
let result = [];
let i=0;
function sum(a) {
    i++;
    //首先判斷數(shù)組內有沒有當前斐波那契數(shù)列項，如果有直接從數(shù)組獲??；沒有則將該項push進數(shù)組，再從數(shù)組過去該項
    if (result[a] !== undefined){
        return result[a];
    } else{
        if (a===1 || a===2){
            result[a] = 1;
            return 1;
        } else{
            result[a] = sum(a-1)+sum(a-2);
            return result[a];
        }
    }
}
console.log(sum(1476));
console.log(i);

上面代碼就是經(jīng)過優(yōu)化之后的代碼，很簡單；就是添加了一個數(shù)組存儲斐波那契數(shù)列項。效果也是很顯著；

下面是求第1476項 i 的值：