- Fylls
- Läses
- Svar
Fibonacci med dynamisk programmering
Fibonaccitalen är det klassiska första exemplet på dynamisk programmering. Vanlig rekursion frågar efter samma termer om och om igen, men med en tabell som kommer ihåg varje term växer arbetet bara med n. Välj en term, välj bottom-up eller top-down och stega igenom för att se varje cell fyllas en gång. Tryck på Spela för att se tabellen fyllas, eller använd Steg och Bakåt för att gå ett steg i taget. Dra i stegreglaget för att hoppa var som helst. Välj n, den term som ska räknas ut, och metoden: Bottom-up fyller tabellen från vänster, Top-down behåller rekursionen men tittar först i tabellen, och raden under tabellen är då stacken av öppna anrop. Nytt exempel väljer ett annat n. När brädet är markerat stegar piltangenterna, mellanslag spelar och pausar, och Home och End hoppar till början och slutet.
Hur det fungerar
- Skriv n, den term som ska räknas ut, och välj Bottom-up eller Top-down.
- Tryck på Spela, eller använd Steg och Bakåt för att gå ett steg i taget. Dra i stegreglaget för att hoppa var som helst.
- Se hur varje cell läser de två cellerna före den. Med Top-down är raden under tabellen stacken av öppna anrop.
Bottom-up och top-down
Bottom-up, även kallat tabulering, börjar med F(0) = 0 och F(1) = 1 och fyller tabellen från vänster till höger: varje ny cell är summan av de två cellerna före den. Top-down, även kallat memoisering, behåller den rekursiva definitionen: för att hitta F(n) frågar man efter F(n − 1) och F(n − 2). Skillnaden mot vanlig rekursion är att varje anrop först tittar i tabellen och bara räknar ut en term om dess cell fortfarande är tom. Båda fyller varje cell en gång och använder n − 1 additioner.
Varför vanlig rekursion är så långsam
Utan tabell anropar F(n) F(n − 1) och F(n − 2), båda anropar F(n − 3) och så vidare: anropen bildar ett träd där samma termer dyker upp om och om igen. Antalet anrop är 2·F(n + 1) − 1, som växer lika snabbt som Fibonaccitalen själva: 177 anrop för F(10), 21 891 för F(20) och mer än 331 miljoner för F(40). Överlappande delproblem som dessa är precis vad dynamisk programmering är till för.
Ofta ställda frågor
Vad är dynamisk programmering?
Ett sätt att lösa ett problem genom att dela upp det i mindre problem som överlappar, lösa varje mindre problem en gång och spara svaret i en tabell. Fibonaccitalen är det enklaste exemplet: varje term byggs av de två före den.
Vad är skillnaden mellan memoisering och tabulering?
Memoisering behåller den rekursiva koden och sparar varje svar första gången det räknas ut, så att senare anrop bara läser det. Tabulering fyller tabellen i en ordning som ser till att varje svar som en cell behöver redan finns där. Båda gör samma additioner; tabulering slipper anropsstacken, och memoisering räknar bara ut de celler som verkligen behövs.
Hur många additioner behöver F(n)?
n − 1 med en tabell: en för varje term från F(2) till F(n). Bara de två sista termerna läses någonsin, så ett program kan också nöja sig med att spara två tal i stället för hela tabellen.
Varför slutar appen vid n = 40?
F(40) = 102 334 155 får fortfarande gott plats på skärmen, och vanlig rekursion skulle redan behöva 331 160 281 anrop för det. Större termer växer snabbt: F(78) är den största som ett JavaScript-tal kan hålla exakt.
Skickas något någonstans?
Nej. Allt räknas ut i din webbläsare, och dina senaste inställningar sparas i den här webbläsarens lokala lagring.
Redo att prova det?
Öppna PictorX i din webbläsare - ingen installation, inget kreditkort krävs för att starta.
Gå till Editor