meine Aufgabe ist es die n-te Zahl der Fibonacci-Folge rekursiv zu berechnen, wobei die Methode mittels eines Caches für jedes n höchstens einmal aufgerufen werden soll, sodass am Ende die Methode maximal n+1 mal aufgerufen wurde. Ich hab viel nachgedacht, viel rumprobiert, komme aber leider nicht unter 2n-3 Aufrufe. Ich wär Euch sehr dankbar, wenn Ihr mir helfen könntet meinen Denkfehler zu finden, bzw meine Gedanken in die richtige Richtung zu lenken:
Java:
publicclassFibonacciCache{privatestaticint aufrufe =0;privatestaticintfib(int n,int[] cache){
aufrufe++;if(n <=0){return0;}
cache[0]=1;if(cache[n-1]!=0){return cache[n-1];}if(cache [n-2]!=0){int result = cache[n-2]+fib(n -2, cache);
cache[n-1]= result;return result;}elseif(cache [n-3]!=0){int result =fib(n-1, cache)+ cache[n-3];
cache[n-1]= result;return result;}elseif(cache[n-2]!=0&& cache[n-3]!=0){int result = cache[n-2]+ cache[n-3];
cache[n-1]= result;return result;}else{int result =fib(n-1, cache)+fib(n -2, cache);
cache[n-1]= result;return result;}}publicstaticvoidmain(String[]args){int n =Integer.parseInt(args[0]);int[] cache =newint[n];System.out.println("fib("+ n +") = "+fib(n, cache)+" (Aufrufe = "+ aufrufe +")");//for(int i = 0; i < n; i++){// System.out.println(cache[i]);//}}
Du fragst zuerst einzeln nach ob "cache[n-2]" bzw. "cache[n-3]" ungleich 0 sind und dann erst ob beiden ungleich 0 sind.
Sobald einer der beiden Plätze im Cache != 0 ist wird das 3.else-if nicht mehr betreten, da davor eine der beiden Bedingungen erfüllt ist.
Eines der Probleme ist die Reihenfolge bei den if/else Bedingungen
Du fragst zuerst einzeln nach ob "cache[n-2]" bzw. "cache[n-3]" ungleich 0 sind und dann erst ob beiden ungleich 0 sind.
Sobald einer der beiden Plätze im Cache != 0 ist wird das 3.else-if nicht mehr betreten, da davor eine der beiden Bedingungen erfüllt ist.
jap ist mir auch aufgefallen :/ überprüf ich zuerst ob beide gleich null sind, krieg ich ne ArrayOutOfBounds-Exception, da ich für n = 2 die -1-te stelle im cache auf ungleichheit mit 0 überprüfe, welche ja gar nicht existiert. dann muss ich da wohl noch rumschrauben.
dann muss ich blind sein hab da keinen lörungsansatz für die berechnung mittels rekursion und eines cache-arrays gefunden, nur iterativ über ein array...
Du bist nicht blind. Der Link hat mit cache nichts zu tun, und das ist ja dein Problem. Ich wage mal die These du musst da andeers ran gehen. Deine Rekursion (und so macht man das üblicherweise ohne Cache ) rechnet ja von grösseren n's zu kleineren. Da wird der Cache doch nie gefüllt sein. Du sparst dir sozusagen nur die letzten 3 Aufrufe und deshalb 2n-3 !! Musst du hier nicht von kleineren zu grösseren n's gehen ?
Du bist nicht blind. Der Link hat mit cache nichts zu tun, und das ist ja dein Problem. Ich wage mal die These du musst da andeers ran gehen. Deine Rekursion (und so macht man das üblicherweise ohne Cache ) rechnet ja von grösseren n's zu kleineren. Da wird der Cache doch nie gefüllt sein. Du sparst dir sozusagen nur die letzten 3 Aufrufe und deshalb 2n-3 !! Musst du hier nicht von kleineren zu grösseren n's gehen ?
das Problem vom TE ist ja nicht die eigentliche Berechnung der Fibonacci Zahl sondern die Reduzierung der rekursiven Aufrufe. Das wird da nicht behandelt. In dem Thread wird nur kurz dargestellt, dass diverse Fibonacci-Zahlen mehrfach berechnet werden (am Beispiel der fib(5).). Bezüglich der Problematik dürfte Joose einen Fehler gefunden haben. Aber die ganze Logik scheint mir noch zu komplex zu sein.
Fib(n) = fib(n-1) + fib(n-2)
Also ist fib(n-1) = fib(n-2) + fib(n-3)
Das bedeutet, dass bei der Berechnung von fib(n-1) auch fib(n-2) berechnet werden muss.
Somit gilt, dass wenn fib(n-1) bekannt ist, dann ist auch fib(n-2) bekannt. Hier gibt es am Anfang nur eine einzige Ausnahme: Es wird nur das erste Feld initialisiert und dann bei der ersten Berechnung bräuchte man zwei Werte. Das kann man mit einer zusätzlichen IF Anweisung lösen, aber ich würde da einfach ein Array-Feld des Caches mehr verbrauchen. Ich würde fib(n) in cache[n] speichern. Dann würde der cache initialisiert mit cache[0] = 0; cache[1] = 1;
Das führt dann zu einem sehr einfachen Code:
- Wenn cache[n-1] unbekannt, dann cache[n-1] = fib(n-1) -> Rekursiver Aufruf.
- cache[n] = cache[n-1]+cache[n-2]
- cache[n] zurück geben.
Desweiteren fällt mir auf, dass die Initialisierung des caches unschön ist. Hier würde ich objektorientiert heran gehen und das in eine eigene Klasse tun. Der Konstruktor würde dann die ersten zwei Felder initialisieren. Bei fin(1000) werden die ersten Felder sonst tausend mal gesetzt was ja nicht sein muss.
das Problem vom TE ist ja nicht die eigentliche Berechnung der Fibonacci Zahl sondern die Reduzierung der rekursiven Aufrufe. Das wird da nicht behandelt. In dem Thread wird nur kurz dargestellt, dass diverse Fibonacci-Zahlen mehrfach berechnet werden (am Beispiel der fib(5).). Bezüglich der Problematik dürfte Joose einen Fehler gefunden haben. Aber die ganze Logik scheint mir noch zu komplex zu sein.
Fib(n) = fib(n-1) + fib(n-2)
Also ist fib(n-1) = fib(n-2) + fib(n-3)
Das bedeutet, dass bei der Berechnung von fib(n-1) auch fib(n-2) berechnet werden muss.
Somit gilt, dass wenn fib(n-1) bekannt ist, dann ist auch fib(n-2) bekannt. Hier gibt es am Anfang nur eine einzige Ausnahme: Es wird nur das erste Feld initialisiert und dann bei der ersten Berechnung bräuchte man zwei Werte. Das kann man mit einer zusätzlichen IF Anweisung lösen, aber ich würde da einfach ein Array-Feld des Caches mehr verbrauchen. Ich würde fib(n) in cache[n] speichern. Dann würde der cache initialisiert mit cache[0] = 0; cache[1] = 1;
Das führt dann zu einem sehr einfachen Code:
- Wenn cache[n-1] unbekannt, dann cache[n-1] = fib(n-1) -> Rekursiver Aufruf.
- cache[n] = cache[n-1]+cache[n-2]
- cache[n] zurück geben.
Desweiteren fällt mir auf, dass die Initialisierung des caches unschön ist. Hier würde ich objektorientiert heran gehen und das in eine eigene Klasse tun. Der Konstruktor würde dann die ersten zwei Felder initialisieren. Bei fin(1000) werden die ersten Felder sonst tausend mal gesetzt was ja nicht sein muss.
das blöde ist nur, dass cache[n] nicht existiert, da cache[] ja nur mit n stellen deklariert wird. die main war in der aufgabe vorgegeben und darf nicht verändert werden. abgegeben werden darf nur EINE .java-datei, also fällt die objektorientierte umsetzung auch flach, alles ein wenig verzwickt
Ok, das mit dem objektorientierten Ansatz ist ja auch nicht so wild. Wie die Werte gespeichert werden ist ja nicht ganz so wichtig. Wenn man fib(0) nicht im cache speichern kann, dann kann man das ja über ein einfache if abhandeln.
Man muss dann halt:
- zwei cache Werte sichern.
- Erst prüfen, ob der cache für die gewünsche Zahl schon gefüllt ist.
- Dann die eigentliche Lösung wie von mir beschrieben.
Und damit nicht unnötig Prüfungen stattfinden kann man sogar den Code noch auf Zwei Funktionen aufteilen. Deine fib Funktion hat dann nur noch reine Initialisierung und Prüfung des Caches und die Rekursion mit Berechnungen ist dann komplett in einer (privaten) Funktion BerechneFibonacci oder so. (Was aber evtl. von der Aufgabenstellung auch ausgeschlossen ist.)
das erfüllt aber nicht die Anforderungen des TE. Es war explizit verlangt, die Anzahl der fib Aufrufe zu minimieren und das ist bei Deiner Implementation nicht gegeben. Wenn Du fib(t-1) berechnest dann kannst Du im Anschluss direkt fib(t-2) aus dem Cache nehmen. Hier zwei fib Aufrufe zu verwenden ist einfach nicht sinnvoll und sorgt für deutlich mehr Aufrufe von fib.
Also wenn man hier jetzt eine Musterlösung posten sollte, dann wäre mein Favorit:
Java:
importjava.util.*;publicclassZahlenMuster{privatestaticint aufrufe =0;privatestaticintfib(int n,int[] cache){
aufrufe++;if(n <=0){return0;}// switch statt der vielen ifsswitch(n){case1:case2:// Hier finde ich die Lösung interessant, dass der Cache nur einmal gesetzt wird. Gefiel mir gut bei JStein52
cache[0]=1;
cache[1]=1;return1;default:if(cache[n-2]==0)fib(n-1,cache);// Diese Stelle gefiel mir eigentlich nicht - die Rückgabe wird ignoriert. Aber das erspart uns ein mehrfachen code.return cache[n-1]= cache[n-2]+ cache[n-3];// Sollte man evtl. in zwei Zeilen machen. Return mit einer Zuweisung ist evtl. in den Augen vieler nicht "sauber".}}publicstaticvoidmain(String[] args){int[] cache =newint[20];int fib20 =fib(20, cache);for(int i =0; i<20; i++){System.out.println(cache[i]);}System.out.println(aufrufe);}}
Hat im Vergleich zu der Lösung von JStein52 zwei Aufrufe weniger (19 statt 21 bei Berechnung von fib(20)).
@kneitzel : Ist das gleiche aber die Abfrage im default-Zweig kannst du dir schenken. Das entspricht meinem letzten else.
Und du hast nur zwei Aufrufe weniger weil du es anders initialisierst. Daqs hatte ich auch zuerst aber ich dachte der TE wollte n+1 Aufrufe
Jo, stimmt. Habe wohl nicht gut genug hingesehen. Aber hast mit Deiner Sicht natürlich Recht. Die Initialisierung im if von Dir fand ich übrigens eine sehr gute Idee. Das hatte ich zuerst so nicht gesehen.
