[Java] Rekursion von Fibonacci mit einem Buffer

SnusMaster · 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

Anzeige

Korona · 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

SnusMaster · 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!!

Deepercut · 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;
}

Korona · 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!

smokie88 · 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

Korona · 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*

smokie88 · 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;
}

Nützliche Suchen

[Java] Rekursion von Fibonacci mit einem Buffer

Videos zum Themenbereich