#302 · Subiectul II · Programare

Primii n termeni ai șirului lui Fibonacci, separați prin virgulă

✓ Rezolvare explicatăTeleorman 2026 · nr. 61

Enunț

Se citește un număr natural n. Să se afișeze primii n termeni ai șirului lui Fibonacci.

Exemple

Date de intrare	Date de ieșire
`6`	`1,1,2,3,5,8`
`1`	`1`

Al doilea exemplu e construit și verificat de mână. Exemplul oficial fixează două lucruri pe care enunțul nu le spune: șirul pornește de la 1, 1 (nu de la 0, 1), iar termenii se separă prin virgulă, fără virgulă la final.

⚠️ Enunțul nu dă nicio limită pentru n. Cu long long, termenii sunt corecți până la al 92-lea inclusiv; de la al 93-lea, niciun tip întreg cu semn din C++ nu-i mai poate ține.

Rezolvare

C++

#include <iostream>
using namespace std;

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

    long long a = 1, b = 1;          // a = termenul curent, b = urmatorul
    for (int i = 1; i <= n; i++) {
        if (i > 1)
            cout << ',';             // virgula doar INTRE termeni
        cout << a;
        long long urm = a + b;       // calculam inainte sa suprascriem
        a = b;
        b = urm;
    }
    return 0;
}

Cum funcționează

Un șir recurent e un șir în care fiecare termen se calculează din cei dinaintea lui. La Fibonacci, regula e: primii doi termeni sunt 1 și 1, iar fiecare termen nou e suma ultimilor doi.

1, 1, 2, 3, 5, 8, 13, 21, ...
      └1+1  └1+2 └2+3

Ideea care face rezolvarea scurtă: nu ai nevoie de vector. Ca să calculezi termenul următor îți trebuie doar ultimii doi, deci două variabile ajung, oricât de mare ar fi n. Perechea (a, b) avansează la fiecare pas în (b, a + b):

pas	`a` (se afișează)	`b`	`urm = a + b`
1	1	1	2
2	1	2	3
3	2	3	5
4	3	5	8
5	5	8	13
6	8	13	21

Ordinea din buclă contează: întâi afișezi a, apoi avansezi. Dacă avansezi întâi, primul 1 nu mai apare.

Variabila urm există din același motiv ca aux la o interschimbare: dacă scrii direct a = b; b = a + b;, pe a doua linie a are deja valoarea nouă, deci aduni b cu el însuși.

Virgula se scrie înaintea fiecărui termen, cu excepția primului — așa nu rămâne o virgulă în plus la final, fără să trebuiască să știi care e ultimul termen.

Același subiect apare și în varianta de la Dolj, unde șirul e definit explicit cu f(0) = 0 și pornește de la 0, 1. Ambele convenții sunt corecte; decide exemplul din subiect. Aici exemplul începe cu 1,1.

Greșeli frecvente

a = b; b = a + b; fără variabilă temporară — pe a doua linie a e deja b, deci b se dublează: ies 1,1,2,4,8,16 în loc de 1,1,2,3,5,8. Primii trei termeni coincid, de aceea greșeala trece de un test făcut doar pe n = 3.
int în loc de long long — al 47-lea termen (2971215073) depășește deja int-ul și se afișează un număr negativ, fără nicio eroare.
Pornirea de la 0, 1 — tot șirul se decalează cu un termen față de exemplu: 0,1,1,2,3,5.
cout << a << ',' pe fiecare pas — ultima virgulă rămâne în plus: 1,1,2,3,5,8,. Evaluatorul compară exact formatul din exemplu.
Recursivitate (fib(n) = fib(n-1) + fib(n-2)) — corectă matematic, dar recalculează aceiași termeni de foarte multe ori; pentru n = 45 durează deja secunde.

Exersează mai departe

Probleme cu aceeași tehnică

#073ProgramareSă se afişeze primii n termeni ai şirului lui Fibonacci #173ProgramareMatrice completată cu termeni din șirul lui Fibonacci #247ProgramarePrimii n termeni ai șirului 1, 1 2, 1 2 3, … (șir format din grupe)#253ProgramareAl n-lea termen al șirului 1, 2, …, 9, 11, 22, …, 99, 111, …#255ProgramareVerifică dacă două numere sunt termeni consecutivi în șirul lui Fibonacci #582ProgramareMedia numerelor prime din șirul lui Fibonacci aflate într-o matrice (fibo și divprim)