#073Programare

Să se afişeze primii n termeni ai şirului lui Fibonacci

siruri recurente

Enunț

Se citeşte numărul natural nenul n de la tastatură. Să se afişeze primii n termeni ai şirului lui Fibonacci, definit astfel:

f(0) = 0
f(1) = 1
f(n) = f(n-1) + f(n-2),  pentru n > 1

Exemple

Date de intrare	Date de ieșire	Explicații
`10`	`0 1 1 2 3 5 8 13 21 34`	Fiecare termen e suma celor doi dinaintea lui

Rezolvare

C++

#include <iostream>
using namespace std;

int main() {
    int n;
    cin >> n;

    int a = 0, b = 1;                   // primii doi termeni

    for (int i = 0; i < n; i++) {
        cout << a << " ";
        int urmator = a + b;            // calculam inainte sa pierdem valorile
        a = b;
        b = urmator;
    }

    return 0;
}

Cum funcționează

Un șir recurent e un șir în care fiecare termen se calculează din cei dinainte. Fibonacci e cel mai cunoscut: pornești de la 0 și 1, iar fiecare termen nou e suma ultimilor doi.

0, 1, 1, 2, 3, 5, 8, 13, 21, 34
    └──┘  └──┘  └──┘
    0+1   1+1   1+2

Observația care simplifică rezolvarea: nu ai nevoie de vector. Ca să calculezi termenul următor îți trebuie doar ultimii doi, deci două variabile sunt suficiente, indiferent cât de mare e n.

Mecanismul de „avansare" e partea care se greșește. La fiecare pas, perechea (a, b) se transformă în (b, a+b):

a=0  b=1   → afisezi 0
a=1  b=1   → afisezi 1
a=1  b=2   → afisezi 1
a=2  b=3   → afisezi 2
a=3  b=5   → afisezi 3

Variabila urmator e necesară din același motiv ca aux la interschimbări: dacă scrii direct a = b; b = a + b;, atunci la a doua linie a are deja noua valoare, iar suma iese greșită. Calculezi întâi, atribui după.

Afișarea se face la începutul pasului, înainte de avansare — altfel ai sări peste 0 și ai afișa n termeni începând de la al doilea.

Fibonacci se poate scrie și recursiv, dar nu o face la atestat dacă enunțul nu o cere explicit: varianta recursivă simplă recalculează aceiași termeni de mii de ori și devine inutilizabilă chiar și pentru n = 45. Varianta iterativă de mai sus face exact n pași.

Greșeli frecvente

Atribuirea fără variabilă temporară — a = b; b = a + b; dublează valoarea în loc s-o adune corect.
Pornirea de la a = 1, b = 1 — se sare peste 0, iar șirul iese decalat cu un termen.
Afișarea după avansare — lipsește primul termen.
Folosirea recursivității — corect matematic, dar prea lent pentru n mare.
Bucla i <= n — se afișează n + 1 termeni.

Apariții

Dolj 2026 — problema 5 · sursa oficială