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

Fie 'şirul lui Fibonacci':http://en.wikipedia.org/wiki/Fibonacci_number, dat prin <tex> F_{1} = 1, F_{2} = 1, \ldots, F_{n} = F_{n-1} + F_{n-2} </tex>.

Fie 'şirul lui Fibonacci':http://en.wikipedia.org/wiki/Fibonacci_number, dat prin <tex> F_{0} = 0, F_{1} = 1, \ldots, F_{n} = F_{n-1} + F_{n-2} </tex>.

h2. Cerinţă

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

Pentru a obţine $100$ de puncte trebuie găsită o metodă eficientă de a rezolva această recurenţă. Ne vom folosi de 'înmulţirea matricelor':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 vom dori să îl aflăm pe <tex> F_{n} </tex>:

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

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

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

\emph{}
\[ \left( \begin{array}{ccc}
0 & 1 \\
1 & 1 \end{array} \right)\] =  \emph{}
\[ \left( \begin{array}{ccc}

F_n-1_ & F_n_ \end{array} \right)\] </tex>

F_{n-1}_ & F_n_ \end{array} \right)\] </tex>

Vom nota cu $M{~i~}$ matricea <tex>

Vom nota cu <tex> M_{i} </tex> matricea <tex>

\emph{}
\[ \left( \begin{array}{ccc}

F_i-1_ & F_i_ \end{array} \right)\] </tex> iar cu $Z$ matricea constantă, <tex> \emph{}

F_{i-1}_ & F_i_ \end{array} \right)\] </tex> iar cu <tex> Z </tex> matricea constantă <tex> \emph{}

\[ \left( \begin{array}{ccc}
0 & 1 \\
1 & 1 \end{array} \right)\] </tex>.

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 <tex>M_{i}</tex> este egal cu <tex>Z^2 \times M_{i-2}</tex>. Inductiv rezulta ca <tex>M_{i}</tex> = <tex>Z^{N-1} \times M_{1}</tex>. '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 <tex>O(log K \times const)</tex>. <tex>const</tex> este numarul de operatii efectuate la fiecare pas al ridicarii la putere si este egal cu dimensiunea matricii constante la puterea a <tex>3</tex>-a, adica <tex>8</tex>.
 

Ştim că <tex>M_{i} = Z \times M_{i-1}</tex> şi mai ştim că <tex>M_{i-1} = Z \times M_{i-2}</tex>. Din proprietatea de asociativitate a înmulţirii matricelor rezultă că <tex>M_{i} = Z^2 \times M_{i-2}</tex>. Inductiv, rezultă egalitatea <tex>M_{i}</tex> = <tex>Z^{i-1} \times M_{1}</tex>. 'Soluţia':/job_detail/372680?action=view-source optimă se foloseşte de 'ridicarea la putere în timp logaritmic':/problema/lgput, având complexitatea <tex>O(log K)</tex>. Constanta ce se ascunde în spatele acestei complexităţi este egală cu numărul de operaţii efectuate la fiecare pas al ridicării la putere, adică cu dimensiunea matricii constante <tex> Z </tex> la puterea a <tex>3</tex>-a, care este <tex>8</tex>.

h2. Aplicaţii

# 'Iepuri':problema/iepuri
# 'Hprob':problema/hprob
# "Nice Patterns Strike Back":http://acm.sgu.ru/problem.php?contest=0&problem=197, _SGU_
# "Tour Counting":http://www.topcoder.com/stat?c=problem_statement&pm=6386, _Topcoder_
# 'Ecu':problema/ecu
# 'Pkinv':problema/pkinv
# 'Recurenta2':problema/recurenta2
# 'Nr2':problema/nr2

* 'Iepuri':problema/iepuri
* 'Hprob':problema/hprob
* 'Ecu':problema/ecu
* 'Pkinv':problema/pkinv
* 'Recurenta2':problema/recurenta2
* 'Nr2':problema/nr2
* "Nice Patterns Strike Back":http://acm.sgu.ru/problem.php?contest=0&problem=197, _SGU_
* "Tour Counting":http://www.topcoder.com/stat?c=problem_statement&pm=6386, _Topcoder_

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