Șirul Fibonacci

În convenția $F_0=0$, $F_1=1$, fiecare termen ulterior este suma celor doi anteriori: $F_n=F_{n-1}+F_{n-2}$ pentru $n\ge 2$. Primii termeni sunt 0, 1, 1, 2, 3, 5. O problemă poate folosi altă numerotare; citește valorile inițiale din enunț înainte de a calcula.

Șirul lui Fibonacci este definit prin recurență de ordinul doi: un termen se obține din ceilalți doi dinaintea lui. Manualele de liceu îl scriu adesea $f_1=f_2=1$ și $f_n=f_{n-1}+f_{n-2}$ pentru $n\ge 3$, iar matematica îl începe cu $F_0=0$, $F_1=1$. Cele două scrieri dau aceleași valori, 1, 1, 2, 3, 5, 8, 13, 21, ..., numai că $F_n=f_n$ pentru $n\ge 1$: indicele este singura diferență. De aceea, la fiecare problemă citești întâi ce valori are enunțul pentru primii doi termeni.

Nu este nevoie de un vector. Ca să calculezi termenul următor îți trebuie doar ultimii doi, deci ții în memorie două variabile, $a$ și $b$, cu $a=F_i$ și $b=F_{i+1}$. La fiecare pas se calculează suma, apoi cele două variabile „alunecă” cu o poziție: $a$ primește vechea valoare a lui $b$, iar $b$ primește suma. Timpul este proporțional cu $n$, iar memoria auxiliară este constantă.

Exemplul 1 — termenul de rang $n$. Se citește $n$ și se afișează $F_n$.

#include <iostream>
using namespace std;
int main() {
    int n;
    cin >> n;
    long long a = 0, b = 1; // a = F(i), b = F(i+1), pentru i = 0
    for (int i = 0; i < n; ++i) {
        long long urmator = a + b;
        a = b;
        b = urmator;
    }
    cout << a;
    return 0;
}

Pentru $n=5$ perechea $(a,b)$ se schimbă astfel: $(0,1)\to (1,1)\to (1,2)\to (2,3)\to (3,5)\to (5,8)$. După cinci pași $a=5$, deci se afișează $F_5=5$. Pentru $n=0$ bucla nu se execută și se afișează 0, iar pentru $n=1$ se afișează 1. Pentru $n=10$ se afișează 55, iar pentru $n=20$ se afișează 6765.

Același ciclu răspunde și la întrebări de numărare. Printre $F_0,\dots ,F_{12}$, adică 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, sunt cinci termeni pari; îi numeri testând a % 2 == 0 la fiecare pas, înainte de actualizarea perechii.

Exemplul 2 — primul termen care depășește o limită. Se cere primul termen din șirul $1,1,2,3,\dots$ care este cel puțin 100 și poziția lui.

1. Pornești cu $a=1$, $b=1$, $k=2$, unde $b$ este al $k$-lea termen.
2. Cât timp $b<100$, calculezi $c=a+b$, muți $a\leftarrow b$, $b\leftarrow c$ și crești $k$.
3. La ieșire din ciclu, $b\ge 100$ este primul termen cerut, pe poziția $k$.

int a = 1, b = 1, c, k = 2;
while (b < 100) {
    c = a + b;
    a = b;
    b = c;
    k++;
}
cout << k << ' ' << b;

Secvența, rulată într-un program complet, afișează 12 144: termenul al 11-lea, 89, este încă mai mic decât 100, iar al 12-lea, 144, îl depășește.

Exemplul 3 — suma primilor $n$ termeni. Se cere $S_n=f_1+f_2+\dots +f_n$, cu $f_1=f_2=1$. Un ciclu adaugă la fiecare pas termenul curent:

long long a = 1, b = 1, s = 0;
for (int i = 1; i <= n; ++i) {
    s += a;
    long long urmator = a + b;
    a = b;
    b = urmator;
}
cout << s;

Pentru $n=6$ termenii adăugați sunt 1, 1, 2, 3, 5, 8, iar sumele parțiale sunt 1, 2, 4, 7, 12, 20; se afișează 20. Se observă că $S_6=20=f_8-1$, unde $f_8=21$. Relația $S_n=f_{n+2}-1$ este adevărată pentru orice $n\ge 1$ și permite verificarea rezultatului: sumele parțiale 1, 2, 4, 7, 12 sunt cu 1 mai mici decât 2, 3, 5, 8, 13, adică termenii $f_3,\dots ,f_7$. Greșeala tipică este să pornești suma cu $s=1$ sau să aduni termenul după ce perechea a alunecat; în ambele cazuri se obține un rezultat decalat.

Limitele tipului. Termenii cresc repede. Cel mai mare termen care încape în long long este $F_{92}=7540113804746346429$, iar $F_{93}$ depășește $9223372036854775807$ și încape numai în unsigned long long. Dacă enunțul impune limite pentru $n$, alegi tipul după ele.

La un fragment cu recurență urmărești simultan ambele variabile și ordinea actualizărilor. Pașii unei secvențe de forma „$a\leftarrow b$; $b\leftarrow a+b$” nu produc șirul lui Fibonacci: după prima atribuire $a$ și $b$ sunt egale, iar suma devine dublul lui $b$. Pornind de la $a=0$, $b=1$, valorile sunt $1,2$, apoi $2,4$, apoi $4,8$: se dublează. Corect este să salvezi suma într-o a treia variabilă sau să calculezi $b\leftarrow a+b$ înainte de $a\leftarrow b-a$.

Verifică și cazurile mici: dacă ciclul face $n$ pași, la $n=0$ răspunsul este valoarea inițială a lui $a$, iar la $n=2$ obții $F_2=1$.

Exemplu în formatul examenului. Ce se afișează în urma executării secvenței de mai jos?

int a = 0, b = 1;
for (int i = 0; i < 4; ++i) {
    a = b;
    b = a + b;
    cout << a << ' ' << b << '\n';
}

Variante:

• a) 1 1, 1 2, 2 3, 3 5
• b) 1 2, 2 4, 4 8, 8 16
• c) 1 2, 2 3, 3 5, 5 8
• d) 1 1, 1 1, 1 1, 1 1

Răspunsul corect este b). În prima iterație $a$ primește 1, iar $b=a+b=1+1=2$. În a doua, $a=2$ și $b=2+2=4$. Fiecare iterație dublează perechea, deci ultima linie este 8 16. Varianta a) ar fi corectă numai dacă suma s-ar calcula înainte de atribuirea lui $a$.

Al doilea exemplu în formatul examenului. Ce se afișează în urma executării secvenței de mai jos?

int a = 1, b = 2, s = 0;
for (int i = 0; i < 5; ++i) {
    s = s + a;
    int c = a + b;
    a = b;
    b = c;
}
cout << s;

• a) 19
• b) 32
• c) 12
• d) 8

Răspunsul corect este a). Ciclul se execută de cinci ori, iar la fiecare iterație a ia pe rând valorile 1, 2, 3, 5, 8, care se adaugă la s. Suma este $1+2+3+5+8=19$. Varianta b) rezultă dacă se fac șase iterații, nu cinci, iar varianta d) este ultima valoare a lui a în ciclu, nu suma.

Greșeli frecvente

• Greșit: orice șir Fibonacci începe obligatoriu cu 1, 1 indiferent de enunț.
  Corect: verifică termenii inițiali și indexarea.
• Greșit: $F_5=8$ în convenția $F_0=0$.
  Corect: $F_5=5$.
• Greșit: actualizările pot fi făcute fără a păstra valoarea veche necesară.
  Corect: folosește un temporar.

Înainte și după