App下載

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

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

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

分析

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

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

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

根據(jù)題目要求,其實就是要我們做兩件事:

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

基礎解法

解題思路:

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

代碼實現(xiàn)如下:

  1. /**
  2. * @description 創(chuàng)建一個生成數(shù)列數(shù)組的方法
  3. * @param {number} n 表示要生成多少項(即數(shù)組長度,不是數(shù)組下標)
  4. */
  5. function createFibArr(n) {
  6. // 聲明一個存放數(shù)據(jù)的數(shù)組
  7. let fibArr = [];
  8. // 從第三項(下標為2)開始,每一項都等于前兩項之和
  9. for (let index = 0; index < n; index++) {
  10. index < 2 ? fibArr.push(1) : fibArr.push(fibArr[index - 1] + fibArr[index - 2]);
  11. console.log(fibArr[index]);
  12. }
  13. }
  14.  
  15. // 調(diào)用方法
  16. createFibArr(10);

分析:

這應該是最基本的解題方法,很容易就實現(xiàn)了。

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

初級遞歸

解題思路:

  • 通過遞歸的手段計算出各位置對應的值(這里有個前提是:第一項和第二項是確定值,否則,遞歸就不好用了)。
  • 打印結(jié)果。

代碼實現(xiàn)如下:

  1. /**
  2. * @description 計算出第 n 項的值
  3. * @param {number} n 表示每一項的下標值
  4. * @returns {number} 下標為 n 的位置的值
  5. */
  6. function calFibValue(n) {
  7. console.count("執(zhí)行次數(shù):")
  8. return n < 2 ? 1 : (calFibValue(n - 1) + calFibValue(n - 2));
  9. }
  10.  
  11. /**
  12. * @description 打印計算結(jié)果
  13. * @param {number} n 代表要打印多少項
  14. */
  15. function printRes(n) {
  16. for (let index = 0; index < n; index++) {
  17. console.log(calFibValue(index));
  18. }
  19. }
  20.  
  21. // 調(diào)用打印方法
  22. printRes(10);
  23.  
  24. // 執(zhí)行次數(shù):: 276

分析:

遞歸的使用確實提升了代碼的逼格,但是又引來了另外一個問題:性能問題。

每一項的值都是從第一項開始計算累加 出來的,比如計算第四項的值,其過程如下:

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

在計算第五項值的時候,還要經(jīng)過上面這個過程來獲取第四項的值,進行了大量的重復運算。

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

遞歸優(yōu)化

解題思路:

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

代碼實現(xiàn):

  1. /**
  2. * @description 計算出第 n 項的值
  3. * @param {number} n 表示每一項的下標值
  4. * @returns {number} 下標為 n 的位置的值
  5. */
  6.  
  7. // 存放每次計算結(jié)果的 Map 結(jié)構(gòu)
  8. // 這里也可以用數(shù)組,但是在語義方面沒有 Map 或?qū)ο笾苯?/li>
  9. let fibValueMap = new Map();
  10. function calFibValue(n) {
  11. console.count("執(zhí)行次數(shù):");
  12. // 如果緩存中已存在對應的值,則直接返回
  13. if (fibValueMap.has(n)) {
  14. return fibValueMap.get(n);
  15. }
  16. const value = n < 2 ? 1 : (calFibValue(n - 1) + calFibValue(n - 2));
  17. // 在計算出每一項的之后,需要及時存入 Map
  18. fibValueMap.set(n, value);
  19. return value;
  20. }
  21.  
  22. /**
  23. * @description 打印計算結(jié)果
  24. * @param {number} n 代表要打印多少項
  25. */
  26. function printRes(n) {
  27. for (let index = 0; index < n; index++) {
  28. console.log(calFibValue(index));
  29. }
  30. }
  31.  
  32. // 調(diào)用打印方法
  33. printRes(10);
  34.  
  35. // 執(zhí)行次數(shù):: 26

分析:

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

這次面試官應該可以滿意了吧。

總結(jié)

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

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

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

少寫 BUG,我們才能有更多的時間來摸魚,不是嗎?

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

0 人點贊