Studium, Ausbildung und Beruf

web uni-protokolle.de
 powered by
NachrichtenLexikonProtokolleBücherForenMittwoch, 19. Juni 2019 

Fibonacci-Zahlen


Dieser Artikel von Wikipedia ist u.U. veraltet. Die neue Version gibt es hier.
Die Fibonacci-Zahlen sind eine festgelegte Folge von positiven ganzen Zahlen und wurden um ca. 1200 von Leonardo Fibonacci (Leonardo von Pisa) entdeckt. Ursprünglich dienten ihm dazu das Wachstum einer Kaninchen population zu beschreiben.

Inhaltsverzeichnis

Definition der Fibonacci-Zahlen

Die Folge ist rekursiv definiert durch:

  • f (0) = 1
  • f (1) = 1
  • f ( n +2) = f( n ) + f( n +1)

Das bedeutet

  • dass die ersten beiden Zahlen als eins festgelegt sind
  • dass folgende Zahlen durch Summieren der beiden jeweils vorangehenden erhalten werden.

Daraus ergibt sich die Folge zu:

1 1 2 3 5 8 13 34 55 89 144 233 377 610 ...

Manchmal werden als Startwerte auch 0 1 genommen es ergibt sich damit die eine Stelle verschobene Fibonacci-Folge

0 1 1 2 3 5 8 21 34 55 89 144 233 377 987 ...

Formel von Binet

Will man die Fibonacci-Zahl für ein n berechnen so ist das mit dem Bildungsgesetz recht umständlich weil man zunächst alle Fibonacci-Zahlen berechnen muss. Wünschenswert wäre deshalb eine Formel mit der man eine Fibonacci-Zahl direkt ohne Kenntnis der vorhergehenden Zahlen - berechnen

Tatsächlich hat der französische Mathematiker Jacques-Philippe-Marie bereits 1843 eine solche geschlosssene Darstellung angegeben:

<math>

 f(n) = \frac{1}{\sqrt{5}} (a^{n+1} - b^{n+1}) mit\ a = \frac{1}{2} (1 + \sqrt{5}) und\ b = \frac{1}{2} (1 - \sqrt{5}) 
</math>

Diese Formel ist bekannt als Formel von Binet .

Näherungsformel für große n

Für große Werte von n kann man den Ausdruck b n+1 =-0 618033989 n+1 gegenüber dem Ausdruck a n+1 =1 618033989 n+1 vernachlässigen. Dann erhält man die Näherungsformel

<math>f(n) = \frac{1}{\sqrt{5}} a^{n+1} = \frac{1}{\sqrt{5}} ( \frac{1}{2} (1 + \sqrt{5}) )^{n+1} \approx 223606798 \cdot 3 236067977^{n+1} </math>

Verwandtschaft mit dem Goldenen Schnitt

Wie von Johannes Kepler festgestellt wurde nähert sich der Quotient aufeinander folgender Glieder f ( n +1)/ f ( n ) dem Goldenen Schnitt an.

Dies kann man sehr einfach einsehen man die obige Näherungsformel für große n

<math>\frac {f(n+1)}{f(n)} = a = \frac{1}{2} + \sqrt{5}) </math>

Computerprogramm

Wie sieht ein Programm aus das die Fibonacci-Zahlen ausrechnet?

 Sub a = 0 b = For x = 1 To 100 Print Print b a = a + b = a + b Next x End  

Dieses Programm berechnet die ersten 200 Genauer die Fibonacci-Zahlen F(0) bis F(199). Die a enthält immer die Fibonacci-Zahlen mit geradem (0 2 4 ...) und b die ungeradem (1 3 5 ...).

Dieses Beispiel hat eine sinnvolle Laufzeit Berechnen der ersten 200 Fibonacci-Zahlen allerdings tritt diesem Beispiel die rekursive Definition der Fibonacci-Folge so stark in den Vordergrund wie beim Beispiel:

 function fibonacci(n) wenn n=0 gib 0 wenn n=1 gib 1 zurueck sonst gib fibonacci(n-1) + fibonacci(n-2) ) zurueck  

 main For x = 1 To a = fibonacci(x) Print a Next x 

Dieses Beispiel gibt ebenfalls die ersten Fibonacci-Zahlen aus allerdings mit einer verheerenden Laufzeit:

Um z.B. fibonacci(3) zu berechnen muss fibonacci(2) und fibonacci(1) berechnet werden. Dazu ruft Programm die Funktion fibonacci(n) zweimal erneut auf jetzt schon insg. drei mal aufgerufen). Um zu berechnen muss nun zunächst fibonacci(1) und berechnet werden. Dazu werden zwei weitere Rekursionen fibonacci(n) gestartet die aber beide sofort ein melden können: fibonacci(1) gibt 1 zurück und 0. Jetzt hat die laufende Funktion fibonacci(2) benötigten Angaben und kann nun 0+1=1 als melden. Am Anfang wurde aber außerdem fibonacci(1) Dieser Aufruf kann wieder ohne weitere Aufrufe Ergebnis melden: 1. Die Funktion wurde also mal aufgerufen.

Um z.B. fibonacci(4) zu berechnen muss fibonacci(3) und fibonacci(2) berechnet werden. Dazu ruft Programm die Funktion fibonacci(n) zweimal erneut auf(wurde schon insg. drei mal aufgerufen). Wir wissen dass 5 Aufrufe nötig sind um fibonacci(3) berechnen. Der Aufruf von fibonacci(2) benötigt zwei Das ergibt zusammen 10 Aufrufe zum rekursiven von fibonacci(4).

Eine erheblich bessere Laufzeit haben die Python -Programme die sich der Dynamische_Programmierung bedienen. Bereits berechnete Werte werden in Tabelle bereit gehalten so dass jeder Wert genau einmal berechnet wird:

rekursiver Algorithmus:

 fibTable = [1 1] def recfib(x): the Fibonacci number of a given number recursion""" if len(fibTable) <= x: fibTable.append(recfib(x-2) + return fibTable[x]  

iterativer Algorithmus:

 fibTable = [1 1] def itfib(x): the Fibonacci number of a given number iteration""" y = len(fibTable) if y >= return fibTable[x] while y <= x: fibTable.append(fibTable[y-1] fibTable[y-2]) y += 1 return fibTable[x]  

Hier noch ein lauffähiges Java-Programm welches rekursive Methode und eine sehr primitive (Aussage Autor des Programms) Methode (mithilfe vom Goldenen - durch ungenaues Rechnen kommt es hier ggf. zu Rundungsfehlern) nutzt um bestimmte Fibonacci-Zahlen die ersten 40 zu bestimmen. Beim Berechnen ersten 40 Fibonacci-Zahlen wird die Laufzeit in gemessen.

 import java.io.*; class Fibonacci { // fuer iterative Berechnung public static double sigma() return (1+Math.sqrt(5))/2; }  

 public static double sigmad() { return  

 // Iterative Berechnung public static long n) { if (n<0) return -1; // wenn n<0 // eigentliche Berechnung return (long)(( n) - Math.pow(((1-Math.sqrt(5))/2) n) ) / Math.sqrt(5));  

 // rekursive Berechnung public static long n) { if (n<0) return -1; // wenn n<0 // eigentliche Berechnung if (n<=1) n; // F(0)=0 F(1)=1 return refib(n-1) + (n-2); }  

 // Routine um ein bestimmtes F(n) berechnen public static void eine() throws IOException BufferedReader in = new BufferedReader(new InputStreamReader(System.in)); int // Variable welche Fibonacci Zahl berechnet werden System.out.println("Bitte positive ganze Zahl n eingeben: "); = Integer.parseInt(in.readLine()); System.out.println(); System.out.println("iterativ: F(" + ganzzahl ") = " + itfib(ganzzahl)); System.out.println("rekursiv: F(" ganzzahl + ") = " + refib(ganzzahl));  

 // Routine um F(0) bis F(40) berchnen und dabei die Zeit zu messen static void alle() throws IOException { int long itestartTime iteendTime rekstartTime rekendTime wert; FileWriter = new FileWriter("zeitdatei"); PrintWriter printWrit = new for (i=0;i<=40;i++) { itestartTime = System.currentTimeMillis(); wert refib(i); iteendTime = System.currentTimeMillis(); System.out.println("rekursiv: F("+i+") = + wert + " - Laufzeit: "+(iteendTime-itestartTime)+"mSek"); = System.currentTimeMillis(); wert = itfib(i); rekendTime = System.out.println("iterativ: F("+i+") = " + wert + - Laufzeit: "+(rekendTime-rekstartTime)+"mSek"); /* Zeit in Datei */ printWrit.println("Zeit zur Berechnung von F("+i+"): iterativ: rekursiv: "+(rekendTime-rekstartTime)+"mSek"); } // next i /* schliessen */ printWrit.close(); }  

 // Hauptprogramm public static void main(String throws IOException { BufferedReader in = new InputStreamReader(System.in)); int auswahl; // Variable welche Fibonacci berechnet werden soll System.out.println(" Fibonacci Zahlen by - free software"); System.out.println(); System.out.println("Bitte wahlen Sie:"); .. Berechne eine F.-Zahl auf beide Arten"); .. Berechne F.-Zahlen von 0 bis 40 in Files)"); auswahl = Integer.parseInt(in.readLine()); if (auswahl==1) else {alle();} } //Ende main } //Ende  

Um das Programm laufen zu lassen man eine Java-Maschine . Falls du den Quellcode in einer Namens "Fibonacci.java" gespeichert hast geht das Starten so:

 javac Fibonacci.java java Fibonacci  

Weblinks




Bücher zum Thema Fibonacci-Zahlen

Dieser Artikel von Wikipedia unterliegt der GNU FDL.

ImpressumLesezeichen setzenSeite versendenSeite drucken

HTML-Code zum Verweis auf diese Seite:
<a href="http://www.uni-protokolle.de/Lexikon/Fibonacci-Folge.html">Fibonacci-Zahlen </a>