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,
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
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