Gefüllte Zellen
Additionen
Aufrufe ohne Tabelle

  • Wird gefüllt
  • Wird gelesen
  • Ergebnis

Mehr über Fibonacci mit dynamischer Programmierung

Fibonacci mit dynamischer Programmierung

Die Fibonacci-Zahlen sind das klassische erste Beispiel für dynamische Programmierung. Einfache Rekursion fragt immer wieder nach denselben Gliedern, aber mit einer Tabelle, die sich jedes Glied merkt, wächst der Aufwand nur mit n. Wählen Sie ein Glied, entscheiden Sie sich für Bottom-up oder Top-down und gehen Sie Schritt für Schritt durch, um zu sehen, wie jede Zelle genau einmal gefüllt wird. Drücken Sie Abspielen, um zuzusehen, wie sich die Tabelle füllt, oder Schritt und Zurück, um Schritt für Schritt vorzugehen. Ziehen Sie den Schrittregler, um an eine beliebige Stelle zu springen. Wählen Sie n, das zu berechnende Glied, und die Methode: Bottom-up füllt die Tabelle von links, Top-down behält die Rekursion bei, schaut aber zuerst in der Tabelle nach, und die Reihe unter der Tabelle ist dann der Stapel der offenen Aufrufe. Neues Beispiel wählt ein anderes n. Wenn das Feld ausgewählt ist, gehen die Pfeiltasten schrittweise vor, die Leertaste startet und pausiert, und Pos1 und Ende springen zum Anfang und zum Ende.

Wie es funktioniert

  1. Geben Sie n ein, das zu berechnende Glied, und wählen Sie Bottom-up oder Top-down.
  2. Drücken Sie Abspielen, oder gehen Sie mit Schritt und Zurück Schritt für Schritt vor. Ziehen Sie den Schrittregler, um an eine beliebige Stelle zu springen.
  3. Beobachten Sie, wie jede Zelle die beiden Zellen davor liest. Bei Top-down ist die Reihe unter der Tabelle der Stapel der offenen Aufrufe.

Bottom-up und Top-down

Bottom-up, auch Tabulation genannt, beginnt mit F(0) = 0 und F(1) = 1 und füllt die Tabelle von links nach rechts: Jede neue Zelle ist die Summe der beiden Zellen davor. Top-down, auch Memoisation genannt, behält die rekursive Definition bei: Um F(n) zu finden, fragt man nach F(n − 1) und F(n − 2). Der Unterschied zur einfachen Rekursion: Jeder Aufruf schaut zuerst in der Tabelle nach und berechnet ein Glied nur, wenn seine Zelle noch leer ist. Beide füllen jede Zelle einmal und brauchen n − 1 Additionen.

Warum einfache Rekursion so langsam ist

Ohne Tabelle ruft F(n) die Glieder F(n − 1) und F(n − 2) auf, beide rufen F(n − 3) auf und so weiter: Die Aufrufe bilden einen Baum, in dem dieselben Glieder immer wieder vorkommen. Die Zahl der Aufrufe ist 2·F(n + 1) − 1 und wächst so schnell wie die Fibonacci-Zahlen selbst: 177 Aufrufe für F(10), 21.891 für F(20) und mehr als 331 Millionen für F(40). Genau für solche überlappenden Teilprobleme ist dynamische Programmierung da.

Häufig gestellte Fragen

Was ist dynamische Programmierung?

Ein Verfahren, bei dem man ein Problem in kleinere, sich überlappende Teilprobleme zerlegt, jedes davon nur einmal löst und das Ergebnis in einer Tabelle speichert. Die Fibonacci-Zahlen sind das einfachste Beispiel: Jedes Glied entsteht aus den beiden davor.

Was ist der Unterschied zwischen Memoisation und Tabulation?

Memoisation behält den rekursiven Code bei und speichert jedes Ergebnis, sobald es zum ersten Mal berechnet ist, sodass spätere Aufrufe es nur noch lesen. Tabulation füllt die Tabelle in einer Reihenfolge, die sicherstellt, dass jedes Ergebnis, das eine Zelle braucht, schon da ist. Beide führen dieselben Additionen aus; Tabulation kommt ohne Aufrufstapel aus, und Memoisation berechnet nur die Zellen, die wirklich gebraucht werden.

Wie viele Additionen braucht F(n)?

Mit Tabelle n − 1: eine für jedes Glied von F(2) bis F(n). Es werden immer nur die letzten beiden Glieder gelesen, deshalb kann ein Programm auch nur zwei Zahlen statt der ganzen Tabelle speichern.

Warum endet die App bei n = 40?

F(40) = 102.334.155 passt noch gut auf den Bildschirm, und einfache Rekursion bräuchte dafür schon 331.160.281 Aufrufe. Größere Glieder wachsen schnell: F(78) ist das größte, das eine JavaScript-Zahl exakt darstellen kann.

Wird irgendetwas übertragen?

Nein. Alles wird in Ihrem Browser berechnet, und Ihre letzten Einstellungen bleiben im lokalen Speicher dieses Browsers.

Bereit, es auszuprobieren?

Öffnen Sie PictorX in Ihrem Browser – keine Installation, zum Starten ist keine Kreditkarte erforderlich.

Zum Editor