Java: Rekursion mit Array zwischenspeichern?
Betrachten Sie die rekursiv definierte Funktion Q.
Zur Berechnung von Q(n) für höhere n sollten Sie bereits berechnete Resultate in einem Array speichern, z.B. als statisches Attribut in ihrer Klasse. Ansonsten wird der naive Ansatz nicht terminieren.
-
Hat jemand einen Vorschlag, wie das mit dem Speichern des Zwischenergebnis in einem Array gehen soll?
Ich habe da mal einen Ansatz mit einer Hilfsmethode, aber irgendwie komme ich nicht ganz drauf.
Vielen Dank im Voraus.
Smokie
public static int Q(int n) {
int[] arr = new int [1000];
for(int i = 0; i < arr.length; i++) {
arr[i] = hilfe(i);
}
return ;
}
public static int hilfe(int n) {
if(n == 1) return 1;
if(n == 2) return 1;
return Q(Q(n-1)) + Q(n-Q(n-1));
}
4 Antworten
Hat jemand einen Vorschlag, wie das mit dem Speichern des Zwischenergebnis in einem Array gehen soll?
ja: nimm dafür kein Array, sondern eine Map. Diese hat keine feste Länge und kann zu jedem Key einen Wert fassen. Und nimm das wirklich als statische Klassenvariable, sodass sich jedes Objekt dieser Klasse den Cache teilt.
Dann: Du willst ja an sich einen schon vorhandenen Wert nicht erneut ausgeben. Deshalb schaust du am Anfang der Methode, ob der entsprechende Wert schon vorhanden ist - und wenn ja, gibst du ihn zurück, ohne etwas zu berechnen.
Sonst berechnest du es einfach rekursiv über die oben genannte Formel und fügst dieses Ergebnis dann dem Cache hinzu.
Die Programmierung selbst ist einfach, ich werd dir aber nicht den Code direkt geben, sondern möchte auch von dir Verbesserung an deinem eigenen Code sehen - eigentlich hab ich ja oben eigentlich schon die Lösung genannt
Okay ich bin mir sicher, dass du in einer IDE programmierst. wie wäre es wenn deine Methode Q ein Array aus integern zurückgibt:
return arr ;
dann in der Main dir den Array anschaust.
Du hast ja auch einen debugger. Dann kannst du es ja erstmal mit einem Array der größe 4 machen. Ist unkompliziert und wenn es funktioniert, wird es auch für große Arrays funktionieren
zeig mal, was du schon hast
habe ich. die Hilfemethode an sich ist die Rekursive Folge. Die Q Methode der Array
Die Anweisung ist doch klar, das Array soll Attribut Deiner Klasse sein.
Du initialisierst es mit0 (0 ist kein legitimes Ergebnis für irgendein Q(n).
Wenn Du Q(n) berechnen willst, schaust Du erst, ob Q(n) im Array ist, wenn ja, gibst Du den Wert zurück und brichst so die Rekursion vorzeitig ab. wenn nein, berechnest Du ihn wie gewohnt udn legst ihn im Array ab, indem Du Q(n) an Position n ins Array schreibst.
Nachtrag:
Sicher, daß es
Q(1) = 1
Q(2) = 1
Q(n) = Q(Q(n-1)) + Q(n-Q(n-1))
sein soll? Und nicht Q(n-1)+Q(n-2)? Das wäre dann Fibonacci. Das andere ist nur um den Offset 1 verschoben die Gaußsche Summe.