...
Eroare Algoritmi și structuri de date · Programare dinamică și memoizare

Fibonacci iterativ dă 1, 2, 4, 8: a = b și b = a + b pe linii separate

Pe scurt

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

Greșit
PYTHON
a = b
b = a + b
Corect
PYTHON
a, b = b, a + b

Partea dreaptă se calculează complet cu valorile vechi, apoi ambele variabile se actualizează deodată.

2Ordinea liniilor inversată

Greșit
PYTHON
b = a + b
a = b
Corect
PYTHON
a, b = b, a + b

Acum a primește noul b, nu pe cel vechi, deci a și b devin egale la fiecare pas.

3Variantă fără atribuire multiplă

Greșit
PYTHON
a = b
b = a + b
Corect
PYTHON
vechi = a
a = b
b = vechi + b

În limbaje fără atribuire multiplă, salvezi valoarea veche într-o variabilă temporară.

Repară tu

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].

Codul care dă eroarea
PYTHON
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)
După reparație, programul afișează
[0, 1, 1, 2, 3, 5, 8, 13]
Indiciu

Actualizează a și b într-o singură atribuire: a, b = b, a + b.

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

← Toate erorile Algoritmi și structuri de date

Tudor Andrei Dumitrescu
Cine a explicat eroarea

Tudor Andrei Dumitrescu

Senior Software Developer · fondatorul Academiei Programatorilor

LinkedIn
  1. 2019 Junior JavaCognizant Softvision
  2. 2021 Mid JavaCognizant Softvision
  3. 2022 Team LeaderEndava
  4. 2023 Senior Software DeveloperUniCredit
  5. Acum Senior Software DeveloperHCLTech
Certificat de absolvire Instructor / Preparator formare, Tudor Andrei Dumitrescu
Certificat de formator autorizatMinisterul Muncii și Ministerul Educației · 2022
Certificat de absolvire Instructor / Preparator formare, Tudor Andrei Dumitrescu

Certificat de formator autorizat · Ministerul Muncii și Ministerul Educației · 2022

Din 2020 construiește Academia Programatorilor, iar din 2026 și JoburiIT.ro. Fiecare eroare de aici a fost reprodusă în editorul nostru: codul greșit chiar dă mesajul din titlu, iar reparația chiar funcționează.

Î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.