JS輸出斐波那契數(shù)列的方法

猿友 2021-06-30 10:14:07 瀏覽數(shù) (2814)

反饋

試輸出斐波那契數(shù)列的前10項(xiàng)，即 1、1、2、3、5、8、13、21、34、55。今天帶來的是JS輸出斐波那契數(shù)列的方法，希望能對(duì)各位有所幫助。

分析

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

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

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

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

生成每一項(xiàng)的值。
打印輸出所有值。

基礎(chǔ)解法

解題思路：

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

代碼實(shí)現(xiàn)如下：

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

分析：

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

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

初級(jí)遞歸

解題思路：

通過遞歸的手段計(jì)算出各位置對(duì)應(yīng)的值（這里有個(gè)前提是：第一項(xiàng)和第二項(xiàng)是確定值，否則，遞歸就不好用了）。
打印結(jié)果。

代碼實(shí)現(xiàn)如下：

/**
 * @description 計(jì)算出第 n 項(xiàng)的值
 * @param {number} n 表示每一項(xiàng)的下標(biāo)值
 * @returns {number} 下標(biāo)為 n 的位置的值
 */
function calFibValue(n) {
    console.count("執(zhí)行次數(shù)：")
    return n < 2 ? 1 : (calFibValue(n - 1) + calFibValue(n - 2));
}
 
/**
 * @description 打印計(jì)算結(jié)果
 * @param {number} n 代表要打印多少項(xiàng)
 */
function printRes(n) {
    for (let index = 0; index < n; index++) {
        console.log(calFibValue(index));
    }
}
 
// 調(diào)用打印方法
printRes(10);
 
// 執(zhí)行次數(shù)：: 276

分析：

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

每一項(xiàng)的值都是從第一項(xiàng)開始計(jì)算累加出來的，比如計(jì)算第四項(xiàng)的值，其過程如下：

返回第一項(xiàng)的值：1 。
返回第二項(xiàng)的值： 1 。
計(jì)算第三項(xiàng)的值為 1 + 1 = 2 。
計(jì)算第四項(xiàng)的值為 2 + 1 = 3 。

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

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

遞歸優(yōu)化

解題思路：

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

代碼實(shí)現(xiàn)：

/**
 * @description 計(jì)算出第 n 項(xiàng)的值
 * @param {number} n 表示每一項(xiàng)的下標(biāo)值
 * @returns {number} 下標(biāo)為 n 的位置的值
 */
 
// 存放每次計(jì)算結(jié)果的 Map 結(jié)構(gòu)
// 這里也可以用數(shù)組，但是在語(yǔ)義方面沒有 Map 或?qū)ο笾苯?/li>
let fibValueMap = new Map();
function calFibValue(n) {
    console.count("執(zhí)行次數(shù)：");
    // 如果緩存中已存在對(duì)應(yīng)的值，則直接返回
    if (fibValueMap.has(n)) {
        return fibValueMap.get(n);
    }
    const value = n < 2 ? 1 : (calFibValue(n - 1) + calFibValue(n - 2));
    // 在計(jì)算出每一項(xiàng)的之后，需要及時(shí)存入 Map
    fibValueMap.set(n, value);
    return value;
}
 
/**
 * @description 打印計(jì)算結(jié)果
 * @param {number} n 代表要打印多少項(xiàng)
 */
function printRes(n) {
    for (let index = 0; index < n; index++) {
        console.log(calFibValue(index));
    }
}
 
// 調(diào)用打印方法
printRes(10);
 
// 執(zhí)行次數(shù)：: 26

分析：

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

這次面試官應(yīng)該可以滿意了吧。

總結(jié)

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

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

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

少寫 BUG，我們才能有更多的時(shí)間來摸魚，不是嗎？

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

JavaScript

0 人點(diǎn)贊