數據結構與算法（遞歸與循環） --javascript語言描述

nanfeiyan 發布于2019-08-26 11:44 / 3399人閱讀

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

斐波那契數列

大家都知道斐波那契數列，現在要求輸入一個整數n，請你輸出斐波那契數列的第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));

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

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

  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階臺階問題可以轉換成登上n-2個臺階方式加上登上n-1個臺階加上登上n-3個臺階....加到登上1個臺階方式之和再加上一次登上總臺階和的問題
即有公式 f(n)=f(n-1)+f(n-2) +f(n-3)+......+f(3)+f(2)+(1)+1 。

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

  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階臺階的跳法數。
當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)種跳法；第一次跳出四階，只有這一種跳法。所以，Fib(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云服務器算法與數據結構數據結構與算法數據結構與算法教程數據結構與算法答案

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://specialneedsforspecialkids.com/yun/107481.html

數據結構與算法:常見排序算法

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

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

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

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

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

Cristalven 2019-08-22 10:57 評論0 收藏0
[翻譯] JS的遞歸與TCO尾調用優化

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

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

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

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