迭代函數作爲箱子的遞歸函數

Question

我是新的算法，並想知道這個顯示函數應該如何從遞歸轉換/迭代到迭代。轉換時我應該記住什麼？

public int binom(int n, int k) 
{ 
    if (k == 0 || n == k) { return 1; } 

    return binom(n - 1, k - 1) + binom(n - 1, k); 
} 

在此先感謝！

Answer 1

其實，這個問題不是那麼容易的，如果你只是看遞歸代碼，並試圖對其進行解密。 然而，這可能是對你有用的提示，即（N超過K），即二項式係數可以寫成

n!/(k! * (n - k)!) 

其中「！」表示階乘。 對於你來說，計算循環中的階乘（即迭代）應該是相當容易的。

如果中間結果太大，可以在計算之前縮短。你可以縮短任一項k！或術語（n-k）！ （你會選擇更大的）。例如，對於n = 5和k = 3，您具有：（1 * 2 * 3 * 4 * 5）/（（1 * 2 * 3）*（1 * 2））=（4 * 5）/ * 2）

擾流警報：

public static int binomial(int n, int k) { 
    int nMinusK = n - k; 
    if (n < nMinusK) { 
     //Switch n and nMinusK 
     int temp = n; 
     n = nMinusK; 
     nMinusK = temp; 
    } 

    int result = 1; 

    // n!/k! 
    for (int i = k + 1; i <= n; i++) { 
     result *= i; 
    } 

    //Division by (n-k)! 
    for (int j = 1; j <= nMinusK; j++) { 
     result = result/j; 
    } 
    return result; 
} 

Answer 2

您可以使用乘法形式的二項式係數，例如從Wikia，這可以很容易地與faculties或循環實現。