Șirul lui Fibonacci și alte șiruri recurente

Un șir recurent este un șir în care fiecare termen depinde de unul sau mai mulți termeni anteriori.

Cel mai cunoscut exemplu este șirul lui Fibonacci.

Șirul lui Fibonacci

Definiție

primul termen: F(1) = 1
al doilea termen: F(2) = 1
de la al treilea termen: F(n) = F(n-1) + F(n-2)

Adică fiecare termen este suma celor doi termeni anteriori.

Primii termeni

n	1	2	3	4	5	6	7	8	9	10
F(n)	1	1	2	3	5	8	13	21	34	55

Verificare: 2 = 1+1, 3 = 2+1, 5 = 3+2, 8 = 5+3, …

Generarea primilor n termeni Fibonacci

Ideea: avem nevoie de doi termeni anteriori la fiecare pas. Îi păstrăm în două variabile.

#include <iostream>
using namespace std;

int main()
{
    int n;
    cin >> n;

    int a = 1, b = 1;

    cout << a << " ";
    if (n >= 2) cout << b << " ";

    for (int i = 3; i <= n; i++) {
        int c = a + b;
        cout << c << " ";
        a = b;
        b = c;
    }

    return 0;
}

Input:
10

Output:
1 1 2 3 5 8 13 21 34 55

Pas cu pas

Pas	a	b	c = a + b	Afișăm
start	1	1	-	1, 1
i=3	1	1	2	2
i=4	1	2	3	3
i=5	2	3	5	5
i=6	3	5	8	8
i=7	5	8	13	13
i=8	8	13	21	21
i=9	13	21	34	34
i=10	21	34	55	55

Cum funcționează „deplasarea”?

La fiecare pas: 1. Calculăm noul termen: c = a + b 2. a devine b (termenul penultim devine cel mai vechi) 3. b devine c (noul termen devine cel mai recent)

Imaginează-ți o fereastră care se mișcă pe șir: vedem mereu doar ultimii doi termeni, iar din ei calculăm pe următorul.

Al n-lea termen Fibonacci

Dacă vrem doar termenul de pe poziția n, nu trebuie să afișăm tot șirul:

#include <iostream>
using namespace std;

int main()
{
    int n;
    cin >> n;

    int a = 1, b = 1;

    for (int i = 3; i <= n; i++) {
        int c = a + b;
        a = b;
        b = c;
    }

    cout << b;

    return 0;
}

Input:
7

Output:
13

Suma primilor n termeni Fibonacci

#include <iostream>
using namespace std;

int main()
{
    int n;
    cin >> n;

    int a = 1, b = 1;
    int suma = a;
    if (n >= 2) suma = suma + b;

    for (int i = 3; i <= n; i++) {
        int c = a + b;
        suma = suma + c;
        a = b;
        b = c;
    }

    cout << suma;

    return 0;
}

Input:
10

Output:
143

Verificarea: este un număr termen Fibonacci?

Generăm termeni Fibonacci până depășim n și verificăm dacă vreunul este egal cu n:

#include <iostream>
using namespace std;

int main()
{
    int n;
    cin >> n;

    int a = 1, b = 1;

    while (b < n) {
        int c = a + b;
        a = b;
        b = c;
    }

    if (b == n || a == n) {
        cout << "DA";
    } else {
        cout << "NU";
    }

    return 0;
}

Input:
21

Output:
DA

Input:
10

Output:
NU

Alte șiruri recurente

Șirul lui Fibonacci nu este singurul șir recurent. Iată câteva exemple:

Șirul cu regula `a(n) = 2 * a(n-1) - a(n-2)`

Primii termeni (cu a(1) = 1, a(2) = 3):

1, 3, 5, 7, 9, 11, ...

Acesta generează numerele impare!

#include <iostream>
using namespace std;

int main()
{
    int n;
    cin >> n;

    int a = 1, b = 3;

    cout << a << " ";
    if (n >= 2) cout << b << " ";

    for (int i = 3; i <= n; i++) {
        int c = 2 * b - a;
        cout << c << " ";
        a = b;
        b = c;
    }

    return 0;
}

Input:
8

Output:
1 3 5 7 9 11 13 15

Șirul cu regula `a(n) = a(n-1) + a(n-2) + a(n-3)`

Un șir care depinde de trei termeni anteriori (tribonacci):

Primii termeni (cu a(1) = 1, a(2) = 1, a(3) = 1):

1, 1, 1, 3, 5, 9, 17, 31, ...

#include <iostream>
using namespace std;

int main()
{
    int n;
    cin >> n;

    int a = 1, b = 1, c = 1;

    if (n >= 1) cout << a << " ";
    if (n >= 2) cout << b << " ";
    if (n >= 3) cout << c << " ";

    for (int i = 4; i <= n; i++) {
        int d = a + b + c;
        cout << d << " ";
        a = b;
        b = c;
        c = d;
    }

    return 0;
}

Input:
8

Output:
1 1 1 3 5 9 17 31

Cum funcționează deplasarea la 3 termeni?

La fiecare pas, avem trei variabile a, b, c (cele mai recente trei valori).

Calculăm d = a + b + c, apoi: - a devine b (cel mai vechi dispare) - b devine c - c devine d (noul termen)

Este aceeași idee ca la Fibonacci, dar cu o variabilă în plus.

Schema generală a unui șir recurent

1. Inițializăm primii termeni
2. Într-o buclă:
   a. Calculăm noul termen din cei anteriori
   b. Actualizăm variabilele (deplasare)
   c. Afișăm sau prelucrăm noul termen

Greșeli frecvente

1. Ordinea greșită a deplasării

La Fibonacci, ordinea contează:

// GREȘIT:
b = c;
a = b; // acum a = c, nu b-ul vechi!

// CORECT:
a = b;
b = c;

Prima linie trebuie să fie a = b, apoi b = c. Altfel pierdem valoarea lui b.

2. Bucla pornește de la 1 în loc de 3

Dacă am afișat deja primii doi termeni, bucla trebuie să pornească de la i = 3:

cout << a << " " << b << " ";
for (int i = 3; i <= n; i++) { // NU de la 1!

3. Depășire pentru termeni mari

Fibonacci crește exponențial. F(47) = 2971215073 depășește int.

Folosește long long dacă n poate fi mare.

4. Cazurile `n = 1` și `n = 2`

Bucla for (int i = 3; i <= n; ...) nu se execută dacă n < 3. Trebuie tratat separat afișarea primilor termeni.

Ce să reții

Un șir recurent calculează fiecare termen din termenii anteriori.
Fibonacci: F(n) = F(n-1) + F(n-2), cu F(1) = F(2) = 1.
Folosim două (sau mai multe) variabile pentru a reține ultimii termeni.
La fiecare pas facem o deplasare: actualizăm variabilele în ordinea corectă.
Schema funcționează pentru orice regulă recurentă, nu doar Fibonacci.
Atenție la ordinea deplasării și la cazurile n = 1, n = 2.