Die Fibonacci-Funktion

Letztmalig dran rumgefummelt: 09.12.07 13:14:37

	LEONARDO VON PISA, LEONARDO PISANO - * Pisa um 1170, † ebenda nach 1240, italienischer Mathematiker. Erster bedeutender Mathematiker des Abendlandes, der seine im Orient gesammelten mathematischen Kenntnisse vermittelte. In seinem 1202 geschriebenen „Buch vom Abakus“ (lat.: liber abaci; der Abakus war das Rechenbrett der Römer) behandelte er die folgende Aufgabe: Jemand sperrt ein Kaninchenpaar in ein allseitig ummauertes Gehege, um zu erfahren, wie viele Nachkommen dieses Paar im Laufe eines Jahres haben werde. Es wird dabei vorausgesetzt, jedes Kaninchenpaar bringe monatlich ein neues Paar zur Welt und die Kaninchen würden vom zweiten Monat nach ihrer Geburt an gebären. Die Lösung überlegte sich FIBONACCI so: das eine Paar hat im ersten Monat Junge, so dass dann zwei Paare vorhanden sind. Von diesen hat im zweiten Monat nur eines Nachkommen, nämlich das erste, und nach drei Monaten leben drei Kaninchenpaare in dem Gehege. Von diesen gebären auch im folgenden Monat; das gibt dann schon fünf Paare. Und so weiter: Für die nächsten Monate erhält man der Reihe nach 8, 13, 21, 34, 55, 89, 144, 233 und schließlich 377 Kaninchenpaare nach einem Jahr. Natürlich vermehren sich lebende Kaninchen nicht so mathematisch wie die Fibonacci-Kaninchen, aber doch so ähnlich: In Australien erzeugten am Ende des vorigen Jahrhunderts zwölf freigelassene Kaninchenpaare innerhalb von 40 Jahren eine Nachkommenschaft von rund 20 Millionen Tieren! 700 Jahre nach dem Erscheinen des Liber abaci eine schöne Bestätigung der Theorie durch die Natur.
	1. Problembeschreibung 2. Hintergründe und Zusammenhänge - Einordnung in Klassen 3. Lösungsalgorithmen 4. Programmvorschläge 5. Zusammenfassung 6. Weiterführende Literatur 7. Linkliste zum Thema 8. Verwandte Themen
	Probleme & Problemlösunsverfahren Logo für das Fibonacci-Problem Informatik-Profi-Wissen
	Quellen: Lehr- und Übungsbuch Informatik Band 1 - 5 Seite ??? Technische und Theoretische Informatik  Seite ???
	Beachte vor allem bei Problemlösungsalgorithmen: Murphys Gesetze sowie deren Optimierung durch Computer sowie deren Optimierung durch Computer

1. Problembeschreibung

	Zur Anzahl der jeweils vorhandenen Kanninchenpaare kommen im Folgemonat deren Jungtiere hinzu, welche zwei Monate später wieder Nachwuchs haben (zumindest nach dem theoretischen Idealmodell).
	Die Fibonacci-Funktion
	Wertebereich der Fibonacci-Funktion
	generiert die Folge: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, ...
	grafisch dargestellt könnte das so aussehen ;-)
	Tabellarische Veranschaulichung der Fibonacci-Zahlen
	0          1 1          1 2          2 3          3 4          5 5          8 6          13 7          21 8          34 9          55 10        89 11        144 12        233 13        377 14        610 15        987 16        1.597 17        2.584 18        4.181 19        6.765 20        10.946 21        17.711 22        28.657 23        46.368 24        75.025 25        121.393 26        196.418 27        317.811 28        514.229 29        832.040 30        1.346.269 31        2.178.309 32        3.524.578 33        5.702.887 34        9.227.465 35           14.930.352 Wertetabelle der Fibonacci-Funktion für 1>=n<=35
	Rekursive Baumstruktur des Aufrufes der Fibonacci-Funktion

2. Hintergründe, Zusammenhänge - Einordnung in Klassen

	Der Lösungsalgorithmus für die Fibonacci-Funktion
	effiziente Lösung nur als rekursiver Algorithmus
	Die lineare Folge von Aufrufen wird durch dieses Beispiel eindeutig erkennbar, und die Eingabewerte n hatten nur eine Anzahl von n + 1 Aufrufen zur Folge. Es lässt sich rein rechnerisch leichter nachvollziehen. Bei den Messungen zur Laufzeit konnte keine Verzögerung festgestellt werden. Die Vorteile der endrekursiven Lösung sind sehr gut nachweisbar. Kein Stacküberlauf konnte bei einem Eingabewert von 40 festgestellt werden.
	Die Folge hat eine Reihe interessanter Eigenschaften, von denen einige nachstehend beschrieben werden. (sk bedeutet die Summe der ersten Glieder, k v N0). [1] a)               Beweis durch vollständige Induktion:          b)     c)      Der ezeugende Term lautet          Beweis: f0=0, f1=1 folgt für n=0 bzw. n=1. Für alle n vN0 gilt:          Nun ist d)     Banachbarte Fibonaccische Zahlen sind stets teilerfremd! e)    Wie findet man den erzeugenden Term? Die vielseitige Verwendbarkeit geometrischer Folgen rechtfertigt es, mit Hilfe eines solchen Ansatzes, nämlich mit fx = xn, sein Glück zu versuchen. Die Substitution fx = xn in die Rekursionsgleichung fx+2 = fn + fn+1 führt nach Division durch xn auf die charakteristische Gleichung

3. Lösungsalgorithmus

	Wenn es mindestens einen Lösungsansatz gibt, dann versuche, aus den gegebenen Wortpaaren identische Sätze auf beiden Seiten der Gleichung zu bilden. Wiederhole dies solange, bis keine weitere Möglichkeit mehr existiert.
	Rufprozedur in PASCAL Function fiboaux (n, acc1, acc2:longint):longint; Begin   if n=0   Then fiboaux:=acc1   Else  fiboaux:=fiboaux (n-1,acc2,acc1+acc2); End; Verschachtelungstiefe mit Parameterstruktur Bei Betrachtung dieses Beispiels wird der kaskadenartige Charakter deutlich sichtbar, und zwar wie stark der Stack belastet wird und der zeitliche Ablauf realisiert wird. Man stelle sich die Verzweigung und damit die Belastung bei folgenden Zahlen vor: Fib (25) = 75025 oder Fib (30) = 832040 oder Fib (35) = 9227465 Auch aus den Testergebnissen wird die Annahme und optische Vorstellung bestätigt (siehe Grafik oben). Die Anzahl der rekursiven Aufrufe verdoppelt sich solange wie Fib nicht 1 oder 0 ist. Das führt zu einer enormen Belastung mit Rechenzeit und Speicher bei hohen Eingabewerten. Dies kann auch durch andere rekursive Lösungen abgebaut werden, indem nicht echt rekursiv, sondern endständig rekursiv programmiert wird. (siehe dort)
	Es ist deutlich zu sehen, dass bei dieser Variante der rekursive Aufruf der Fibonacci-Funktion als letzte Aktion ausgelöst wird. Das o wird mit dem Wert 1 und m mit dem Wert 0 gestartet. So erhält man immer die letzte und die vorletzte Zahl der Fibonacci-Zahl nach der kompletten Abarbeitung, aller Aufrufe und m stellt dann das Ergebnis dar. Durch diese Art haben wir eine Verschachtelung vermieden, und der zeitliche Gewinn ist ab der Größenordnung von 20 und ab 30 bei schnellen Rechnern (Tabelle) erheblich.
	Beispiel: Gesucht ist die 6. Zahl in der Fibonacci-Folge: Fibonacci(0) = 1 Fibonacci(1) = 1 Fibonacci(2) = Fibonacci(2-1) + Fibonacci(2-2) + Fibonacci(1) = 2 Fibonacci(3) = Fibonacci(3-1) + Fibonacci(3-2) + Fibonacci(2) = 3 Die Fibonacci’schen Zahlen beschreiben das Anwachsen einer Kaninchenfamilie von Generation zu Generation, und zwar unter der Annahme, dass: alle Tiere unbegrenzt am Leben und zeugungsfähig bleiben und dass: jedes Tier in regelmäßigen Zeitabständen mit Ausnahme des ersten Intervalls nach seiner Geburt ein neues Tier zur Welt bringt - und zwar immer vom gleichen Geschlecht wie das jeweilige Elterntier

4. Programmvorschläge

	Rufprozedur in LOGO pr fibo :n    (wenn :n = 0 [rg 0]~                 [(wenn :n = 1 [rg 1]~                               [rg sum fibo :n-2 fibo :n-1])]) ende
	Fibonacci-Zahlen als Excel-Tabelle (das geht gut und ohne Rekursion)

5. Zusammenfassung

	Hier greifen wir unter anderem die Argumente für einen Algorithmus auf und vergleichen, ob Übereinstimmung in allen Punkten gegeben ist.
	Endlichkeit der Beschreibung ist gegeben
	Eindeutigkeit ist gegeben - jeder Schritt ist für jede Bedingung eindeutig fest vorgegeben und lässt keine Abweichung zu
	Effektivität ist gegeben - jeder Schritt ist ausführbar
	Terminierung ist nicht gegeben - der Algorithmus läuft nach erreichen des Zwischenergebnisses 91 ewig und generiert einen Stapelüberlauf
	Determiniertheit ist gegeben, der Folgeschritt nach einer Operation ist immer bekannt

6. Weiterführende Literatur

	Walter Kranzer; „So interessant ist Mathematik“; VEB Deutscher Verlag der Wissenschaften Berlin 1989; © 1989 by Aulis Verlag Deubner & Co. KG Köln

7. Links zum Thema

	http://www.panix.com/~derwisch/hannes/elug/lisp/scheme.pdf
	http://www-is.informatik.uni-oldenburg.de/~dibo/teaching/java9900/vorlesungen/vorlesung7/tsld031.htm
	http://www.lexikon-definition.de/LISP.html

8. Verwandte Themen

	Das Vorangestellte hilft wirtschaften, löst jedoch kein einziges Problem (allerdings ohne Beachtung der Worst-Case-Strategien wird man auch nicht erfolgreich Software entwickeln und/oder informatische Projekte realisieren können). Deshalb nunmehr das, was wirklich Arbeiten hilft.
	das 8-Dame-Problem des Cliquen-Problem Domino-Problem das Entscheidbarkeitsproblem das Erfüllbarkeitsproblem das Flaggenproblem das Halteproblem das Hamilton-Problem das K-Farben-Problem der Kaprekar-Algorithmus die Magischen Quadrate das PASCAL'sche Dreiecksproblem das Philosophenproblem das Königsberger-Brückenproblem das Post'schen Korrespondenzproblem das Rucksackproblem das Rundreiseproblem das Springer-Problem die Türme von Hanoi das Wortproblem das Wüstenfit-Problem
	Worst-Case-Denken Algorithmentheorie Komplexität, Mächtigkeit und Aufwand Praktische Elementaralgorithmen Lösbarkeit und Problemlösungsstrategien Klassische algorithmisch lösbare Probleme Zufall und Computer Graphentheorie Petri-Netze
	Informationsbegriff Logo für die Signale Nachrichten Wissen Systembegriff Modellbegriff Simulation Denken und Sprache Zahlen, Daten und Datentypen Gegenläufigkeit und Verklemmung Pattern-Matching

zur Hauptseite

© Samuel-von-Pufendorf-Gymnasium Flöha

© Frank Rost im März 1995