O implementare directa a relatiei de recurenta ar trebui sa obtina 20 de puncte si se gaseste 'aici':/job_detail/372678?action=view-source.

Pentru a obtine 100 de puncte trebuie gasita o metoda mai eficienta de a rezolva aceasta recurenta. Ne vom folosi de 'inmultirea matricilor':http://en.wikipedia.org/wiki/Matrix_multiplication#Ordinary_matrix_product in felul urmator: la pasul $K$ o sa avem deja calculate $F{~K - 2~}$ si $F{~K - 1~}$ si vrem sa il aflam pe $F{~K~}$. 'Solutia':/job_detail/372680?action=view-source foloseste 'ridicarea la putere in timp logaritmic':/problema/lgput.
 

Pentru a obtine 100 de puncte trebuie gasita o metoda mai eficienta de a rezolva aceasta recurenta. Ne vom folosi de 'inmultirea matricilor':http://en.wikipedia.org/wiki/Matrix_multiplication#Ordinary_matrix_product in felul urmator: la pasul $K$ o sa avem deja calculate $F{~K - 2~}$ si $F{~K - 1~}$ si vrem sa il aflam pe $F{~K~}$.

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

\[ \left( \begin{array}{ccc}
F_K - 1_ & F_K_ \end{array} \right)\] </tex>

Vom nota cu $M{~i~}$ matricea <tex>
\emph{}
\[ \left( \begin{array}{ccc}
F_i - 1_ & F_i - 1_ \end{array} \right)\] </tex> si cu $Z$ matricea constanta, <tex> \emph{}
\[ \left( \begin{array}{ccc}
0 & 1 \\
1 & 1 \end{array} \right)\] </tex>.
 
'Solutia':/job_detail/372680?action=view-source foloseste 'ridicarea la putere in timp logaritmic':/problema/lgput.
 

== include(page="template/taskfooter" task_id="kfib") ==