Fibonacci rekursiv mittels Cache

[mseep]

Hi Leute,

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:

public class FibonacciCache {

    private static int aufrufe = 0;
    private static int fib(int n, int[] cache) {
        aufrufe++;
        if(n <= 0){
            return 0;
        }
        
        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;
        }
        else if(cache [n-3] != 0){
            int result = fib(n-1, cache) + cache[n-3];
            cache[n-1] = result;
            return result;
        }
        else if(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;
        }
    }

   
    public static void main(String []args) {
        int n = Integer.parseInt(args[0]);
        int[] cache = new int[n];
        System.out.println("fib(" + n + ") = " + fib(n, cache) + " (Aufrufe = " + aufrufe + ")");
       
        //for(int i = 0; i < n; i++){
        //    System.out.println(cache[i]);
        //}
    }

Vielen Dank im Voraus!

 

[KaffeeFan]

Hey,
vielleicht hilft dir das weiter: http://www.java-forum.org/thema/fibonacci-folge.123595/

Gruß
Lukas

 

[mseep]

Hey,
vielleicht hilft dir das weiter: http://www.java-forum.org/thema/fibonacci-folge.123595/

Gruß
Lukas

Vielen Dank für die schnelle Antwort, aber leider hilft mir das absolut nicht weiter.

 

[Joose]

Eines der Probleme ist die Reihenfolge bei den if/else Bedingungen

  if(cache [n-2] != 0){
  int result = cache[n-2] + fib(n - 2, cache);
  cache[n-1] = result;
  return result;
  }
  else if(cache [n-3] != 0){
  int result = fib(n-1, cache) + cache[n-3];
  cache[n-1] = result;
  return result;
  }
  else if(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;
  }
  }

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.

 

[VfL_Freak]

Moin,

Vielen Dank für die schnelle Antwort, aber leider hilft mir das absolut nicht weiter

Ach ... und warum nicht ??
Da steht doch alles drin

Gruß Klaus

 

[mseep]

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.

Moin,

Ach ... und warum nicht ??
Da steht doch alles drin

Gruß Klaus

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...

 

[JStein52]

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 ?

 

[mseep]

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 ?

na mit der antwort kann ich was anfangen, dank dir! ich mach mir mal meine gedanken dazu und versuchs umzusetzen

 

[kneitzel]

Hi Klaus,

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.

Viele Grüße,

Konrad

 

[JStein52]

Ich kann meinen vorherigen Beitrag gerade nicht mehr editieren aber das ist auch Schmarrn.

 

[mseep]

Hi Klaus,

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.

Viele Grüße,

Konrad

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

 

[kneitzel]

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.)

Konrad

 

[klauskarambulut]

import java.util.HashMap;
import java.util.Map;

/**
 *
 * @author klauskarambulut
 */
public class Fibonacci {

    public static void main(String[] args) {
        for (int i = 10; i >= 0; i--) {
            System.out.println("Fib " + i + ":  " + fib(i));
        }
    }

    private static final Map<Integer, Long> fibs = new HashMap<>();

    private static long fib(int i) {

        return fibs.computeIfAbsent(i, t -> {
            System.out.println("Calculation of " + i);
            return (t <= 1) ? 1l : fib(t - 1) + fib(t - 2);

        });
    }
}

Ist doch alles schon im Standard drin

 

[kneitzel]

Hallo klauskrambulut,

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.

Konrad

 

[JStein52]

Aber so passt es:

  private static int aufrufe = 0;
  private static int fib(int n, int[] cache) {
  aufrufe++;


  if(n <= 0){
  return 0;
  }

  fib(n-1,cache);
  if (n==1){
  cache[0] = 1;
  }
  else if (n==2) {
  cache[1] = 1;
  }
  else {
  cache[n-1]= cache[n-3] + cache[n-2];
  }
  return cache[n-1];
  }

Wichtig ist dass man zuerst in die Rekursion absteigt damit der Cache von unten gefüllt wird.

Ergebnis:
run:
fib(11) = 89 (Aufrufe = 12)
BUILD SUCCESSFUL (total time: 1 second)

Edit: die letzte Abfrage kann man vereinfachen, habe ich inzwischen schon im Code oben gemacht !

 

[kneitzel]

Also wenn man hier jetzt eine Musterlösung posten sollte, dann wäre mein Favorit:

import java.util.*;

public class ZahlenMuster {

  private static int aufrufe = 0;

  private static int fib(int n, int[] cache) {
    aufrufe++;

    if(n <= 0){
      return 0;
    }

    // switch statt der vielen ifs
    switch (n)
    {
      case 1:
      case 2:
        // 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;
        return 1;

      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".
      }
    }

    public static void main(String[] args) {
      int[] cache = new int[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)).

 

[JStein52]

@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

 

[kneitzel]

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.

Viele Grüße,

Konrad