Șiruri definite prin recurență

Fibonacci și rudele lui: cum calculezi termenul n fără vector, de ce contează ordinea atribuirilor și unde depășește tipul.

Ce înseamnă recurent

Un șir este definit prin recurență când fiecare termen se calculează din cei dinainte.

Cel mai cunoscut este șirul lui Fibonacci:

F₁ = 1, F₂ = 1
Fₙ = Fₙ₋₁ + Fₙ₋₂,  pentru n ≥ 3

adică 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, …

O definiție prin recurență are întotdeauna două părți: termenii de pornire și regula. Fără termenii de pornire, regula nu are de unde începe.

Cu vector

Traducerea directă:

int f[50];
f[1] = 1;
f[2] = 1;
for (int i = 3; i <= n; i++)
    f[i] = f[i-1] + f[i-2];
cout << f[n];

Merge, dar folosește n locuri de memorie ca să afișeze un singur număr.

Fără vector

La fiecare pas îți trebuie doar ultimii doi termeni:

int a = 1, b = 1;       // F₁ și F₂
for (int i = 3; i <= n; i++) {
    int c = a + b;      // termenul următor
    a = b;
    b = c;
}
cout << b;

Ai trei variabile în loc de un vector întreg.

Ordinea atribuirilor contează foarte mult. Dacă scrii a = b; b = a + b;, ai stricat pe a înainte să-l folosești și obții cu totul alt șir. De aceea calculăm întâi suma într-o a treia variabilă.

Se poate și fără a treia variabilă, dar cu grijă:

b = a + b;
a = b - a;      // vechiul b

Codul e mai scurt, dar mai greu de citit. Nu merită.

Cazurile mici trebuie tratate. Pentru n = 1 sau n = 2 bucla nu pornește și b este 1. Rezultatul e corect din întâmplare, dar verifică de fiecare dată, pentru că la alte șiruri nu se potrivește.

Depășirea

Fibonacci crește foarte repede. F₄₇ depășește un int, iar F₉₃ depășește un long long.

Dacă enunțul spune „n ≤ 40", int ajunge. Dacă spune „n ≤ 80", ai nevoie de long long. Dacă spune „n ≤ 1000", rezultatul nu încape în niciun tip, deci problema cere sigur altceva. De obicei cere ultima cifră sau restul împărțirii la un număr.

Regula e generală: limitele din enunț îți spun ce tip să folosești. Citește-le înainte să scrii prima linie.

Alte recurențe

Tiparul se schimbă foarte puțin.

Suma primelor n numere naturale

S₁ = 1,  Sₙ = Sₙ₋₁ + n

long long s = 0;
for (int i = 1; i <= n; i++)
    s += i;

Factorial

0! = 1,  n! = n · (n-1)!

long long p = 1;
for (int i = 1; i <= n; i++)
    p *= i;

20! este ultimul care încape în long long.

Un șir cu trei termeni de pornire

T₁ = 1, T₂ = 2, T₃ = 3
Tₙ = Tₙ₋₁ + Tₙ₋₂ + Tₙ₋₃

int a = 1, b = 2, c = 3;
for (int i = 4; i <= n; i++) {
    int d = a + b + c;
    a = b; b = c; c = d;
}

Structura e aceeași: păstrezi atâtea variabile câți termeni îți trebuie.

La Subiectul I

Un item frecvent îți dă recurența și îți cere un anumit termen. Sau invers: îți dă termenii și te întreabă care este regula.

În primul caz, fă tabelul. În al doilea, uită-te la diferențe și la rapoarte. Dacă diferențele sunt constante, șirul este aritmetic. Dacă rapoartele sunt constante, e geometric. Dacă fiecare termen e suma celor doi dinainte, e de tip Fibonacci.

Pentru 2, 6, 18, 54 rapoartele sunt 3, deci Tₙ = 3 · Tₙ₋₁.

De reținut

• O recurență are termeni de pornire și o regulă. Ai nevoie de amândouă.
• Dacă îți trebuie doar termenul n, nu ai nevoie de vector. Ajung două-trei variabile.
• Calculează termenul nou într-o variabilă separată, apoi mută valorile. Ordinea contează.
• Fibonacci depășește int pe la termenul 47 și long long pe la 93.
• Limitele din enunț îți spun ce tip de date să alegi.