Fyldte celler
Additioner
Kald uden tabel

  • Bliver fyldt
  • Læses
  • Svar

Mere om Fibonacci med dynamisk programmering

Fibonacci med dynamisk programmering

Fibonacci-tallene er det klassiske første eksempel på dynamisk programmering. Almindelig rekursion spørger efter de samme led igen og igen, men med en tabel, der husker hvert led, vokser arbejdet kun med n. Vælg et led, vælg bottom-up eller top-down, og gå trin for trin for at se hver celle blive fyldt én gang. Tryk på Afspil for at se tabellen blive fyldt, eller brug Trin og Tilbage for at gå et trin ad gangen. Træk i trinskyderen for at springe hvorhen som helst. Vælg n, det led der skal beregnes, og metoden: Bottom-up fylder tabellen fra venstre, Top-down beholder rekursionen, men kigger først i tabellen, og rækken under tabellen er så stakken af åbne kald. Nyt eksempel vælger et andet n. Når brættet er valgt, går piletasterne et trin, mellemrumstasten afspiller og sætter på pause, og Home og End springer til starten og slutningen.

Sådan virker det

  1. Skriv n, det led der skal beregnes, og vælg Bottom-up eller Top-down.
  2. Tryk på Afspil, eller brug Trin og Tilbage for at gå et trin ad gangen. Træk i trinskyderen for at springe hvorhen som helst.
  3. Se hver celle læse de to celler før den. Ved Top-down er rækken under tabellen stakken af åbne kald.

Bottom-up og top-down

Bottom-up, også kaldet tabulering, starter med F(0) = 0 og F(1) = 1 og fylder tabellen fra venstre mod højre: hver ny celle er summen af de to celler før den. Top-down, også kaldet memoisering, beholder den rekursive definition: for at finde F(n) spørger man efter F(n − 1) og F(n − 2). Forskellen fra almindelig rekursion er, at hvert kald først kigger i tabellen og kun beregner et led, hvis dets celle stadig er tom. Begge fylder hver celle én gang og bruger n − 1 additioner.

Hvorfor almindelig rekursion er så langsom

Uden en tabel kalder F(n) F(n − 1) og F(n − 2), begge kalder F(n − 3) og så videre: kaldene danner et træ, hvor de samme led dukker op igen og igen. Antallet af kald er 2·F(n + 1) − 1, som vokser lige så hurtigt som Fibonacci-tallene selv: 177 kald for F(10), 21.891 for F(20) og mere end 331 millioner for F(40). Overlappende delproblemer som disse er præcis det, dynamisk programmering er til for.

Ofte stillede spørgsmål

Hvad er dynamisk programmering?

En måde at løse et problem på ved at dele det op i mindre problemer, der overlapper, løse hvert mindre problem én gang og gemme svaret i en tabel. Fibonacci-tallene er det enkleste eksempel: hvert led bygges ud fra de to før det.

Hvad er forskellen på memoisering og tabulering?

Memoisering beholder den rekursive kode og gemmer hvert svar, første gang det beregnes, så senere kald bare læser det. Tabulering fylder tabellen i en rækkefølge, der sikrer, at hvert svar, en celle har brug for, allerede er der. Begge laver de samme additioner; tabulering undgår kaldstakken, og memoisering beregner kun de celler, der faktisk er brug for.

Hvor mange additioner kræver F(n)?

n − 1 med en tabel: én for hvert led fra F(2) til F(n). Kun de sidste to led bliver nogensinde læst, så et program kan også nøjes med at gemme to tal i stedet for hele tabellen.

Hvorfor stopper appen ved n = 40?

F(40) = 102.334.155 kan stadig nemt være på skærmen, og almindelig rekursion ville allerede bruge 331.160.281 kald på det. Større led vokser hurtigt: F(78) er det største, et JavaScript-tal kan rumme præcist.

Bliver noget sendt nogen steder hen?

Nej. Alt beregnes i din browser, og dine seneste indstillinger bliver i denne browsers lokale lager.

Er du klar til at prøve?

Åbn PictorX i din browser – ingen installation og intet kreditkort for at komme i gang.

Gå til Editor