Einfache rekursive Methode konvertieren, die innerhalb einer Schleife in iterative Methode recursiert

Question

Vor einiger Zeit arbeitete ich an einem Programmierproblem (CCC). Ich bin auch auf ähnliche Fragen in vergangenen Wettbewerben gestoßen, also habe ich mich entschieden, nach diesem zu fragen. Das Problem ist im Grunde genommen das.

Sie erhalten n Menschen und p Stück Kuchen.

n Menschen stehen in einer Reihe.

Sie müssen p Stück Kuchen unter ihnen verteilen. Sie gehen in Reihenfolge und jede Person muss mindestens so viele Stücke erhalten wie die Person vor ihnen. Jede Person muss mindestens ein Stück Kuchen erhalten und kein Kuchen darf übrig bleiben.

Sie müssen die Anzahl der möglichen Verteilungswege für den Kuchen angeben.

konnte ich die folgende rekursive Lösung schaffen, aber es dauert zu lange (mehr als 5 Sekunden) für die folgenden Eingänge:

120 Stück, 20 Personen -> 97132873

250 Stück, 130 Personen -> 1844349560

Meine Lösung:

import java.io.*; 

public class Main 
{ 
    int pieces, people; 
    int combinations = 0; 

    public void calculate (int person, int piecesLeft, int prev) 
    { 
    if (person == people) 
    { 
     if (piecesLeft == 0) 
      combinations++;    
    } 
    else 
    { 
     for (int x = prev ; (x * (people - person)) <= piecesLeft ; x++) 
     { 
      calculate (person + 1, piecesLeft - x, x); 
     } 
    } 
    } 


    public static void main (String[] args) throws Exception 
    { 
    Main m = new Main(); 
    BufferedReader in = new BufferedReader (new InputStreamReader (System.in)); 
    //m.pieces = Integer.parseInt (in.readLine()); 
    //m.people = Integer.parseInt (in.readLine()); 
    m.pieces=250; 
    m.people=130; 
    if (m.people == m.pieces) 
     System.out.println (1); 
    else if (m.people == 1) 
     System.out.println (1); 
    else 
    { 
     m.calculate (0, m.pieces, 1); 
     System.out.println (m.combinations); 
    } 
    } 
} 

ich die folgende python-Lösung aus den inoffiziellen Lösungen gefunden, die von dem, was ich unders tand, erstellt im Grunde eine Reihe von bereits angetroffenen Werten.

visited = [] 
def pi(n,k,min): 
if visited [n][k][min] == 0:  
    if n == k: 
     visited[n][k][min] = 1 
    elif k == 1: 
     visited[n][k][min] = 1 
    else: 
     t = 0 
     for i in range (min, (n/k)+1): 
      t = t + pi(n-i, k-1, i) 
     visited[n][k][min] = t 
return visited[n][k][min] 


file = open("j5.10.in", "r") 
n = int(file.readline()) 
k = int(file.readline()) 

for i in range(n+1): 
x = [] 
for j in range(k+1): 
    t = [] 
    for kk in range(n+1): 
     t.append (0) 
    x.append(t) 
visited.append(x) 

print pi(n,k,1) 

Was ich tun möchte, ist eine iterative Lösung aus diesen beiden, aber bin mir nicht sicher, wie es geht. Von dem, was ich verstehe, gibt es möglicherweise keine große Geschwindigkeitsdifferenz, aber mit noch größeren Fällen erlaubt es mir, Stapelüberläufe zu vermeiden.

Answer 1

Die zweite Lösung ist gemoised ... die visited Array Datensätze Werte, die bereits berechnet wurden. Ein Trick, um eine Memo-Rekursion in eine (Art von) iterierte Lösung umzuwandeln, besteht darin, kleinere Fälle zu durchlaufen, um das Memo-Array auszufüllen. Sie können die Ergebnisse für die kleineren Fälle einfach wegwerfen (sie werden sowieso im Memo-Array gespeichert). Dann, wenn Sie schließlich die gewünschte berechnen, wird das Memo-Array sofort verwendet, keine zusätzliche Berechnung.

Wenn Sie wirklich eine iterative Lösung von Grund auf aufbauen möchten, müssen Sie herausfinden, welche vorherigen Fälle Sie speichern müssen, um den nächsten Fall aufzubauen. Um beispielsweise faktoriell mit einer Schleife zu berechnen, müssen Sie nur einen Wert im Speicher speichern. In einem Änderungsproblem mit Münzen der Nennwerte 1, 5 und 10 Cent, müssten Sie nur zehn vorherige Elemente speichern, um das nächste zu konstruieren. In einigen Fällen müssen Sie alle vorherigen Werte kennen, um den nächsten zu konstruieren. Sobald Sie das wissen, sollte die Speicherstruktur klar sein, dann wird die Programmlogik klar.