Șiruri recurente la atestatul de informatică: Fibonacci și șiruri pe grupe, în C++

La atestat, „șirurile” apar în două forme. Prima e șirul recurent propriu-zis, în care fiecare termen se calculează din cei dinaintea lui — practic întotdeauna șirul lui Fibonacci. A doua e șirul descris prin primii termeni (1, 1 2, 1 2 3, … sau 1, 2, …, 9, 11, 22, …), la care trebuie să ghicești singur regula și s-o transformi în bucle.

Ambele se rezolvă cu aceeași idee: termenii se generează din mers, nu se stochează. Pagina e organizată pe tehnici, de la cea de bază la cele care o refolosesc. Problemele vin din sesiunile Dolj, Galați și Teleorman 2026; lista completă e la final.

Tehnica 1 — Șirul lui Fibonacci, fără vector

Primii doi termeni sunt 1 și 1, iar fiecare termen nou e suma ultimilor doi:

1, 1, 2, 3, 5, 8, 13, 21, 34, 55, ...

Pentru termenul următor îți trebuie doar ultimii doi, deci două variabile ajung, oricât de mare ar fi n. Nu e nevoie de vector.

long long a = 1, b = 1;          // a = termenul curent, b = urmatorul
for (int i = 1; i <= n; i++) {
    cout << a << ' ';
    long long urm = a + b;       // calculam inainte sa suprascriem
    a = b;
    b = urm;
}

La fiecare pas, perechea (a, b) devine (b, a + b):

Trei detalii decid dacă rezolvarea e corectă:

1. Variabila urm e obligatorie. a = b; b = a + b; dublează b în loc să adune doi termeni diferiți și dă 1, 1, 2, 4, 8, 16. Primii trei termeni coincid cu cei corecți, de aceea greșeala scapă la un test pe n mic.
2. Afișezi întâi, avansezi după — altfel lipsește primul termen.
3. long long, nu int. Al 47-lea termen (2971215073) nu mai încape în int; cu long long mergi corect până la al 92-lea.

Două convenții, ambele corecte. Unele subiecte pornesc șirul de la 0, 1 (f(0) = 0, f(1) = 1), altele de la 1, 1. Diferă doar inițializarea: a = 0, b = 1 sau a = 1, b = 1. Decide exemplul din subiect, nu ce ai învățat la clasă — dacă alegi greșit, tot șirul iese decalat cu un termen.

Fibonacci se poate scrie și recursiv, dar varianta recursivă simplă recalculează aceiași termeni de foarte multe ori și devine inutilizabilă deja pe la n = 45. La atestat, scrie-l iterativ.

Probleme: primii n termeni, separați prin virgulă · primii n termeni, pornind de la 0 · matrice completată cu termeni Fibonacci

Tehnica 2 — Oprirea după valoare, nu după număr de termeni

Când întrebarea e despre valori („sunt a și b termeni consecutivi?”, „e x termen Fibonacci?”), nu știi dinainte câți termeni îți trebuie. Bucla for devine while, cu condiția de oprire pe valoare:

int x = 1, y = 1;
while (y < b) {                  // avansam pana cand y ajunge la b sau il depaseste
    int urm = x + y;
    x = y;
    y = urm;
}
// acum y e cel mai mic termen >= b, iar x e termenul dinaintea lui
if (x == a && y == b) cout << "DA"; else cout << "NU";

Avantajul: nu trebuie să estimezi câți termeni să generezi. Un vector de 20 de termeni ar părea suficient „din ochi”, dar al 20-lea termen e abia 6765, iar subiectul merge până la 32000.

Capcana e perechea 1 1: 1 apare de două ori la începutul șirului. Pornind cu x = y = 1, ea se recunoaște fără niciun pas.

Probleme: doi termeni consecutivi în șirul lui Fibonacci

Tehnica 3 — Șiruri generate pe grupe

Șirul 1, 1 2, 1 2 3, 1 2 3 4, … nu e recurent în sens strict, dar are o structură clară: grupa k conține numerele de la 1 la k. Structura „pe grupe” se traduce în două bucle imbricate — cea exterioară alege grupa, cea interioară scrie termenii ei.

Dificultatea reală e oprirea la exact n termeni, chiar și la mijlocul unei grupe. Un contor de termeni afișați intră în condiția ambelor bucle:

int afisate = 0;
for (int k = 1; afisate < n; k++)
    for (int i = 1; i <= k && afisate < n; i++) {
        cout << i << ' ';
        afisate++;
    }

Dacă pui condiția doar în bucla exterioară, grupa începută se termină întreagă și scrii prea mulți termeni: pentru n = 23 ies 28.

Probleme: șirul 1, 1 2, 1 2 3, …

Tehnica 4 — Formula directă pentru al n-lea termen

Când toate grupele au aceeași lungime, nu mai trebuie să generezi nimic: poziția se calculează. Șirul 1, 2, …, 9, 11, 22, …, 99, 111, … are grupe de câte 9 termeni (cifrele 1–9, scrise o dată, de două ori, de trei ori…). Numerotând de la 0, cu p = n - 1:

int k = (n - 1) / 9 + 1;     // grupa = numarul de cifre
int c = (n - 1) % 9 + 1;     // cifra care se repeta
for (int i = 0; i < k; i++)
    cout << c;

Tiparul (n - 1) / L și (n - 1) % L funcționează pentru orice șir cu grupe de lungime fixă L. -1-ul e esențial: fără el, ultimul termen al fiecărei grupe se calculează greșit (n = 9 ar da cifra 0).

Și încă o lecție: termenul se afișează cifră cu cifră, nu se construiește ca număr. Pentru n = 100 are 12 cifre, iar într-un int primul termen care nu mai încape e al 83-lea.

Probleme: al n-lea termen al șirului 1, 2, …, 9, 11, 22, …

Greșeli care se repetă

• a = b; b = a + b; fără variabilă temporară — ies puteri ale lui 2 în loc de Fibonacci
• int la Fibonacci — depășire de la al 47-lea termen, fără nicio eroare afișată
• Convenția greșită (0, 1 vs 1, 1) — tot șirul decalat cu un termen
• Virgulă sau spațiu în plus la final — scrie separatorul înaintea termenilor, nu după
• Condiția de oprire doar în bucla exterioară — grupa începută se termină întreagă
• Formulele de poziție fără n - 1 — ultimul termen din fiecare grupă iese greșit
• Recursivitate pentru Fibonacci — corectă, dar mult prea lentă pentru n de ordinul zecilor

Unde exersezi mai departe

Șirurile descrise prin primii termeni sunt un tip de problemă în care contează exercițiul: trebuie să recunoști repede regula și forma buclelor.

Pentru asta, pbinfo.ro e cea mai bună resursă românească: peste 2500 de probleme de informatică cu evaluator automat, și o trimiți la testat direct din browser. E construită pentru olimpiadă și bacalaureat, deci se completează cu ce găsești aici — noi acoperim subiectele de atestat, cu rezolvări scrise.

Toate problemele din această categorie

Fiecare are rezolvare completă în C++, explicată pas cu pas.