Mathematik: Unterschied zwischen den Versionen
(Rekursive Funktion Fibonacci-Zahlen) |
Keine Bearbeitungszusammenfassung |
||
| Zeile 13: | Zeile 13: | ||
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: | 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> | <math>f(n)=f\left( a_{n-1}\right) +f\left( a_{n-2}\right) </math> | ||
Version vom 2. Februar 2007, 07:18 Uhr
Themen
Erzeugende Funktionen
Wir möchten uns für den Anfang mit Erzeugenden Funktionen beschäftigen. Mit Hilfe erzeugender Funktionen kann jede lineare Rekursion explizit angeschrieben werden (und noch vieles mehr). Das heißt, man braucht sich für die, sagen wir, 42. Zahl nicht alle Zahlen davor ausrechnen, sondern kann in eine geschlossene Formel "42" einsetzen und erhält direkt das Ergebnis.
Außerdem sind Erzeugende Funktionen auf den ersten, zweiten und fünften Blick magisch ;)
Wir setzen uns zusammen und reden über Erzeugende Funktionen. Es brauchen keine Vorkenntnisse vorhanden zu sein, insbesondere kein Maturawissen in Mathematik. Alle Grundlagen werden erklärt.
Als Beispiel die Erzeugende Funktion der Fibonacci-Zahlen:
Die Fibonacci-Zahlen beginnen mit Fehler beim Parsen (SVG (MathML kann über ein Browser-Plugin aktiviert werden): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://en.wikipedia.org/api/rest_v1/“:): {\displaystyle 1} als nullter Zahl und als erster Zahl. Dann werden immer die beiden vorhergehenden Zahlen addiert: Die zweite Fibonacci-Zahl ist Fehler beim Parsen (SVG (MathML kann über ein Browser-Plugin aktiviert werden): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://en.wikipedia.org/api/rest_v1/“:): {\displaystyle 2} , die dritte Fehler beim Parsen (SVG (MathML kann über ein Browser-Plugin aktiviert werden): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://en.wikipedia.org/api/rest_v1/“:): {\displaystyle 3} , die vierte Fehler beim Parsen (SVG (MathML kann über ein Browser-Plugin aktiviert werden): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://en.wikipedia.org/api/rest_v1/“:): {\displaystyle 5} usw. Für jede natürliche Zahl Fehler beim Parsen (SVG (MathML kann über ein Browser-Plugin aktiviert werden): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://en.wikipedia.org/api/rest_v1/“:): {\displaystyle n} (natürliche Zahlen: Fehler beim Parsen (SVG (MathML kann über ein Browser-Plugin aktiviert werden): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://en.wikipedia.org/api/rest_v1/“:): {\displaystyle 0, 1, 2, 3, 4, ...} ) gibt es eine, die man Fehler beim Parsen (SVG (MathML kann über ein Browser-Plugin aktiviert werden): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://en.wikipedia.org/api/rest_v1/“:): {\displaystyle a_n} nennen kann. Die rekursive Funktion sieht so aus:
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 Fehler beim Parsen (SVG (MathML kann über ein Browser-Plugin aktiviert werden): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://en.wikipedia.org/api/rest_v1/“:): {\displaystyle n}
-te Fibonacci-Zahl sieht so aus:
Fehler beim Parsen (SVG (MathML kann über ein Browser-Plugin aktiviert werden): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://en.wikipedia.org/api/rest_v1/“:): {\displaystyle 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)}
Und die 42. Fibonacci-Zahl:
Ansprechpartner fuer das Thema: Isis
Tower of Hanoi
Den Erzeugenden Funktionen nich unaehnlich weil, es auch hier darum geht Funktionen mit rekursiven Charakter in solche ohne umzuwandeln (wobei hier die zugrundeliegenden rekursiven Funktionen keine Folgen im aengeren Sinne darstellen), sind die meisten Fragestellungen aus dem Umfeld des Tower of Hanoi Problems. Clifford beschaeftigt sich schon laenger mit diversen Fragen aus dem Tower of Hanoi-Umfeld und hat unter anderem diese Formel fuer den Zustand eines Tower of Hanoi Systems zu einer gegebenen Zugnummer erarbeitet:
Fehler beim Parsen (SVG (MathML kann über ein Browser-Plugin aktiviert werden): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://en.wikipedia.org/api/rest_v1/“:): {\displaystyle s = \left( \left( \left( \left( n + d + 1 \right) \bmod 2 \right) + 1 \right) \cdot \lfloor \frac{ m + 2^{d-1} }{ 2^d } \rfloor \right) \bmod 3}
http://www.clifford.at/hanoi/
Wir koennten uns unter anderem mit folgenden Fragestellungen beschaeftigen:
- Vom Zustand des Hanoi-Systems zur Zugnummer (ohne Numerik natuerlich!)
- Effektive Algorithmen fuer mehr als drei Tuerme
- Von der Zugnummer zum Zustand und umgekehrt fuer belibige Start- und Ziel-Zustaende
- Tower of Hanoi System als Graycode-Darstellungsvariante eines Trinaersystems?
- Weitere Vorschlaege bitte hier einzusetzen
Ansprechpartner fuer das Thema: Clifford
andere Themen
- Unterhaltungsmathematik
- Berühmte ungelöste Problemstellungen verstehen ;)
Organisation
Interessenten
Wann?
Erstes Treffen am 16.2.2007 um 18:00 Uhr im Hauptraum. Es geht um erzeugende Funktionen. Hauptsächlich werden die Grundlagen behandelt, da man ja vorher nix wissen muss :) Wir schauen dann wie weit wir kommen. Die genauen Themen sowie Unterlagen zum Download folgen noch.
