Matrice Fibonacci - al n-lea termen Fibonacci în timp logaritmic

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,

Ecuatie

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

Ecuatie

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:

Ecuatie

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:

Ecuatie

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

Ecuatie

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

Ecuatie

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

DS

Autorul acestei lecții

Dominic Satnoianu

Această lecție a fost redactată de către Dominic Satnoianu.

© 2021 – 2025 Aspire Education Labs SRL. Toate drepturile rezervate.

Așa cum este specificat și în termeni și condiții, conținutul acestei pagini este protejat de legea drepturilor de autor și este interzisă copierea sau modificarea acestuia fără acordul scris al autorilor.

Încălcarea drepturilor de autor este o infracțiune și se pedepsește conform legii.

Comentarii 0

Autentifică-te pentru a putea comenta.

Autentifică-te