Fibonacci
Fibonacci,
mit wirklichem Namen Leonardo
Pisano, war ein italienischer Mathematiker der Mittelalters (1170 –
1250). In seinem berühmten Buch "liber abaci" beschreibt er
ein Problem:
Ein Mann setzt
ein Kaninchenpaar in ein Gehege. Diese Kaninchen bekommen jeden Monat ein
weiteres Paar. Ein frischgeborenes Paar wird im 2. Monat fruchtbar. Wieviele
Kaninchenpaare gibt es nach einem Jahr in diesem Gehege?
Das Originalpaar
bekommt im ersten Monat ein weiteres Paar, also sind es dann zwei. Im nächsten
Monat kommt wieder ein weiteres hinzu, also sind es drei. Im nächsten Monat
kommt ein Kinderpaar des ersten Paares und eines des ersten Kinderpaares hinzu,
also sind es 3+2=5. Die hinzukommenden Paare werden im nächsten Monat nichts
beitragen, aber ab dem übernächsten monatlich ein Paar. Also kommen im nächsten
Monat 3 hinzu, das sind 5+3=8. Im nächsten Monat kommen schon 5 hinzu, das sind
8+5=13, usw.
Fibonacci-Folge:
Ein Folge (ai)
mit der Eigenschaft, dass jedes Glied Summe der beiden vorhergehenden Glieder
ist (an + an+1 = an+2) heißt Fibonacci-Folge.
Legen wir die beiden ersten Glieder fest mit a0 = 0 und
a1 = 1, so bekommen wir folgende Standardfolge:
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, ...
Rabbit-Folge oder die goldene Folge:
Das alte Paar (Typ A) bekommt jeden Monat ein neues Paar (Typ N), das
einen Monat später zu einem alten Paar (Typ A) wird, das zeugungsfähig ist.
Das heißt: haben wir ein Paar vom Typ N (N), so einen Monat später eines vom Typ A (A) und wieder einen Monat später eines vom Typ A und eines vom Typ N (AN). Im nächsten Monat haben wir die Paare ANA, dann ANAAN, dann ANAANANA etc. (Ersetze einfach A durch AN und N durch A). Setzen wir jetzt noch für A eine 1 und für N eine 0, so bekommen wir die Rabbit-Folge:
1 0 1 1 0 1
0 1 1 0 1 1 0 1 0 1 1 0 1 0 1 1 0 1 1 0 1 0 1 1 0 1 .....................
Verweigung:
Wie bei den Kaninchen, kann man auch eine Pflanze betrachten, deren Zweige
jedes Jahr einen neuen Sproß ansetzen, der wieder nach 2 Jahren jährlich
einmal sprosst.
Diese Folge hat die Eigenschaft, dass der Quotient zweier benachbarter Glieder gegen den goldenen Schnitt strebt (lim (an / an-1) = Phi).
Der goldene Schnitt Phi ist ein in der Bautechnik berühmtes Verhältnis
von Strecken (Abständen), wahrscheinlich zuerst so genannt von Leonardo
da Vinci (sectio aurea). Eine Strecke der Länge a ist durch einen Punkt
s im goldenen Schnitt unterteilt, wenn die beiden Teilstrecken im selben Verhältnis
zueinander stehen, wie die gesamte Strecke zu der größen der beiden
Teilstrecken: a : s = s : a-s , was ungefähr ist:
1,61803
39887 49894 84820 45868 34365 63811 77203 09179 80576 .
(Phi und Phi-1 sind die einzigen positiven Zahlen, für die die Gleichung
x2 = x + 1 gilt, d.h. man erhält das Quadrat durch Addition von 1.)
Diese Folge führt auf natürliche Weise zu einer Spirale: man beginnt mit eine Quadrat der Seitenlänge 1. Links daneben setzt man ein ebenso großes Quadrat. Darüber legt man ein Quadrat der Länge 2. Rechts daneben eines der Länge 3, darunter eines der Länge 5, links daneben eines der Länge 8, usw. Legt man jetzt eine Kurve, die die gegenüberliegenden Ecken jedes so erzeugten Quadrates durchläuft, so erhält man eine Spirale, wie sei u.a. bei Muschelgehäusen vorkommt.
Münzen:
Wir haben 1-DM-Münzenund 2-DM-Münzen. Will ich 4 DM bezahlen, kann ich sie auf 5 verschieden Weisen geben (wobei die Reihenfolge, in der ich die Münzen geben, von Bedeutung sein soll): 1+1+1+1 oder 1+1+2 oder 1+2+1 oder 2+1+1 oder 2+2. Bei 5 DM gibt es 8 verschiedene Weisen: 1+1+1+1+1 oder 1+1+1+2 oder 1+1+2+1 oder 1+2+1+1 oder 2+1+1+1 oder 1+2+2 oder 1+2+1 oder 2+2+1. Wieviel Möglichkeiten gibt es bei 10 DM und warum?
Pascalsches Dreieck:
Hier steht das Pascalsche Dreieck (nach links gestaucht): jede Zahl ist die Summe der darüberstehenden und der links davon stehenden (fehlt eine Zahl – drüber oder links davon, so soll man sich eine Null denken) Das ist sehr nützlich, um die Binomialkoeffizienten von (a+b)n zu finden. Betrachte die Summen der nach rechts geneigten Diagonalen. Sie ergeben die Fibonacci-Folge. Warum?
0 | 1
1 | 1 1
2 | 1 2 1
3 | 1 3 3 1
4 | 1 4 6 4 1
5 | 1 5 10 10 5 1
6 | 1 6 15 20 15 6 1
Programmierung
Wir programmieren eine Funktion für die Fibonacci-Folge, einmal iterative und einmal rekursiv:
function
f(n: integer): integer (iterativ)
begin
if = 0;
if n > 0 then begin
a := 0; b := 1;
for
i = 1 to n-1 do begin
b:=
a + b; a:= b - a
end;
result:=
b;
end;
end.
function
f(n: integer) : integer (rekursiv)
begin
if n £=1 then result = n
else
result = f(n-1) + f(n-2)
end.
Wenn n <= 1, so wird n zurückgegeben, der Wert von a0 bzw. a1, also 0 oder 1. Wir können feststellen, dass diese Werte immer und immer wieder berechnet werden, was schon zeigt, dass hier die rekursive Programmierung recht ineffizient ist. So ist z.B.
f(3) =
f(2) + f(1)
= f(1) + f(0) + f(1)
f(4) = f(3) + f(2)
= f(1) + f(0) + f(1) + f(1) + f(0)
Wenn wir f(n) also so herunterbrechen in die Summe von f(0) und f(1), so erhalten wir gerade die goldene Folge der Länge A(n)+1, wobei A(n) die Zahl der nötigen Additionen ist.
Für A(n) lässt sich dabei ganz ähnlich rekursiv definieren wie f(n):
A(0) = 0 ; A(1) = 0 ; A(n) = A(n-1) + A(n-2) + 1 (n>1)
Die ersten 100 Glieder
der Fibonacci-Folge
|
0 : 0 1 : 1 2 : 1 3 : 2 4 : 3 5 : 5 6 : 8 7 : 13 8 : 21 9 : 34 10 : 55 11 : 89 12 : 144 13 : 233 14 : 377 15 : 610 16 : 987 17 : 1597 18 : 2584 19 : 4181 20 : 6765 21 : 10946 22 : 17711 23 : 28657 24 : 46368 25 : 75025 26 : 121393 27 : 196418 28 : 317811 29 : 514229 30 : 832040 31 : 1346269 32 : 2178309 33 : 3524578 |
34 : 5702887 35 : 9227465 36 : 14930352 37 : 24157817 38 : 39088169 39 : 63245986 40 : 102334155 41 : 165580141 42 : 267914296 43 : 433494437 44 : 701408733 45 : 1134903170 46 : 1836311903 47 : 2971215073 48 : 4807526976 49 : 7778742049 50 : 12586269025 51 : 20365011074 52 : 32951280099 53 : 53316291173 54 : 86267571272 55 : 139583862445 56 : 225851433717 57 : 365435296162 58 : 591286729879 59 : 956722026041 60 : 1548008755920 61 : 2504730781961 62 : 4052739537881 63 : 6557470319842 64 : 10610209857723 65 : 17167680177565 66 : 27777890035288 67 : 44945570212853 |
68 : 72723460248141 69 : 117669030460994 70 : 190392490709135 71 : 308061521170129 72 : 498454011879264 73 : 806515533049393 74 : 1304969544928657 75 : 2111485077978050 76 : 3416454622906707 77 : 5527939700884757 78 : 8944394323791464 79 : 14472334024676221 80 : 23416728348467685 81 : 37889062373143906 82 : 61305790721611591 83 : 99194853094755497 84 : 160500643816367088 85 : 259695496911122585 86 : 420196140727489673 87 : 679891637638612258 88 : 1100087778366101931 89 : 1779979416004714189 90 : 2880067194370816120 91 : 4660046610375530309 92 : 7540113804746346429 93 : 12200160415121876738 94 : 19740274219868223167 95 : 31940434634990099905 96 : 51680708854858323072 97 : 83621143489848422977 98 : 135301852344706746049 99 : 218922995834555169026 100: 354224848179261915075 |