Hallo Leute,
ich bin gerade dabei das Thema Rekursion und die dynamische Programmierung zu lernen.
Meine Aufgabe für dieses Programm ist, dass ich aus int v und int g (v <= 123; g <= 123) alle verschiedenen Kombinationsmöglichkeiten herausfinden soll, wobei ich ein g immer nur einmal verwenden darf (wenn einmal in einer Kombinationsmöglichkeit drin, darf ich es nie wieder verwenden).
Das Ganze soll dynamisch programmiert werden, also alle Ergebnisse in einer Tabelle abspeichern und bei jedem neuen Ergebnis in der Tabelle vergleichen, ob die berechnete Kombi schon einmal vorkam. Die Rekursion hab ich nun schon hinbekommen und die ist auch richtig. Hier erstmal mein bisheriger Code.
Mein Problem liegt jetzt in der Abspeicherung der einzelnen Kombis und sie dann zu vergleichen. Ich hab mir gedacht, dass ich ja jeden Rekursionsschritt anfangen muss mit der Überprüfung ob an der Stelle [v][g] schon was gespeichert ist. Wenn da nix ist, führe ich die Rekursion aus, wenn schon, dann eben nicht und gehe gleich, solange eben noch genügend v und g habe. Bloß ich weiß nicht, wie ihm nach jedem Rekursionsschritt sage, dass er die gerade herausgefundene Kombi an der Stelle [v][g] abspeichern soll. Logisch gesehen müsste ich das ja nach dem return essen(v-1,g-1)+v*essen(v,g-1); machen und irgendwie ne for() schleife muss auch rein um alle v und g durchzugehen oder?
Bin für jede Hilfe dankbar!
Liebe Grüße
lollipol27
ich bin gerade dabei das Thema Rekursion und die dynamische Programmierung zu lernen.
Meine Aufgabe für dieses Programm ist, dass ich aus int v und int g (v <= 123; g <= 123) alle verschiedenen Kombinationsmöglichkeiten herausfinden soll, wobei ich ein g immer nur einmal verwenden darf (wenn einmal in einer Kombinationsmöglichkeit drin, darf ich es nie wieder verwenden).
Das Ganze soll dynamisch programmiert werden, also alle Ergebnisse in einer Tabelle abspeichern und bei jedem neuen Ergebnis in der Tabelle vergleichen, ob die berechnete Kombi schon einmal vorkam. Die Rekursion hab ich nun schon hinbekommen und die ist auch richtig. Hier erstmal mein bisheriger Code.
Java:
public class VeggieWahn {
public static long essen(int v, int g) {
long [][] table = new long [124][124];
return 2 * essenHelper(v, g, table);
}
public static long essenHelper (int v, int g, long [][] table) {
if (table[v][g] != 0) {
return table[v][g];
}
if (v == g){
return 1;
}
if (v == 1){
return 1;
}else {
return essen(v-1,g-1)+v*essen(v,g-1);
}
}
}Mein Problem liegt jetzt in der Abspeicherung der einzelnen Kombis und sie dann zu vergleichen. Ich hab mir gedacht, dass ich ja jeden Rekursionsschritt anfangen muss mit der Überprüfung ob an der Stelle [v][g] schon was gespeichert ist. Wenn da nix ist, führe ich die Rekursion aus, wenn schon, dann eben nicht und gehe gleich, solange eben noch genügend v und g habe. Bloß ich weiß nicht, wie ihm nach jedem Rekursionsschritt sage, dass er die gerade herausgefundene Kombi an der Stelle [v][g] abspeichern soll. Logisch gesehen müsste ich das ja nach dem return essen(v-1,g-1)+v*essen(v,g-1); machen und irgendwie ne for() schleife muss auch rein um alle v und g durchzugehen oder?
Bin für jede Hilfe dankbar!
Liebe Grüße
lollipol27
