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

Bearbeiten

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

Die Fibonacci-Folge   ist durch das rekursive Bildungsgesetz

    für  

mit den Anfangswerten

    und    

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   ausgelassen und die Fibonacci-Folge mit   und   beginnend definiert, insbesondere bei der Anwendung auf Situationen, in denen ein Anfangswert Null keinen Sinn hat.[1]

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

Bearbeiten

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

Bearbeiten
  • Schwierigkeitsgrad: leicht
  • Sprache: jede

In dieser Aufgabe geht es darum, sich eine Funktion zu schreiben, die die Fibonacci-Zahl fn 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

Bearbeiten
  • 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 f0 bis fn 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

Bearbeiten
  • 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

Bearbeiten

Einzelnachweise

Bearbeiten
  1. Aus Wikipedia: Fibonacci-Folge, bearbeitet