Rekursion zur normalen Schleife konvertieren

Question

Ich habe eine Methode, die tatsächlich someValues ​​zählt. Die Methode ist unten angegeben.

public static double sum(int z, int x, int y) 
    { 
     double count = 0.0; 
     if (x == 0) 
     { 
      if (z <= 0) return 1.0; 
      return 0.0; 
     } 
     for (int i = 1; i <= y; i++) 
     { 
      count += sum(z - i, x - 1, y); 
     } 
     return count; 
    } 

Ich möchte nur diese Methode von Rekursion in normale Iteration konvertieren. Oder wenn möglich zu einer Ein-Zeilen-Gleichung. Bitte hilf mir.

Answer 1

Das ist also nicht schön, aber es funktioniert ohne Rekursion. Auch änderte ich den Rückgabetyp von Doppel aus Gründen int:

public static int sum(int z, int x, int y) 
{ 
    // Compute number of calls 
    int[][] calls = new int[x+1][x*y+1]; 
    calls[0][0] = 1; 
    for (int i = 0; i < x; i++) { 
     for (int j = 0; j <= x*y; j++) { 
      for (int target = j+1; target <= j+y && target <= x*y; target++) { 
       calls[i+1][target] += calls[i][j]; 
      } 
     } 
    } 

    // Return count of last column where z <= 0 
    int result = 0; 
    for (int j = x*y; z-j <= 0; j--) { 
     result += calls[x][j]; 
    } 
    return result; 
} 

Um zu verstehen, einen Blick auf diesem High-Tech-Excel-Blatt hat:

Dieses Diagramm einen Anruf zeigt von sum(3, 3, 3). Horizontal siehst du x und vertikal siehst du, dass beide kleiner werden. y ist 3 und nicht geändert.

Die obere linke 1 bedeutet einen Anruf an sum(3, 3, 3). Dieser Aufruf erzeugt dann drei untergeordnete Aufrufe (wegen y = 3): sum(2, 2, 3), sum(1, 2, 3) und sum(0, 2, 3). Diese drei Aufrufe finden Sie in der nächsten Spalte (mit x = 2).

Jeder dieser drei Anrufe ruft dann wieder drei Anrufe hervor, die in der Zeile x = 1 angezeigt werden. Diese neun Aufrufe überschneiden sich bezüglich z etwas. Jeder dieser neun Anrufe erzeugt dann erneut drei Anrufe, was zu 27 Anrufen in der Spalte x = 0 führt.

Um das Ergebnis zu erhalten, zählen Sie einfach alle Aufrufe in der Spalte x = 0, wobei z < = 0 ist. In diesem Beispiel ist dies jeder Aufruf, so erhalten Sie ein Ergebnis von 27. Für ein größeres z würde das Ergebnis kleiner sein.

Answer 2

public static double sum(int z, int x, int y) { 
    int num = 0;  
    for (int i = 0; i <= y; i++) { 
     if (z - x - i > 0) { 
      num++; 
     } 
    } 

    return (double) (Math.pow(y, x) - num); 
} 

Erläuterung: Ihre Methode startet höchstens y^x rekursive Aufrufe. Auf der letzten Rekursionsebene, wo x == 0, müssen Sie den maximalen Wert von während aller Anrufe ermitteln und überprüfen, wie viele dieser Anrufe haben z > 0, so dass der Anruf 0 zurückgibt und Sie müssen nicht berücksichtigen . Jetzt, auf der letzten Rekursionsstufe, ist der maximale Wert von z durch z - x gegeben. Sie zählen jetzt einfach alle Instanzen in der for Schleife, für die z - x positiv bleibt, so dass es Ihre Summe nicht beeinflusst. Nachdem Sie diese Zahl berechnet haben, subtrahieren Sie sie von der anfänglichen Annäherung des Ergebnisses, die y^x war.