O implementare directă a relaţiei de recurenţă în complexitate liniară ar trebui să obţină $20$ de puncte şi se găseşte 'aici':/job_detail/372678?action=view-source.

Pentru a obţine $100$ de puncte trebuie găsită o metoda mai eficientă de a rezolva această recurenţă. Ne vom folosi de 'înmulţirea matricilor':http://en.wikipedia.org/wiki/Matrix_multiplication#Ordinary_matrix_product în felul următor: la pasul $n$ vom avea deja calculate <tex> F_{n-2} </tex> şi <tex> F_{n-1} </tex> şi vrem să îl aflăm pe <tex> F_{n} </tex>:

Pentru a obţine $100$ de puncte trebuie găsită o metoda mai eficientă de a rezolva această recurenţă. Ne vom folosi de 'înmulţirea matricilor':http://en.wikipedia.org/wiki/Matrix_multiplication#Ordinary_matrix_product în felul următor: la pasul <tex> n </tex> vom avea deja calculate <tex> F_{n-2} </tex> şi <tex> F_{n-1} </tex> şi vrem să îl aflăm pe <tex> F_{n} </tex>:

<tex>
\emph{}
\[\left( \begin{array}{ccc}

0 & 1 \\
1 & 1 \end{array} \right)\] </tex>.

Stim ca $M{~i~}$ este egal cu $Z$ * $M{~i-1~}$ si mai stim ca $M{~i-1~}$ este egal cu $Z * M{~i-2~}$. Din proprietatea de asociativitate a inmultirii matricilor rezulta ca $M{~i~}$ este egal cu $Z^2^ * M{~i-2~}$. Inductiv rezulta ca $M{~i~}$ = $Z^N-1^$ * $M{~1~}$. 'Soluţia':/job_detail/372680?action=view-source optima se foloseşte de 'ridicarea la putere în timp logaritmic':/problema/lgput, avand complexitatea finala de $O(log K * CONST)$. $CONST$ este numarul de operatii efectuate la fiecare pas al ridicarii la putere si este egal cu dimensiunea matricii constante la puterea a $3$-a, adica $8$.

Stim ca <tex>M_{i}</tex> este egal cu <tex>Z \times M_{i-1}</tex> si mai stim ca <tex>M_{i-1}</tex> este egal cu <tex>Z /times M_{i-2}</tex>. Din proprietatea de asociativitate a inmultirii matricilor rezulta ca $M{~i~}$ este egal cu $Z^2^ * M{~i-2~}$. Inductiv rezulta ca $M{~i~}$ = $Z^N-1^$ * $M{~1~}$. 'Soluţia':/job_detail/372680?action=view-source optima se foloseşte de 'ridicarea la putere în timp logaritmic':/problema/lgput, avand complexitatea finala de $O(log K * CONST)$. $CONST$ este numarul de operatii efectuate la fiecare pas al ridicarii la putere si este egal cu dimensiunea matricii constante la puterea a $3$-a, adica $8$.

h2. Aplicaţii