De ce contează?
O pereche de iepuri face o nouă pereche în fiecare lună, iar puii devin fertili după o lună. Numeri perechile lună de lună: 1, 1, 2, 3, 5, 8... Fiecare număr e suma celor două dinaintea lui. Acesta e șirul lui Fibonacci — apare în iepuri, în floarea-soarelui și în multe probleme.
Regula
Fiecare termen e suma celor doi anteriori:
Fₙ = Fₙ₋₁ + Fₙ₋₂, cu F₀ = 0 și F₁ = 1
| Fₙ | 0 | 1 | 1 | 2 | 3 | 5 | 8 | 13 |
| n | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
De ce două cazuri de bază
Regula folosește doi termeni anteriori, deci ai nevoie de două valori de start: F₀ = 0 și F₁ = 1. Cu un singur caz de bază n-ai de unde calcula F₂.
Implementare iterativă (recomandată)
Reținem doar ultimii doi termeni și îi „rotim" la fiecare pas:
#include <iostream>
using namespace std;
int main() {
int n;
cin >> n;
long long a = 0, b = 1; // F0, F1
if (n == 0) { cout << 0; return 0; }
for (int i = 2; i <= n; i++) {
long long c = a + b; // termenul curent
a = b; // rotim: F(i-2) <- F(i-1)
b = c; // F(i-1) <- F(i)
}
cout << b << "\n"; // al n-lea termen
return 0;
}Pentru n = 7 → 13. Folosim trei variabile, O(1) memorie.
„Rotirea" a = b; b = c; mută fereastra cu un pas la dreapta. E tiparul standard pentru
orice recurență care depinde de ultimii câțiva termeni — reții doar fereastra, nu tot șirul.
De ce NU recursiv naiv
Varianta recursivă directă pare elegantă, dar e o capcană:
long long fib(int n) {
if (n < 2) return n;
return fib(n - 1) + fib(n - 2); // LENT: recalculeaza la infinit
}fib(50) face miliarde de apeluri, fiindcă recalculează aceleași valori întruna. Numărul
de apeluri crește ca 2ⁿ. Iterativ, faci doar n pași.
Complexitate
| Metodă | Timp | Spațiu |
|---|---|---|
| iterativ | O(n) | O(1) |
| recursiv naiv | O(2ⁿ) | O(n) stivă |
Capcane reale la Fibonacci:
- Overflow: F₄₇ depășește deja
int. Foloseștelong long(rezistă până spre F₉₂); peste asta, numere mari sau modulo. - Un singur caz de bază: uiți F₀ sau F₁ și recurența pornește greșit.
- Recursiv naiv pe n mare: corect, dar exponențial — depășește timpul. Folosește iterativ (sau memoizare).
- Confuzia indexării: unele probleme pornesc cu F₁ = 1, F₂ = 1. Verifică de unde numără enunțul.
De reținut
- Fₙ = Fₙ₋₁ + Fₙ₋₂, cu două cazuri de bază (F₀=0, F₁=1).
- Iterativ cu „rotirea" a două variabile → O(n) timp, O(1) memorie.
- Evită recursivul naiv (O(2ⁿ)); atenție la overflow de la F₄₇ în sus.