Gevulde cellen
Optellingen
Aanroepen zonder tabel

  • Wordt gevuld
  • Wordt gelezen
  • Antwoord

Meer over Fibonacci met dynamisch programmeren

Fibonacci met dynamisch programmeren

De Fibonacci-getallen zijn het klassieke eerste voorbeeld van dynamisch programmeren. Gewone recursie vraagt steeds weer naar dezelfde termen, maar met een tabel die elke term onthoudt, groeit het werk alleen met n. Kies een term, kies bottom-up of top-down en ga stap voor stap om te zien hoe elke cel één keer wordt gevuld. Druk op Afspelen om de tabel te zien vullen, of gebruik Stap en Terug om stap voor stap te gaan. Sleep de stappenschuif om ergens heen te springen. Kies n, de term die je wilt berekenen, en de methode: Bottom-up vult de tabel vanaf links, Top-down houdt de recursie maar kijkt eerst in de tabel, en de rij onder de tabel is dan de stapel open aanroepen. Nieuw voorbeeld kiest een andere n. Als het bord geselecteerd is, gaan de pijltjestoetsen een stap verder of terug, start en pauzeert de spatiebalk, en springen Home en End naar het begin en het einde.

Hoe het werkt

  1. Typ n, de term die je wilt berekenen, en kies Bottom-up of Top-down.
  2. Druk op Afspelen, of gebruik Stap en Terug om stap voor stap te gaan. Sleep de stappenschuif om ergens heen te springen.
  3. Kijk hoe elke cel de twee cellen ervoor leest. Bij Top-down is de rij onder de tabel de stapel open aanroepen.

Bottom-up en top-down

Bottom-up, ook tabulatie genoemd, begint met F(0) = 0 en F(1) = 1 en vult de tabel van links naar rechts: elke nieuwe cel is de som van de twee cellen ervoor. Top-down, ook memoïsatie genoemd, houdt de recursieve definitie: om F(n) te vinden, vraag je F(n − 1) en F(n − 2) op. Het verschil met gewone recursie is dat elke aanroep eerst in de tabel kijkt en een term alleen berekent als de cel nog leeg is. Beide vullen elke cel één keer en gebruiken n − 1 optellingen.

Waarom gewone recursie zo traag is

Zonder tabel roept F(n) F(n − 1) en F(n − 2) aan, die allebei F(n − 3) aanroepen, enzovoort: de aanroepen vormen een boom waarin dezelfde termen steeds weer voorkomen. Het aantal aanroepen is 2·F(n + 1) − 1, en dat groeit even snel als de Fibonacci-getallen zelf: 177 aanroepen voor F(10), 21.891 voor F(20) en meer dan 331 miljoen voor F(40). Overlappende deelproblemen als deze zijn precies waar dynamisch programmeren voor bedoeld is.

Veelgestelde vragen

Wat is dynamisch programmeren?

Een manier om een probleem op te lossen door het op te splitsen in kleinere problemen die overlappen, elk kleiner probleem één keer op te lossen en het antwoord in een tabel te bewaren. De Fibonacci-getallen zijn het eenvoudigste voorbeeld: elke term wordt opgebouwd uit de twee ervoor.

Wat is het verschil tussen memoïsatie en tabulatie?

Memoïsatie houdt de recursieve code en slaat elk antwoord op de eerste keer dat het berekend is, zodat latere aanroepen het alleen nog lezen. Tabulatie vult de tabel in een volgorde die ervoor zorgt dat elk antwoord dat een cel nodig heeft er al is. Beide doen dezelfde optellingen; tabulatie heeft geen aanroepstapel nodig, en memoïsatie berekent alleen de cellen die echt nodig zijn.

Hoeveel optellingen heeft F(n) nodig?

n − 1 met een tabel: één voor elke term van F(2) tot en met F(n). Alleen de laatste twee termen worden ooit gelezen, dus een programma kan ook gewoon twee getallen bewaren in plaats van de hele tabel.

Waarom stopt de app bij n = 40?

F(40) = 102.334.155 past nog makkelijk op het scherm, en gewone recursie zou er al 331.160.281 aanroepen voor nodig hebben. Grotere termen groeien snel: F(78) is de grootste die een JavaScript-getal exact kan bevatten.

Wordt er iets verstuurd?

Nee. Alles wordt in je browser berekend, en je laatste instellingen blijven in de lokale opslag van deze browser.

Klaar om het te proberen?

Open PictorX in je browser - geen installatie, geen creditcard nodig om te starten.

Ga naar Editor