Rekursive Funktion zu iterativer Funktion als Binome

Question

Ich bin neu mit Algorithmen und frage mich, wie diese angezeigte Funktion von rekursiv zu iterativ konvertiert werden soll. Was sollte ich bei der Konvertierung beachten?

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

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

Vielen Dank im Voraus!

Answer 1

In der Tat ist dieses Problem nicht so einfach, wenn man sich den rekursiven Code anschauen und versuchen, es zu entschlüsseln. Allerdings könnte es ein hilfreicher Hinweis für Sie, dass (n über k), das heißt der Binomialkoeffizient als

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

wo geschrieben werden „!“ bezeichnet das Fakultätale. Und es sollte ziemlich einfach sein, die Fakultät in einer Schleife (d. H. Iterativ) für Sie zu berechnen.

Wenn die Zwischenergebnisse zu groß sind, können Sie vor der Berechnung verkürzen. Sie können einen der beiden Term k verkürzen! oder der Begriff (n-k)! (Sie würden den größeren wählen). Zum Beispiel mit n = 5 und k = 3 haben Sie: (1 * 2 * 3 * 4 * 5)/((1 * 2 * 3) * (1 * 2)) = (4 * 5)/(1 * 2)

Spoiler-Alarm:

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

Sie können die multiplikative Form von Binomialkoeffizienten verwenden, zum Beispiel von Wikia, die leicht mit Fakultäten oder Schleifen implementiert werden kann.