De ce contează?
Fibonacci nu e singurul șir construit din predecesori. Unele privesc trei termeni înapoi, altele înmulțesc, altele combină. Schema rămâne aceeași: cunoști câteva valori de start și o regulă, apoi „aluneci" o fereastră peste șir. Doar fereastra își schimbă mărimea.
Aceeași idee, reguli variate
O recurență e definită de două lucruri: câți predecesori folosește și cum îi combină. Câteva exemple:
| Șir | Regulă | Predecesori | Start |
|---|---|---|---|
| aritmetic | aₙ = aₙ₋₁ + r | 1 | a₀ |
| geometric | aₙ = aₙ₋₁ · q | 1 | a₀ |
| Fibonacci | aₙ = aₙ₋₁ + aₙ₋₂ | 2 | a₀, a₁ |
| Tribonacci | aₙ = aₙ₋₁ + aₙ₋₂ + aₙ₋₃ | 3 | a₀, a₁, a₂ |
| aₙ = 2aₙ₋₁ + 1 | mixt | 1 | a₀ |
Regula de aur: câți predecesori folosește recurența, atâtea cazuri de bază ai nevoie și atâtea variabile reții în fereastră. Tribonacci → 3 valori de start, 3 variabile.
Algoritm pas cu pas: Tribonacci
T₀ = 0, T₁ = 1, T₂ = 1, apoi fiecare termen = suma ultimilor trei:
| Tₙ | 0 | 1 | 1 | 2 | 4 | 7 | 13 |
| n | 0 | 1 | 2 | 3 | 4 | 5 | 6 |
| n | calcul | Tₙ |
|---|---|---|
| 3 | 0+1+1 | 2 |
| 4 | 1+1+2 | 4 |
| 5 | 1+2+4 | 7 |
| 6 | 2+4+7 | 13 |
Implementare: fereastră de 3 variabile
#include <iostream>
using namespace std;
int main() {
int n;
cin >> n;
long long a = 0, b = 1, c = 1; // T0, T1, T2
if (n == 0) { cout << a; return 0; }
if (n == 1 || n == 2) { cout << 1; return 0; }
for (int i = 3; i <= n; i++) {
long long d = a + b + c; // termenul curent
a = b; // alunecam fereastra
b = c;
c = d;
}
cout << c << "\n";
return 0;
}Pentru n = 6 → 13.
Alunecarea a = b; b = c; c = d; mută fereastra de trei termeni cu un pas. Exact tiparul
de la Fibonacci, doar cu o variabilă în plus. Generalizezi la oricâți predecesori.
Recurență multiplicativă: aₙ = 2aₙ₋₁ + 1
Depinde de un singur predecesor, deci o variabilă ajunge:
long long termen = 0; // a0
for (int i = 1; i <= n; i++) {
termen = 2 * termen + 1; // 0, 1, 3, 7, 15, ...
}Crește rapid — atenție la overflow.
Complexitate
| Vrei | Timp | Spațiu |
|---|---|---|
| al n-lea termen | O(n) | O(k) — fereastra de k predecesori |
Capcane reale la șiruri recurente:
- Prea puține cazuri de bază: Tribonacci cu doar două valori de start → al treilea termen pornește greșit. Numărul de start = numărul de predecesori.
- Ordinea alunecării: dacă suprascrii
aînainte să-l folosești înd, strici fereastra. Calculează termenul nou înainte de a aluneca. - Overflow: recurențele multiplicative (·2, +) cresc exponențial;
long longși, la nevoie, modulo. - Reții tot șirul fără motiv: dacă vrei doar al n-lea termen, fereastra de k variabile ajunge — nu aloca un vector uriaș.
De reținut
- O recurență = câți predecesori + cum îi combină; tot atâtea cazuri de bază și variabile.
- Alunecă fereastra: calculează termenul nou, apoi mută variabilele.
- Al n-lea termen în O(n) timp, O(k) memorie; atenție la overflow la regulile multiplicative.