數(shù)據(jù)結構與算法（遞歸與循環(huán)） --javascript語言描述

nanfeiyan 發(fā)布于2019-08-26 11:44 / 3402人閱讀

摘要：斐波那契數(shù)列大家都知道斐波那契數(shù)列，現(xiàn)在要求輸入一個整數(shù)，請你輸出斐波那契數(shù)列的第項。這樣的計算是以的次方在增長的。我們不難看出這實際上就是斐波那契數(shù)列了。用表示跳上階臺階的跳法數(shù)。所以，種跳法。

斐波那契數(shù)列

大家都知道斐波那契數(shù)列，現(xiàn)在要求輸入一個整數(shù)n，請你輸出斐波那契數(shù)列的第n項。
n<=39

遞歸解法：

  function Fibonacci(n)
  {
    if(n<=0) {
      return 0;
    }
    if(n==1) {
      return 1;
    }
    return Fibonacci(n-1) + Fibonacci(n-2);
  }
  console.log(Fibonacci(10));

由于使用遞歸時，其執(zhí)行步驟是：要得到后一個數(shù)之前必須先計算出之前的兩個數(shù)，即在每個遞歸調(diào)用時都會觸發(fā)另外兩個遞歸調(diào)用，例如：要得到F(10)之前得先得到F(9)、F(8)，那么得到F(9)之前得先得到F(8)、F(7)......如此遞歸下去。這樣的計算是以 2 的次方在增長的。除此之外，我們也可以看到，F(xiàn)(8)和F(7)的值都被多次計算，如果遞歸的深度越深，那么F(8)和F(7)的值會被計算更多次，但是這樣計算的結果都是一樣的，除了其中之一外，其余的都是浪費，可想而知，這樣的開銷是非常恐怖的！

所以，如果在時間復雜度和空間復雜度都有要求的話，我們可以用以下循環(huán)算法來實現(xiàn)：

  function Fibonacci(n)
  {
    if (n == 0 || n == 1) {
        return n;
    }
    let num1 = 0;
    let num2 = 1;
    let numN = 0;
    for (let i = 2; i <= n; i++) {
      numN = num1 + num2;
      num1 = num2;
      num2 =  numN;
    }
    return numN;
  }
  console.log(Fibonacci(10));

時間復雜度為O(N)。

青蛙跳臺階問題

一只青蛙一次可以跳上1級臺階，也可以跳上2級。求該青蛙跳上一個n級的臺階總共有多少種跳法。

思路:登上n階臺階問題可以轉(zhuǎn)換成登上n-2個臺階方式加上登上n-1個臺階加上登上n-3個臺階....加到登上1個臺階方式之和再加上一次登上總臺階和的問題
即有公式 f(n)=f(n-1)+f(n-2) +f(n-3)+......+f(3)+f(2)+(1)+1 。

我們不難看出這實際上就是斐波那契數(shù)列了。

  function jumpFloor(n)
  {
    if (n == 0 || n == 1) {
      return n;
    }
    if(n == 2) {
      return 2;
    }
    let num1 = 1;
    let num2 = 2;
    let numN = 0;
    for (let i = 3; i <= n; i++) {
      numN = num1 + num2;
      num1 = num2;
      num2 =  numN;
    }
    return numN;
  }
  console.log(jumpFloor(10))

{{BANNED}}跳臺階問題

一只青蛙一次可以跳上1級臺階，也可以跳上2級……它也可以跳上n級。求該青蛙跳上一個n級的臺階總共有多少種跳法。

用Fib(n)表示跳上n階臺階的跳法數(shù)。
當n = 1 時，只有一種跳法，即1階跳：Fib(1) = 1;
當n = 2 時，有兩種跳的方式，一階跳和二階跳：Fib(2) = 2;
到這里為止，和普通跳臺階是一樣的。
當n = 3 時，有三種跳的方式，第一次跳出一階后，對應Fib(3-1)種跳法；第一次跳出二階后，對應Fib(3-2)種跳法；第一次跳出三階后，只有這一種跳法。Fib(3) = Fib(2) + Fib(1)+ 1 = Fib(2) + Fib(1) + Fib(0) = 4;
當n = 4時，有四種方式：第一次跳出一階，對應Fib(4-1)種跳法；第一次跳出二階，對應Fib(4-2)種跳法；第一次跳出三階，對應Fib(4-3)種跳法；第一次跳出四階，只有這一種跳法。所以，F(xiàn)ib(4) = Fib(4-1) + Fib(4-2) + Fib(4-3) + 1 = Fib(4-1) + Fib(4-2) + Fib(4-3) + Fib(4-4) 種跳法。
當n = n 時，共有n種跳的方式，第一次跳出一階后，后面還有Fib(n-1)中跳法；第一次跳出二階后，后面還有Fib(n-2)中跳法..........................第一次跳出n階后，后面還有 Fib(n-n)中跳法。Fib(n) = Fib(n-1)+Fib(n-2)+Fib(n-3)+..........+Fib(n-n) = Fib(0)+Fib(1)+Fib(2)+.......+Fib(n-1)。
通過上述分析，我們就得到了通項公式：

             Fib(n) =  Fib(0)+Fib(1)+Fib(2)+.......+ Fib(n-2) + Fib(n-1)

因此，有

Fib(n-1)=Fib(0)+Fib(1)+Fib(2)+.......+Fib(n-2)

兩式相減得：

Fib(n)-Fib(n-1) = Fib(n-1)         =====》  Fib(n) = 2*Fib(n-1)     n >= 3

這就是我們需要的遞推公式：Fib(n) = 2*Fib(n-1) n >= 3

  function jumpFloorII(n)
  {
    if (n == 0 || n == 1) {
      return n;
    }
    if(n == 2) {
      return 2;
    }
    let num2 = 2;
    let numN = 0;
    for (let i = 3; i <= n; i++) {
      numN =  2 * num2;
      num2 = numN;
    }
    return numN;
  }
  console.log(jumpFloorII(10))

GPU云服務器云服務器算法與數(shù)據(jù)結構數(shù)據(jù)結構與算法數(shù)據(jù)結構與算法教程數(shù)據(jù)結構與算法答案

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

轉(zhuǎn)載請注明本文地址：http://systransis.cn/yun/107481.html

數(shù)據(jù)結構與算法:常見排序算法

摘要：這是一個簡單的遞歸函數(shù)，你可以使用它來生成數(shù)列中指定序號的數(shù)值這個函數(shù)的問題在于它的執(zhí)行效率非常低有太多值在遞歸調(diào)用中被重新計算。本章內(nèi)容銜接上一章　數(shù)據(jù)結構與算法：二分查找內(nèi)容提要兩種基本數(shù)據(jù)結構：數(shù)組常見操作: 數(shù)組降維、數(shù)組去重鏈表遞歸：遞歸是很多算法都使用的一種編程方法　　- 如何將問題分成基線條件和遞歸條件　　- 分而治之策略解決棘手問題 ...

wuyumin 2019-07-30 15:33 評論0 收藏0
數(shù)據(jù)結構與算法:常見排序算法

摘要：這是一個簡單的遞歸函數(shù)，你可以使用它來生成數(shù)列中指定序號的數(shù)值這個函數(shù)的問題在于它的執(zhí)行效率非常低有太多值在遞歸調(diào)用中被重新計算。本章內(nèi)容銜接上一章　數(shù)據(jù)結構與算法：二分查找內(nèi)容提要兩種基本數(shù)據(jù)結構：數(shù)組常見操作: 數(shù)組降維、數(shù)組去重鏈表遞歸：遞歸是很多算法都使用的一種編程方法　　- 如何將問題分成基線條件和遞歸條件　　- 分而治之策略解決棘手問題 ...

Carson 2019-08-26 11:32 評論0 收藏0
Javascript 深入學習循環(huán)

摘要：遞歸函數(shù)還會受到瀏覽器調(diào)用棧的大小的限制。雖然迭代也會導致性能問題，但是使用優(yōu)化的循環(huán)就可以代替長時間運行的遞歸函數(shù)，可以提高新能，因為運行一個循環(huán)比反復調(diào)用一個函數(shù)的開銷要小。本文章記錄本人在深入學習js循環(huán)中看書理解到的一些東西，加深記憶和并且整理記錄下來，方便之后的復習。選擇正確的循環(huán)體在大部分編程語言中，代碼執(zhí)行的時間多數(shù)消耗在循環(huán)的執(zhí)行上。 js定義了4種...

Cristalven 2019-08-22 10:57 評論0 收藏0
[翻譯] JS的遞歸與TCO尾調(diào)用優(yōu)化

這兩天搜了下JS遞歸的相關文章，覺得這篇文章很不錯，就順手翻譯了下，也算給自己做個筆記，題目是我自己加的。原文很長，寫得也很詳盡，這里并非逐字翻譯，而是作者所講的主要概念加上我自己的一些理解，本文中解決方案的實際意義并不是特別大，但算法的邏輯挺有意思，不過也略抽象，理解需要花點時間（囧，估計我太閑了）文中的用例?全部來自原文：原文鏈接：（原題為：理解JS函數(shù)式編程中的遞歸）Underst...

pekonchan 2019-08-21 10:49 評論0 收藏0
對于遞歸的傲慢與偏見

摘要：對于函數(shù)調(diào)用開銷，可以利用尾遞歸來解決，不過目前的引擎并沒有實現(xiàn)對尾遞歸的優(yōu)化，所以最開始我以為遞歸沒有理由比非遞歸更快。遞歸與堆棧非遞歸的算法使用一個堆棧來實現(xiàn)。最近刷leetcode 79題 Word Search需要用到DFS算法，由于是刷leetcode，心想不能用遞歸，影響效率，于是利用stack完成。之后又利用遞歸（使用cache）實現(xiàn)了一次，結果竟然是遞歸的算法比非遞歸...

Labradors 2019-08-23 12:58 評論0 收藏0