JavaScripts › Mathematik

Fibonacci-Zahlen

Berechnet die ersten Fibonacci-Zahlen — ohne Rekursion, einfach durch fortlaufendes Addieren der beiden Vorgänger.

Dieses Script berechnet die Fibonacci-Zahlen — und zwar ausdrücklich nicht rekursiv, sondern in einer schlichten Schleife. Ihr tragt ein, wie viele Zahlen ausgegeben werden sollen, und bekommt sie als Tabelle mit fortlaufender Nummer angezeigt. Voreingestellt sind zehn Zahlen. Im Original fragte das Script die Anzahl über ein prompt()-Fenster ab und schrieb die Zahlen direkt in die Seite; wir haben daraus ein normales Eingabefeld gemacht.

Die Fibonacci-Folge entsteht nach einer einzigen Regel: Jede Zahl ist die Summe ihrer beiden Vorgänger. Man beginnt mit 1 und 1, daraus wird 2, dann 3, 5, 8, 13, 21 und so weiter. Benannt ist sie nach Leonardo von Pisa, genannt Fibonacci, der sie 1202 in seinem Rechenbuch „Liber Abaci" an einer Aufgabe über die Vermehrung von Kaninchen vorstellte — in Indien war die Folge allerdings schon Jahrhunderte früher bekannt.

Interessant wird die Folge durch das Verhältnis zweier aufeinanderfolgender Zahlen: 8 zu 5 ergibt 1,6, dann 13 zu 8 gleich 1,625, dann 21 zu 13 gleich 1,615… Je weiter ihr geht, desto näher kommt dieses Verhältnis dem Goldenen Schnitt von rund 1,618. In der Natur begegnen einem Fibonacci-Zahlen bei der Anordnung von Blättern um einen Stängel oder bei der Zahl der Spiralen in einem Sonnenblumenkorb.

Zur Zählweise: Das Script beginnt bei „fib(0)" mit der 1 und nicht, wie in der modernen Mathematik üblich, mit der 0. Beides ist gebräuchlich — die Zahlen selbst sind dieselben, nur die Nummerierung ist um eine Stelle verschoben. Beachtet außerdem, dass die Werte schnell riesig werden: Ab etwa der 78. Zahl kann JavaScript sie nicht mehr exakt darstellen, weil dort die Genauigkeitsgrenze für ganze Zahlen erreicht ist. Deshalb ist die Anzahl auf 100 begrenzt.

Eine zweite Umsetzung derselben Folge findet ihr unter Fibonacci-Reihe berechnen. Wer weitere Zahlenmuster mag, wird beim Pascalschen Dreieck und beim Collatz-Problem fündig.

Mathematik Baujahr 2004 läuft in deinem Browser

So funktioniert das Script

Das Script hat drei Teile: Es liest und prüft die gewünschte Anzahl, erzeugt die Zahlen in einer Schleife und baut daraus eine Tabelle. Der spannende Teil ist die Schleife, denn sie zeigt eine Technik, die man immer wieder braucht — mit ein paar wenigen Variablen eine beliebig lange Reihe erzeugen, ohne alle bisherigen Werte aufzuheben.

let var1 = 1;
let var2 = 1;
let var3 = 2;

Diese drei Variablen sind das ganze Gedächtnis des Scripts: var1 und var2 halten die beiden letzten Zahlen, var3 nimmt die neue auf. Die Namen stammen aus dem Original von 2004 — sprechender wären vorletzte, letzte und neue. Die Startwerte 1, 1 und 2 sind die ersten drei Glieder der Folge; sie werden vor der Schleife von Hand gesetzt, weil es für sie noch keine zwei Vorgänger gibt.

for (let i = 3; i <= anzahl - 1; i++) {
  var1 = var2;
  var2 = var3;
  var3 = var2 + var1;
  zeilen.push(zeile(i, var3));
}

In jedem Durchgang rücken die Werte um eine Position weiter: Die vorletzte Zahl bekommt den Wert der letzten, die letzte den der neuen — und erst danach wird die neue Zahl als Summe der beiden gebildet. Auf die Reihenfolge dieser drei Zuweisungen kommt es an; vertauscht man sie, kommt Unsinn heraus. Genau so rechnet man Fibonacci-Zahlen von Hand: Man schaut immer nur auf die letzten beiden Zahlen und addiert sie.

Das ist der iterative Weg, also der über eine Schleife. Der bekanntere rekursive Weg lässt eine Funktion sich selbst zweimal aufrufen — das sieht in der Theorie eleganter aus, wird aber unbrauchbar langsam, weil dieselben Zwischenergebnisse tausendfach neu berechnet werden. Die Schleife hier braucht für die 100. Zahl genau 97 Additionen.

const zeilen = [];
…
zeilen.push(zeile(i, var3));
…
ausgabe.innerHTML = '<table>…' + zeilen.join("") + "</tbody></table>";

Die einzelnen Tabellenzeilen werden in einem Array gesammelt und ganz am Ende mit join("") zu einem einzigen Text zusammengeklebt. Erst dieser fertige Text landet per innerHTML in der Seite. Das ist nicht nur schneller, als in jedem Schleifendurchgang die Anzeige neu aufzubauen, es ist auch die moderne Antwort auf das document.write() des Originals: document.write funktioniert nur, solange die Seite noch geladen wird — nach einem Klick auf einen Knopf würde es die komplette Seite überschreiben.

function zeile(nummer, wert) {
  return "<tr><td>fib(" + nummer + ")</td><td>" +
    wert.toLocaleString("de-DE") + "</td></tr>";
}

Diese kleine Funktion baut eine einzelne Tabellenzeile. toLocaleString("de-DE") setzt die deutschen Tausenderpunkte — aus 832040 wird 832.040, was bei den schnell wachsenden Zahlen die Lesbarkeit deutlich verbessert. Wollt ihr die Zahlen lieber untereinander ohne Tabelle, gebt hier statt <tr>-Zeilen einfach "fib(" + nummer + ") = " + wert + "<br>" zurück.

Anpassen lässt sich außerdem MAX_ANZAHL. Die Grenze von 100 ist bewusst gesetzt: Ab der 78. Zahl überschreiten die Werte den Bereich, in dem JavaScript ganze Zahlen exakt darstellen kann, und die letzten Stellen stimmen dann nicht mehr. Wer wirklich große Fibonacci-Zahlen braucht, müsste auf den Datentyp BigInt ausweichen.

Script für die eigene Homepage

Kopiert euch den kompletten Code und fügt ihn an der Stelle eurer Seite ein, an der das Script erscheinen soll. Er läuft ohne weitere Dateien und ohne fremde Server.

Mehr aus der Kategorie Mathematik