$$ F_n = \begin{cases}
1& \text{dacă } n = 1 \text{ sau } n = 2 ,\\
F_{n-1} + F_{n-2} & \text{dacă } n > 2.
\end{cases} $$
Pentru a determina al n-termen a șirului putem folosi diverse metode. Acest articol prezintă un algoritm de complexitate \(O(n)\) care determină al n-lea termen.
Prezentul articol prezintă un algoritm de complexitate logaritmică, bazat pe înmulțirea rapidă a matricelor.
Matrice Fibonacci
Considerăm următoarea matrice: \( Q = \left( \begin{matrix} 1& 1\\ 1& 0\end{matrix} \right) \). Dacă extindem șirul lui Fibonacii cu încă un element, \( F_0 = 0 \), observăm că: \( Q = \left( \begin{matrix} F_2& F_1\\ F_1& F_0\end{matrix} \right) \). Să calculăm \(Q^2\) și \(Q^3\):
Pentru a determina \(F_n\), considerăm matricea \( Q = \left( \begin{matrix} 1& 1\\ 1& 0\end{matrix} \right) \), pe care o ridicăm la puterea n. Pentru a efectua repede calculele, folosim exponențierea rapidă.
Problema #Fibonacci2 cere determinarea celui de-al n-lea termen al șirului lui Fibonacii, modulo 666013. Succes!
Leonardo Pisano Bogollo, (c. 1170 – c. 1250) cunoscut și sub numele de Leonardo din Pisa, Leonardo Pisano, Leonardo Bonacci, Leonardo Fibonacci, sau pur și simplu Fibonacci, a fost un matematician italian considerat de unii drept “cel mai talentat matematician din Occidentul Evului Mediu”.
Fibonacci este cel mai bine cunoscut lumii moderne pentru:
Răspândirea sistemului de numărare hindu-arab în Europa, prin publicarea în primul rând la începutul secolului al 13-lea a cărții sale denumită Cartea de calcul , sau Liber Abaci.
Un șir de numere, care i-a purtat ulterior numele, și anume șirul lui Fibonacci, pe care el nu l-a descoperit, dar pe care l-a folosit ca un exemplu în cartea sa, Liber Abaci.
Șirul lui Fibonacci
Numerele Fibonacci sunt numere naturale care fac parte din următorul șir, în care fiecare număr este egal cu suma celor două de dinainte:
1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, …
Uneori, șirul este extins cu încă un termen, la început:
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, …
Termenul Fn este calculat prin următoarea relație de recurență:
Fn = Fn-1 + Fn-2
cu valorile inițiale F1=1, F2=1 sau F0=0 și F1=1.
Algoritm
Cum determinăm primii N termeni din șirul lui Fibonacci? Vom folosi trei variabile simple a b c. Două dintre ele vor reprezenta termenii anteriori Fn-1 și Fn-2, iar a treia va reprezenta termenul curent Fn:
a ← 1
b ← 1
scrie a, b
pentru i ← 3,n execută
c ← a + b
scrie c
a ← b
b ← c
sfarsit_pentru
Proprietăți
Câteva proprietăți aritmetice interesante ale numerelor Fibonacci:
Candale Silviu (silviu) 
