Kurs:Algorithmen und Datenstrukturen/Vorlesung/Fibonacci-Zahlen

Startseite

Vorlesung

1.Einleitung

2. Theoretische Grundlagen

2.1 Programmierparadigmen

2.2. Laufzeitanalysen

2.3. Entwurfsmuster

3. Suchen

3.1 Suchen in sortierten Folgen

3.2 Suchen in Texten

4. Sortieren

4.1 Algorithmen für vergleichsbasiertes Sortieren

4.2 Weitere Sortierprobleme

5. Dynamische Datenstrukturen

5.1 Binäre Suchbäume

5.2 AVL Bäume

5.3 2-3-4-Bäume und Rot-Schwarz Bäume

5.4 Heaps

5.5 Hashtabellen

6. Graphen

6.1 Einführung

6.2 Breitensuche

6.3 Tiefensuche

6.4 Topologisches Sortieren

6.5 Berechnung kürzester Wege

6.6 Berechnung maximaler Flüsse

6.7 Spannbäume

7. Optimierung

7.1 Grundlagen

7.2 Kombinatorische Optimierung

7.4 Lineare Optimierung

7.5 Simplex Verfahren

Fibonacci Zahlen - funktional

In folgendem Beispiel werden wir die Fibonacci-Zahlen mit Hilfe eines funktionalen Algorithmus berechnen.

Hintergrundwissen

Bei den Fibonacci Zahlen handelt es sich um eine unendliche Zahlenreihe. Ursprünglich wurde die Fibonacci-Folge zur Beschreibung des Wachstums einer Kaninchenpopulation verwendet. Diese erfolgt progressiv. Am Anfang gibt es ein Kaninchenpaar, dieses wird im zweiten Monat zeugungsfähig und zeugt jeden Monat ein weiteres Paar Kaninchen. Keins der Kaninchen stirbt. Das heißt, die Summe der benachbarten Zahlen ergibt die nächste Zahl ( 0,1,1,2,3,5,8,...).

$f_{0}=0$

$f_{1}=1$

$f_{2}=1=f_{0}+f_{1}$

$f_{3}=2=f_{1}+f_{2}$

$f_{4}=3=f_{2}+f_{3}$

...

$fib(x):=\left\{{\begin{array}{ll}x-te~Fibonacci-Zahl&fals~x\geq 0\\\bot &sonst\end{array}}\right.$

Programm

fib(x)  :=  if (x==0) then 0 
        else if (x==1)  then  1
                else  fib(x-1) + fib(x-2)

Literatur

Da die Vorlesungsinhalte auf dem Algorithmen und Datenstrukturen: Eine Einführung mit Java von Gunter Saake und Kai-Uwe Sattler aufbauen, empfiehlt sich dieses Buch um das hier vorgestellte Wissen zu vertiefen. Die auf dieser Seite behandelten Inhalte sind in Kapitel 3.2.6 zu finden.