Fibonacci iterativ dă 1, 2, 4, 8: a = b și b = a + b pe linii separate
Pe linii separate, a = b suprascrie valoarea veche a lui a înainte să o folosești în b = a + b, deci b se dublează la fiecare pas. Fă actualizarea simultan: a, b = b, a + b, sau salvează valoarea veche într-o variabilă temporară.
Explicat de Tudor Andrei Dumitrescu, Senior Software Developer, fondatorul Academiei ProgramatorilorActualizat la
Ce înseamnă
Varianta iterativă a șirului lui Fibonacci (și a oricărei recurențe care depinde de ultimele două valori, ca problema treptelor) ține doar două numere: a (penultimul) și b (ultimul). La fiecare pas, noul ultim e a + b, iar noul penultim e vechiul b.
Dacă scrii a = b și apoi b = a + b, pe al doilea rând a are deja valoarea nouă (egală cu b), deci calculezi b + b. Șirul devine 1, 2, 4, 8, 16, adică puteri ale lui 2.
În Python, atribuirea multiplă a, b = b, a + b evaluează întâi toată partea dreaptă, cu valorile vechi, și abia apoi atribuie. Nu primești nicio eroare, doar numere greșite, de obicei observate abia de la al patrulea termen.
De ce apare: cauzele frecvente
1Actualizare pe linii separate
a = b
b = a + ba, b = b, a + bPartea dreaptă se calculează complet cu valorile vechi, apoi ambele variabile se actualizează deodată.
2Ordinea liniilor inversată
b = a + b
a = ba, b = b, a + bAcum a primește noul b, nu pe cel vechi, deci a și b devin egale la fiecare pas.
3Variantă fără atribuire multiplă
a = b
b = a + bvechi = a
a = b
b = vechi + bÎn limbaje fără atribuire multiplă, salvezi valoarea veche într-o variabilă temporară.
Repară eroarea, direct în pagină
Funcția primii_fibonacci(n) returnează primii n termeni ai șirului lui Fibonacci. Testul cu assert pică: de la al patrulea termen numerele se dublează. Repar-o ca să afișeze [0, 1, 1, 2, 3, 5, 8, 13].
def primii_fibonacci(n):
rez = []
a, b = 0, 1
for _ in range(n):
rez.append(a)
a = b
b = a + b
return rez
rez = primii_fibonacci(8)
assert rez == [0, 1, 1, 2, 3, 5, 8, 13], f'sir gresit: {rez}'
print(rez)[0, 1, 1, 2, 3, 5, 8, 13]
Indiciu
Actualizează a și b într-o singură atribuire: a, b = b, a + b.
Reparația
def primii_fibonacci(n):
rez = []
a, b = 0, 1
for _ in range(n):
rez.append(a)
a, b = b, a + b
return rez
rez = primii_fibonacci(8)
assert rez == [0, 1, 1, 2, 3, 5, 8, 13], f'sir gresit: {rez}'
print(rez)De ce merge
După a = b, variabila a avea deja valoarea lui b, deci b = a + b calcula de fapt b + b și dubla numărul: rezultatul era [0, 1, 2, 4, 8, ...]. Cu a, b = b, a + b, partea dreaptă se calculează cu valorile vechi (b vechi și a + b vechi), apoi ambele variabile primesc noile valori deodată.
Cum o eviți pe viitor
Când mai multe variabile se actualizează pe baza valorilor vechi, scrie actualizarea într-o singură atribuire multiplă. Afișează primii 8 termeni și compară-i cu șirul cunoscut (0, 1, 1, 2, 3, 5, 8, 13). Același tipar apare la interschimbări (a, b = b, a) și la recurențe cu trei termeni.
Întrebări frecvente
De ce funcționează atribuirea multiplă?
Python construiește întâi tuplul din dreapta, (b, a + b), cu valorile curente, apoi îl despachetează în a și b. Niciuna nu se schimbă înainte de calculul complet.
E mai rapidă decât varianta cu listă dp?
Ambele sunt O(n) ca timp, dar cu două variabile memoria e O(1) în loc de O(n).
Erori înrudite
Recursivitatea fără memoizare rulează la nesfârșit: fib(40) nu se mai termină Funcția recursivă recalculează aceleași subprobleme de un număr exponențial de ori (fib(40) face sute de milioane de apeluri), așa că pare blocată și editorul o oprește după limita de timp. Salvează rezultatele: @lru_cache(maxsize=None) sau un dicționar memo. TypeError: 'functools._lru_cache_wrapper' object is not subscriptable Ai scris numele funcției memoizate cu paranteze pătrate, drumuri[n - 1], ca și cum ar fi un tabel DP. O funcție se apelează cu paranteze rotunde: drumuri(n - 1). Paranteze pătrate folosești doar pentru liste și dicționare (dp[i]). IndexError: list index out of range la dp[n] (tabelul DP e prea scurt) Ai creat tabelul cu dp = [0] * n, dar răspunsul e dp[n], iar o listă cu n elemente are doar indicii 0..n-1. Când dp[i] înseamnă „primele i elemente” sau „treapta i”, tabelul are nevoie de n + 1 poziții: dp = [0] * (n + 1). Învață Algoritmi și structuri de date de la zero, cu exerciții la fiecare lecție
Curs Algoritmi pentru interviuri: lecții scurte, fiecare cu un exercițiu verificat automat, direct în browser. Primele 2 lecții sunt gratuite.
