h2. Indicaţii de rezolvare

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/382677?action=view-source.

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/382677?action=view-source.

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