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~}$.

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.

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

F_K - 2_ & F_K - 1_ \end{array} \right)\]\times </tex>  <tex>

F_K - 2_ & F_K - 1_ \end{array} \right)\] & \times </tex>  <tex>

\emph{}
\[ \left( \begin{array}{ccc}
0 & 1 \\

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

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

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