Aufgabensammlung Programmierung/ Fibonacci-Zahlen

In dieser Aufgabe soll eine Funktion geschrieben werden, die - verallgemeinert - Fibonaccizahlen berechnet. Es gibt mehrere Funktionen, die man für Fibonacci-Zahlen schreiben kann, mehr dazu in der ausführlichen Aufgabenstellung.

Motivation

Die Fibonacci-Folge ist eine Folge natürlicher Zahlen. Sie ist folgendermaßen definiert:

Die Fibonacci-Folge $f_{0},\,f_{1},\,f_{2}\,\ldots$ ist durch das rekursive Bildungsgesetz

$f_{n}=f_{n-1}+f_{n-2}\$   für $n\geq 2$

mit den Anfangswerten

$f_{0}=0\$   und   $f_{1}=1\$

definiert. Das bedeutet in Worten:

• Für die beiden ersten Zahlen werden die Werte null und eins vorgegeben.
• Jede weitere Zahl ist die Summe ihrer beiden Vorgänger.

Daraus ergibt sich:

f0	f1	f2	f3	f4	f5	f6	f7	f8	f9	f10	f…
0	1	1	2	3	5	8	13	21	34	55	…

Oft wird auch $f_{0}=0$ ausgelassen und die Fibonacci-Folge mit $f_{1}=1$ und $f_{2}=1$ beginnend definiert, insbesondere bei der Anwendung auf Situationen, in denen ein Anfangswert Null keinen Sinn hat.

Die Fibonacci-Zahlen spielen eine wichtige Rolle in verschiedensten Bereichen der Mathematik, der Kunst und einiger anderer Wissenschaften. Aufgrund des einfachen Bildungsgesetzes lassen sie sich leicht berechnen.

Aufgaben

Man kann einiges mit Fibonacci-Zahlen anstellen, daher gibt es hier nicht eine Aufgabestellung, sondern mehrere. Die Aufgabenstellungen haben dabei verschiedene Schwierigkeitsgrade.

Fibonacci-Zahl x berechnen

• Schwierigkeitsgrad: leicht
• Sprache: jede

In dieser Aufgabe geht es darum, sich eine Funktion zu schreiben, die die Fibonacci-Zahl f_n berechnet. Dies kann man entweder über eine Schleife oder Rekursiv tun.

Hinweis: Eine Lösung der form fib(n) = fib(n-1) + fib(n-2) ist extrem ineffizient. Versuche bitte so etwas zu vermeiden.

Liste von Fibonacci-Zahlen berechnen

• Schwierigkeitsgrad: leicht / mittel
• Sprache: jede

Versuche jetzt, eine Funktion zu schreiben, die als Argument eine Zahl n einliest und als Ausgabe eine Liste der Fibonaccizahlen f₀ bis f_n zurückliefert. Versuche dies so zu implementieren, dass möglichst wenige Berechnungen angestellt werden, also versuche die bereits aus den vorherigen Elementen der Liste bekannten Fibonaccis weiter zu verwerten.

Den goldenen Schnitt aus Fibonacci-Zahlen berechnen

• Schwierigkeitsgrad: mittel
• Sprache: jede

Ziel dieser Aufgabe ist es, aus aufeinanderfolgenden Fibonacci-Zahlen den goldenen Schnitt zu errechnen. Dies kann man auf verschiedene Weisen tun, die genaue Art ist dem Programmierer überlassen und kann unterschiedlich kompliziert sein. Hier mögliche Vorschläge:

• Als Eingabe wird ein Index einer Fibonaccizahl entgegengenommen, die Funktion errechnet aus dieser und aus der darauf folgenden Fibonaccizahl den goldenen Schnitt
• Als Eingabe wird eine Gleitkommazahl gegeben, der goldene Schnitt wird solange berechnet, bis die Genauigkeit höher als die angegebene Toleranzgrenze ist (bzw. so genau ist, dass bei gewählter Float oder Double-Genauigkeit keine Differenz mehr feststellbar ist)

Lösungen

• Haskell