Mathematik: Unterschied zwischen den Versionen
Keine Bearbeitungszusammenfassung |
Rekursive Funktion Fibonacci-Zahlen |
||
| Zeile 11: | Zeile 11: | ||
Als Beispiel die Erzeugende Funktion der Fibonacci-Zahlen: | Als Beispiel die Erzeugende Funktion der Fibonacci-Zahlen: | ||
Die Fibonacci-Zahlen beginnen mit <math>1</math> als nullter Zahl und <math>1</math> als erster Zahl. Dann werden immer die beiden vorhergehenden Zahlen addiert: Die zweite Fibonacci-Zahl ist <math>2</math>, die dritte <math>3</math>, die vierte <math>5</math> usw. Für jede natürliche Zahl <math>n</math> (natürliche Zahlen: <math>0, 1, 2, 3, 4, ...</math>) gibt es eine, | Die Fibonacci-Zahlen beginnen mit <math>1</math> als nullter Zahl und <math>1</math> als erster Zahl. Dann werden immer die beiden vorhergehenden Zahlen addiert: Die zweite Fibonacci-Zahl ist <math>2</math>, die dritte <math>3</math>, die vierte <math>5</math> usw. Für jede natürliche Zahl <math>n</math> (natürliche Zahlen: <math>0, 1, 2, 3, 4, ...</math>) gibt es eine, die man <math>a_n</math> nennen kann. Die rekursive Funktion sieht so aus: | ||
<math>f(n)=f(a_{n-1})+f(a_{n-2})</math> | |||
Aber wie kann man eine geschlossene Formel anschreiben, damit man nicht alle Zahlen vor der gesuchten ausrechnen muss? Wie man das macht werden wir lernen, die <math>n</math>-te Fibonacci-Zahl sieht so aus: | |||
<math>f(n)=\frac{1}{\sqrt{5}} \left( \left( \frac{1+\sqrt{5}}{2}\right)^{n+1} - \left( \frac{1-\sqrt{5}}{2}\right)^{n+1}\right)</math> | <math>f(n)=\frac{1}{\sqrt{5}} \left( \left( \frac{1+\sqrt{5}}{2}\right)^{n+1} - \left( \frac{1-\sqrt{5}}{2}\right)^{n+1}\right)</math> | ||