查找斐波那契數的最佳途徑

斐波那契數列是0 1 1 2 3 5 8 ...依此類推。它可以通過交換元素並顯示它們來獲得，而我們可以使用數組來獲得它。有人問我使用遞歸的採訪和主要邏輯是它找到，查找斐波那契數的最佳途徑

int fib(int n){ 
if(n<1) 
    return 1; 
else 
    return fib(n-1)+fib(n-2);}

它產生堆棧大數目的問題，因爲我們在這裏日益複雜。那麼什麼是最佳方式？

來源

2017-03-08 Rajesh Navagare

請發佈有效的Java代碼或更改標籤 –

@LuisMuñoz此代碼是我的Java程序中的方法。這種方法對於java來說什麼是無效的？ –

使代碼可行以運行更大數字的標準方法是使用便於在Java中實現的memoization（https://en.wikipedia.org/wiki/Memoization）。但是 - 斐波納契數字非常快速地增長，所以你會很快遇到'int'可以容納的問題，所以你應該切換到大整數。另一個想法是讓一個遞歸輔助函數返回兩對連續斐波那契數的對*這將消除雙遞歸這是主要問題。 –

記憶。創建邏輯來計算每個fib麻木只有一次。

static BigInteger[] fibNumbs = new BigInteger[10000]; 


public static void main(String[] args) { 
     fibNumbs[1] = BigInteger.ONE; 
     fibNumbs[2] = BigInteger.ONE; 
     System.out.println(fibOf(10000)); 
    } 

public static BigInteger fibOf(int n) { 
     if (n <= 1) { 
      return BigInteger.ONE; 
     } 

     if (fibNumbs[n - 1]==null) { 
      fibNumbs[n - 1] = fibOf(n - 1); 
     } 

     if (fibNumbs[n - 2]==null) { 
      fibNumbs[n - 2] = fibOf(n - 2); 
     } 

     return fibNumbs[n - 1].add(fibNumbs[n - 2]); 
    }

來源

2017-03-08 16:46:55

我知道這一點。我想要它的代碼格式。見我正在返回添加fib（n-1）和fib（n-2），其中fib（n-1）將在下次調用時計算fib（n-2），這是需要存儲在某處以便我可以添加它。所以複雜性會降低。與陣列三元運算符可以幫助，但我期待更好的方式。 –

如果我告訴你兩個連續斐波那契數字，例如。 a=3和b=5，你可以猜測下一個？這是兩個總結如此8。現在用a=5和新計算的數字b=8你可以計算下一個？你開始迭代的第一個0，1和你想要的每個迭代的數字索引你倒計數，當你打到零a是你的答案。這是一個O（n）算法。

來源

2017-03-08 21:01:32 Sylwester

是的，它可以單獨執行循環和O（n）的數組。但我的要求是使用遞歸的解決方案，如上所述，複雜性較低。使用遞歸是堆棧管理的壞習慣，我知道這一點，但我被要求這個解決方案來檢查我的優化算法。 –

@RajeshNavagare當遞歸調用處於尾部位置並且語言支持尾部調用優化時，循環和遞歸函數之間沒有區別。許多語言例如。 GNU擴展到C++。該算法只是相同的，而不是更新變量的值，您將值更新爲遞歸調用，並且變量實質上是綁定參數。 – Sylwester

查找斐波那契數的最佳途徑

回答

相關問題