Cunoaștem deja ce este acela Șirul lui Fibonacci, șir de numere descoperit de matematicianul Leonardo Pisano, unde fiecare element se definește în funcție de suma ultimilor doi. Astfel,

Formal, se consideră că există și al 0-lea termen al șirului, cu valoarea 0:

Există multe aplicații, în special în probleme de olimpiadă sau de concursuri, unde trebuie să determinăm eficient al n-lea termen al șirului. Metoda descrisă pentru clasa a IX-a, pe care am discutat-o în acest articol, generează brut toți termenii de dinainte pentru a putea găsi cel de-al n-lea termen, însă asta înseamnă că algoritmul brut face n pași și are astfel complexitatea O(n).

Din fericire însă, utilizând ridicarea la putere în timp logaritmic pe matrice, există o metodă de găsire a celui de-al n-lea termen din șirul Fibonacci cu complexitatea O(log n) (logaritmică). Deși înmulțirea matricelor se învață în clasa a XI-a la matematică, noțiunile discutate aici sunt foarte ușor de înțeles pentru orice clasă.

Metodă eficientă: matrice Fibonacci

Considerăm matricea (de la matematică) următoare:

Am înlocuit valorile de 0 și de 1 cu termeni din șirul lui Fibonacci. Să vedem ce se întâmplă în continuare atunci când ridicăm matricea la puterea a 2-a:

Vedem că matricea M2 conține termenii F1, F2 și F3. Vedem că M3 o să conțină termenii F2, F3 și F4:

Prin urmare, găsim că, ridicând matricea noastră M la puterea n, generăm matricea:

Matricea aceasta are pe a doua coloană a primei linii (și pe prima coloană a celei de-a doua linii) elementul Fn, pe care ni l-am dorit să îl generăm. Totodată, cum înmulțirea matricelor se poate realiza logaritmic, putem să adaptăm algoritmul și să generăm în O(log n) matricea noastră.

Al n-lea termen Fibonacci în timp logaritmic în C++

Atenție: termenii șirului Fibonacci ies foarte rapid din tipurile de date int și long long. De aceea, problemele care cer calcularea celui de-al n-lea termen Fibonacci de obicei cer modulo un număr prim, precum 666013 sau 1.000.000.007. În secvența de mai jos, am calculat termenii modulo 666013.

#include <iostream>

using namespace std;

int m[2][2], rasp[2][2], n;

//Functie care inmulteste matricea a cu b, punand rezultatul in a
void inmultireMatrice(int a[][2], int b[][2]) {
    int aa[2][2]; //Copie a lui a
    aa[0][0] = a[0][0]; aa[0][1] = a[0][1];
    aa[1][0] = a[1][0]; aa[1][1] = a[1][1];

    int bb[2][2]; //Copie a lui b
    bb[0][0] = b[0][0]; bb[0][1] = b[0][1];
    bb[1][0] = b[1][0]; bb[1][1] = b[1][1];

    a[0][0] = ((long long)aa[0][0] * bb[0][0] + aa[0][1] * bb[1][0]) % 666013;
    a[0][1] = ((long long)aa[0][0] * bb[0][1] + aa[0][1] * bb[1][1]) % 666013;
    a[1][0] = ((long long)aa[1][0] * bb[0][0] + aa[1][1] * bb[1][0]) % 666013;
    a[1][1] = ((long long)aa[1][0] * bb[0][1] + aa[1][1] * bb[1][1]) % 666013;
}

void ridicare(int n) {
    while(n > 0) {
        if(n % 2 == 1)
            inmultireMatrice(rasp, m);
        inmultireMatrice(m, m);
        n /= 2;
    }
}

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

    //Matricea initiala
    m[0][0] = 1; m[0][1] = 1;
    m[1][0] = 1; m[1][1] = 0;

    //Matricea raspuns (initial este egala cu I2)
    rasp[0][0] = 1; rasp[0][1] = 0;
    rasp[1][0] = 0; rasp[1][1] = 1;

    //Ridicam matricea la puterea n
    ridicare(n);

    //Afisam cel de-al n-lea termen Fibonacci
    cout << rasp[0][1];
    return 0;
}

Bibliografie și alte resurse

• Ridicare la putere în timp logaritmic C++
• Fibonacci Q-Matrix (Wolfram MathWorld)
• Al k-lea termen Fibonacci (InfoArena)
• Șirul lui Fibonacci în C++
• Matrice Fibonacci (PbInfo)