[Java] Rekursion von Fibonacci mit einem Buffer

Dieses Thema im Forum "Programmierung & Entwicklung" wurde erstellt von SnusMaster, 28. Oktober 2008 .

  1. 28. Oktober 2008
    Rekursion von Fibonacci mit einem Buffer

    Hi @all,

    Hab folgende Aufgabe:

    Die Rekursive Fibonacci Folge zu Optimieren (Aber nicht iterativ lösen!!)
    und zwar mit einem Buffer!



    Schreib euch schonmal meine Fibonacci Rekursion welche optimiert werden muss:

    Code:
    public static int fibonacciFolge(int zahl1) {
     if (zahl1 == 1 || zahl1 == 0) {
    
     return zahl1;
    
     } else {
     return fibonacciFolge(zahl1 - 1) + fibonacciFolge(zahl1 - 2);
     }
     }
    
    Ich denke dass ich irgendwie Teilantworten immer in diesen Buffer speichern muss?!

    Kennt sich da jemand aus??

    Bw iss ehren Sache, hab jetzt lange gegrübelt aber komm einfach nicht drauf!

    THX
     
  2. 29. Oktober 2008
    AW: Rekursion von Fibonacci mit einem Buffer

    Also meine idee wär da jetz Endrekursiv drann zu gehen.
    Code:
    function fiber-iter(a, b, n)
    if (n==0) return a
    else return fib-iter(b, (a+b), (n-1))
    
    function fibo(n)
    return fiber-iter 0 1 n
    
    Nur is Endrekursion eigentlich nichts anderes als Iteration.
    Alternativ schreib dir eine klasse Buffer, die Zwischenergebnisse speichert.
    Bsp: fibonacciFolge(9) => fibonacciFolge(8) + fiboF(7) => fiboF(7) +fiboF(6) + fiboF(7)
    Hier würde 2 mal FiboF(7) berechnet was natürlich überflüssig ist.
    Um das per Buffer zu machen würde ich dir auch eine Rekursion von unten nach oben also bei den kleineren anfange und solange hochzugehen bis du bei der zahl angekommen bist...

    Hoffe geholfen zu haben
     
  3. 29. Oktober 2008
    AW: Rekursion von Fibonacci mit einem Buffer

    Danke schonmal...denke dass ist schonmal ein super Ansatz!!
    Denn der Aufruf erfolgt nur noch einmal sprich die Geschwindigkeit ist besser...aber könnte man nicht irgendwie die Werte in einen Buffer schreiben und dadurch zeit gewinnen?

    BW haste natürlich schon! Danke für deine Mühe!!
     
  4. 29. Oktober 2008
    AW: Rekursion von Fibonacci mit einem Buffer

    Dein so genannter Buffer nennt man in diesem Fall auch "Dynamische Programmierung" oder auch Memoization,
    wenn danach googlest, findest z.b. das hier:

    Code:
    
    static int knownF[] = new int[1000];
    
    int fib(int n)
    {
     if( knownF[n] != 0) { return knownF[n];}
     if( n < 2)
     {
     return 1;
     }
    
     int newFib = fib(n-2) + fib(n-1);
     return knownF[n] = newFib;
    }
    
    
     
  5. 30. Oktober 2008
    AW: Rekursion von Fibonacci mit einem Buffer

    So groß muss der buffer doch gar nicht sein eine größe von n reicht doch schon!
     
  6. 1. November 2008
    AW: Rekursion von Fibonacci mit einem Buffer

    naja, so wirklich groß ist das auch nicht (außer du hast ne Uralt-Mühle )

    Das Grundkonzept eines Buffers ist es Laufzeit zu "kaufen" und in Speicherplatz zu "bezahlen". Bekannte Werte werden gespeichert und wenn sie später gebraucht werden kann schnell daruf zugegriffen werden.
    Ist ein allgemeines Grundkonzept in der Informatik
     
  7. 1. November 2008
    AW: Rekursion von Fibonacci mit einem Buffer

    Ja aber wenn er die Funktion mit n = 100000 ausführt bekommt er beim statischen Buffer nen problem *pfeif*
     
  8. 8. November 2008
    AW: Rekursion von Fibonacci mit einem Buffer

    naja, ist relativ unwahrscheinlich, weil die Fib doch irgendwann recht schnell wächst

    Aber wenn mans unabhängig von der Größe machen will, kann man ja Collections verwenden, z.B. ne HashMap (
    HashMap (Java Platform SE 6)
    ) verwenden. (ArrayList o.ä, auch denkbar, hab hier jetzt die HashMap genommen wegen der leichten Abfrage, ob an einer gewissen Stelle schon was ist, unabhängig von der momentanen Größe (containsKey(n)))

    Könnte dann ungefähr so aussehen (hab hier jetzt nix drauf zum Testen )

    Code:
    HashMap<int,int> knownF = new Hashmap<int,int>();
    
    int fib(int n)
    {
     if(knownF.containsKey(n)) 
     { 
     return knownF.get(n);
     }
    
     if( n < 2)
     {
     return 1;
     }
    
     int newFib = fib(n-2) + fib(n-1);
     knownF.put(n,newFib);
     return = newFib;
    }
    
    
     
  9. Video Script

    Videos zum Themenbereich

    * gefundene Videos auf YouTube, anhand der Überschrift.