h1. 'Fibsmen':problema/fibsmen

Orice numar natural se poate scrie in mod unic ca suma de termeni Fibonacci neconsecutivi. Aceasta scriere se poate obtine in mod greedy (alegem tot timpul cel mai mare numar Fibonacci mai mic sau egal decat numarul curent) in O(k) unde k e numarul de numere Fibonacci mai mici decat N (in cazul nostru, k e maxim 78).
 
Urmatoarea observatie este ca daca ordonam termenii unei sume de numere Fibonacci distincte, putem grupa termeni consecutivi astfel incat sa creeze exact scrierea unica a lui N cu termeni neconsecutivi (e.g. 73 = (2 + 3) + (13) + (21 + 34) = 5 + 13 + 55), ceea ce inseamna ca putem construi solutia inductiv, parcurgand scrierea unica si calculand la fiecare pas:
A = numarul de scrieri al sumei de pana acum care contin termenul Fibonacci curent
B = numarul de scrieri al sumei de pana acum care NU contin termenul Fibonacci curent
 
Pentru a calcula, vom mai avea nevoie de faptul ca pt M<N, Fib(N) poate fi scris ca suma de numere Fibonacci intre Fib(M) si Fib(N-1) (inclusiv) in exact (N-M)/2 moduri (notam cu d[N][M]).
 
Astfel, cand trecem de la un pas la urmatorul, noul A va fi A+B (deoarece putem adauga termenul Fibonacci  curent la oricare din sumele precedente fara a altera unicitatea), iar noul B va fi A*d[curent][precedent+1] + B*d[curent][precedent] (deoarece A dintre sume deja contin Fib(precedent)). Rezultatul final va fi A+B (cu A si B de la ultimul pas).
 

==include(page="template/monthly-2014/footer")==