JavaScript輸出斐波那契數列的實(shí)現方法

目錄

題目

有這么一道題目需要我們來(lái)解答：

• 試輸出斐波那契數列的前10項，即 1、1、2、3、5、8、13、21、34、55。
  

分析

有些人看到題目中出現了“斐波那契數列”這個(gè)概念后，可能腦袋就蒙圈了，其實(shí)大可不必！

對于這道題，可以不用理會(huì )這個(gè)陌生概念，我們只需要關(guān)心后面它給出的數字規律即可。

我們可以看到，規律總結起來(lái)就一句話(huà)：從第三位開(kāi)始，后面每項的值等于前兩項之和，用式子表示的話(huà)就是：an = an-1 + an-2（n ≥ 2） 。

根據題目要求，其實(shí)就是要我們做兩件事：

1. 生成每一項的值。
2. 打印輸出所有值。
   

基礎解法

解題思路：

• 創(chuàng )建一個(gè)數組存放數列各項的值。
• for 循環(huán)生成數列各項并存入數組（為了計算后面各項的值），打印生成的項。
  

代碼實(shí)現如下：

/**
 * @description 創(chuàng  )建一個(gè)生成數列數組的方法
 * @param {number} n 表示要生成多少項（即數組長(cháng)度，不是數組下標）
 */
function createFibArr(n) {
    // 聲明一個(gè)存放數據的數組
    let fibArr = [];
    // 從第三項(下標為2)開(kāi)始，每一項都等于前兩項之和
    for (let index = 0; index < n; index++) {
        index < 2 ? fibArr.push(1) : fibArr.push(fibArr[index - 1] + fibArr[index - 2]);
        console.log(fibArr[index]);
    }
}

// 調用方法
createFibArr(10);

分析：

這應該是最基本的解題方法，很容易就實(shí)現了。

但如果這是面試題的話(huà)，這樣的答案只能說(shuō)是中規中矩，沒(méi)有出彩的地方，最重要的是體現不出我們與眾不同的氣質(zhì)啊，所以，我們應該用點(diǎn)其他的手段來(lái)提升下自己的逼格！

初級遞歸

解題思路：

• 通過(guò)遞歸的手段計算出各位置對應的值（這里有個(gè)前提是：第一項和第二項是確定值，否則，遞歸就不好用了）。
• 打印結果。
  

代碼實(shí)現如下：

/**
 * @description 計算出第 n 項的值
 * @param {number} n 表示每一項的下標值
 * @returns {number} 下標為 n 的位置的值 
 */
function calFibValue(n) {
    console.count("執行次數：")
    return n < 2 ? 1 : (calFibValue(n - 1) + calFibValue(n - 2));
}

/**
 * @description 打印計算結果
 * @param {number} n 代表要打印多少項
 */
function printRes(n) {
    for (let index = 0; index < n; index++) {
        console.log(calFibValue(index));
    }
}

// 調用打印方法
printRes(10);

// 執行次數：: 276

分析：

遞歸的使用確實(shí)提升了代碼的逼格，但是又引來(lái)了另外一個(gè)問(wèn)題：性能問(wèn)題。

每一項的值都是從第一項開(kāi)始計算累加 出來(lái)的，比如計算第四項的值，其過(guò)程如下：

• 返回第一項的值：1 。
• 返回第二項的值： 1 。
• 計算第三項的值為 1 + 1 = 2 。
• 計算第四項的值為 2 + 1 = 3 。
  

在計算第五項值的時(shí)候，還要經(jīng)過(guò)上面這個(gè)過(guò)程來(lái)獲取第四項的值，進(jìn)行了大量的重復運算。

為了驚艷面試官，我們還需要再做優(yōu)化！

遞歸優(yōu)化

解題思路：

• 導致重復計算的是遞歸那部分的邏輯，所以?xún)?yōu)化點(diǎn)在遞歸這里。
• 既然存在重復運算，那就意味著(zhù)其實(shí)后面的運算完全可以使用前面已經(jīng)計算出來(lái)的值，所以我們需要引入緩存來(lái)保存每次的計算結果。

代碼實(shí)現：

/**
 * @description 計算出第 n 項的值
 * @param {number} n 表示每一項的下標值
 * @returns {number} 下標為 n 的位置的值 
 */

// 存放每次計算結果的 Map 結構
// 這里也可以用數組，但是在語(yǔ)義方面沒(méi)有 Map 或對象直接
let fibValueMap = new Map();
function calFibValue(n) {
    console.count("執行次數：");
    // 如果緩存中已存在對應的值，則直接返回
    if (fibValueMap.has(n)) {
        return fibValueMap.get(n);
    }
    const value = n < 2 ? 1 : (calFibValue(n - 1) + calFibValue(n - 2));
    // 在計算出每一項的之后，需要及時(shí)存入 Map
    fibValueMap.set(n, value);
    return value;
}

/**
 * @description 打印計算結果
 * @param {number} n 代表要打印多少項
 */
function printRes(n) {
    for (let index = 0; index < n; index++) {
        console.log(calFibValue(index));
    }
}

// 調用打印方法
printRes(10);

// 執行次數：: 26

分析：

根據打印出來(lái)的 count 來(lái)看，優(yōu)化后的遞歸次數是優(yōu)化前的 1/10 左右，這個(gè)結果就很驚喜了。

這次面試官應該可以滿(mǎn)意了吧。

總結

萬(wàn)變不離其宗，只要將解題思路理清了，代碼實(shí)現只是一個(gè)結果而已。在平常的工作學(xué)習中，我們要有意識地培養自己的發(fā)散性思維，從多角度去看待問(wèn)題，你可能會(huì )發(fā)現不一樣的風(fēng)景哦！希望能夠對大家有所啟發(fā)哦！

在面試中，為了突顯自己的獨特氣質(zhì)或者人家面試題目就有具體要求的，我們使用一些看起來(lái)高大上的思路，這無(wú)可厚非。

但是呢，在平常的工作中，我還是更建議大家：在性能相近的情況下，能使用基礎方法解決的一般不要用“高檔”方法，因為基礎方法出錯的概率小很多。就比如今天這道題，其實(shí)基礎解法的性能是最好的。

少寫(xiě) BUG，我們才能有更多的時(shí)間來(lái)摸魚(yú)，不是嗎？

到此這篇關(guān)于JavaScript輸出斐波那契數列的文章就介紹到這了,更多相關(guān)JS輸出斐波那契數列內容請搜索腳本之家以前的文章或繼續瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！