Celule completate
Adunări
Apeluri fără tabel

  • Se completează
  • Citită
  • Răspuns

Mai multe despre Fibonacci cu programare dinamică

Fibonacci cu programare dinamică

Numerele Fibonacci sunt primul exemplu clasic de programare dinamică. Recursivitatea simplă cere aceiași termeni iar și iar, dar cu un tabel care reține fiecare termen, munca crește doar odată cu n. Alegeți un termen, alegeți metoda ascendentă sau descendentă și avansați pas cu pas pentru a vedea fiecare celulă completată o singură dată. Apăsați Redare pentru a urmări cum se completează tabelul sau folosiți Pas și Înapoi pentru a avansa câte un pas. Trageți glisorul pentru pași pentru a sări oriunde. Alegeți n, termenul de calculat, și metoda: Ascendentă completează tabelul de la stânga, Descendentă păstrează recursivitatea, dar se uită mai întâi în tabel, iar rândul de sub tabel este atunci stiva apelurilor deschise. Exemplu nou alege alt n. Cu tabla selectată, tastele săgeți avansează pas cu pas, bara de spațiu pornește și oprește redarea, iar Home și End sar la început și la sfârșit.

Cum funcționează

  1. Introduceți n, termenul de calculat, și alegeți Ascendentă sau Descendentă.
  2. Apăsați Redare sau folosiți Pas și Înapoi pentru a avansa câte un pas. Trageți glisorul pentru pași pentru a sări oriunde.
  3. Urmăriți cum fiecare celulă citește cele două celule dinaintea ei. La metoda Descendentă, rândul de sub tabel este stiva apelurilor deschise.

Metoda ascendentă și cea descendentă

Metoda ascendentă (bottom-up), numită și tabelare, pornește de la F(0) = 0 și F(1) = 1 și completează tabelul de la stânga la dreapta: fiecare celulă nouă este suma celor două celule dinaintea ei. Metoda descendentă (top-down), numită și memoizare, păstrează definiția recursivă: pentru a afla F(n), cere F(n − 1) și F(n − 2). Diferența față de recursivitatea simplă este că fiecare apel se uită mai întâi în tabel și calculează un termen doar dacă celula lui este încă goală. Ambele completează fiecare celulă o dată și folosesc n − 1 adunări.

De ce recursivitatea simplă este atât de lentă

Fără tabel, F(n) apelează F(n − 1) și F(n − 2), ambele apelează F(n − 3) și așa mai departe: apelurile formează un arbore în care aceiași termeni apar iar și iar. Numărul de apeluri este 2·F(n + 1) − 1 și crește la fel de repede ca numerele Fibonacci însele: 177 de apeluri pentru F(10), 21.891 pentru F(20) și peste 331 de milioane pentru F(40). Tocmai pentru subprobleme suprapuse ca acestea există programarea dinamică.

Întrebări frecvente

Ce este programarea dinamică?

O metodă de a rezolva o problemă împărțind-o în probleme mai mici care se suprapun, rezolvând fiecare problemă mai mică o singură dată și păstrându-i răspunsul într-un tabel. Numerele Fibonacci sunt cel mai simplu exemplu: fiecare termen se construiește din cei doi dinaintea lui.

Care este diferența dintre memoizare și tabelare?

Memoizarea păstrează codul recursiv și salvează fiecare răspuns prima dată când este calculat, astfel încât apelurile ulterioare doar îl citesc. Tabelarea completează tabelul într-o ordine care garantează că fiecare răspuns de care are nevoie o celulă este deja acolo. Ambele fac aceleași adunări; tabelarea evită stiva de apeluri, iar memoizarea calculează doar celulele de care este într-adevăr nevoie.

Câte adunări necesită F(n)?

n − 1 cu un tabel: câte una pentru fiecare termen de la F(2) la F(n). Sunt citiți mereu doar ultimii doi termeni, așa că un program poate păstra și doar două numere în loc de tot tabelul.

De ce se oprește aplicația la n = 40?

F(40) = 102.334.155 încape încă ușor pe ecran, iar recursivitatea simplă ar avea deja nevoie de 331.160.281 de apeluri pentru el. Termenii mai mari cresc repede: F(78) este cel mai mare pe care un număr JavaScript îl reține exact.

Se trimite ceva undeva?

Nu. Totul este calculat în browserul dumneavoastră, iar ultimele setări rămân în stocarea locală a acestui browser.

Ești gata să încerci?

Deschide PictorX în browser – fără instalare și fără card de credit.

Mergi la editor