Mach doch mal die unnoetigen Header, und die Pause heraus ....
Mach doch mal die unnoetigen Header, und die Pause heraus ....
--"When I was in college, there were certain words you couldn't say in front of a girl," "Now you can say them, but you can't say 'girl." - Tom Lehrer
Für Fibonacci braucht man ja nicht viele Rechenarten... Haben wir damals im Programmieren-Kurs als Übung auch implementieren müssen, rauszufinden, wann die Fibonacci-Zaheln 80-stellig werden. Einfach die Zahlen als Byte-Array und die Addition dafür implementieren, ziemlich easy.
Die Fibonacci-Reihenfolge ist auch mehr ein Rekursives Problem, als ein Iteratives.Zitat von Irian
Per Rekursion wäre der Algorithmus ein zwei-Zeiler.
Und ein Speicherkiller. Bedenke, dass für jeden Rekursionsschritt neuer Speicher reserviert wird, der erst wieder freigegeben wird, wenn alle danach gestarteten Rekursionsschritte wieder beendet wurden. Grade, wenn man mit BigInteger arbeitet, wird das schnell böse.
--
Hatten das grad am Diesntag, Das Problem rekursiv zu bearbeiten ist echt ne Killer selbst für Großrechner (auf dem wir das probiert haben). Iterativ wäre hier echt besser, das dauert das keine Sekunde.
Edit:
Arg, jetzt erst seh ich dein Post DFYX >.<
Also Dito 8'D
--
Sicherlich.
Dennoch ist und bleibt die Fibonacci-Folge ein Rekursives Gesetz. Obs nun besser wäre oder nicht, sei mal dahingestellt.
Das selbe trifft auch beim Floodfill-Algorithmus (Zum Füllen von Flächen) zu. Rekursiv nur ein paar Zeilen aber die Rekursionstiefe ist so enorm, dass selbst aktuelle Maschinen bei einem Bild von 500x500 Pixeln in die Knie gehen.
Das war so ne Falle in meiner Algorithmen&Datenstrukturen-Prüfung... Eine (versteckte) Fibonacci-Reihe möglichst schnell zu berechnen. Die Reihe mag ja rekursiv definiert sein, aber sie am Computer rekursiv zu berechnen ist so ziemlich die schlechteste Methode - nicht nur weil mehr Speicher gebraucht wird, sondern auch, weil diverse Schritte sehr oft wiederholt werden müssen. Typische Gefahr bei der Rekursion, es ist oft die eleganteste Möglichkeit, etwas zu definieren, aber nicht notwendigerweise die beste, ums zu implementieren.
Iterativ ist etwas besser, da steigt die Rechenzeit wenigstens nur linear an. So haben wir das damals in Programmieren gemacht.
Für die ganz ungeduldigen gibts auch einfach die Formel von Moivre-Binet :-)
Berechtigungen
Zitieren
