Vreau 2 rezolvari la urmatoarea problema:
Vrem sa urcam o scara cu N trepte. Ptr asta putem sari de pe o treapta pe alta (adica luam treptele la rand) sau putem sari fix o treapta (adica luam a 2-a treapta sarim una doar). Vreau sa stiu in cate moduri pot ajunge la destinatie (sa urc cele N trepte). Ca sa fie clar pot sa urc daca N=20 : 1 2 2 1 1 2 2 1 2 1 1 1 1 2. Deci ma pot decide in orice moment sa schimb tactica sau sa revin la vechea tactica. (1<=N<=1000000)
Cine vrea ar tb sa faca si un program sau doua cu cele 2 solutii
Problema poate fi exprimata printr-o recurenta fibonacci:
n(i) = n(i – 1) + n(i – 2), unde n(i) semnifica numarul de moduri in care se pot urca i trepte.
O poti rezolva eficient prin programare dinamica, dezvoltand recurenta in mod bottom up … sau ineficient, scriind direct o solutie recursiva.
Asta ar fi o rezolvare. O vreau si pe cea de-a doua. Pana la urma la ce complexitate ajungi lucrand optim? sau sa pun altfel intrebarea avem un 0<=N<=1.000.000.000. Imi intra in 0.001 sec rezolvarea dumitale cu 260 kbyts disponibili de memorie? Daca da fii bun si scrie si codul poate o sa foloseasca cuiva care o sa vrea sa implementeze aceasta problema eficient!
Complexitatea este O(n). In termeni de spatiu ocupat, este O(1).
Daca se incadreaza in nu stiu cate secunde si nu stiu cati kB poti testa.
O implementare recursiva, extrem de lenta, de complexitate O(2^n) (a nu se folosi in practica):
Fara suparare. Am modificat ptr implementare N-ul cu 1 miliard si nu a intrat in timp (nici cu 1 milion nu intra). 1 milion ->0.004 sec si 1 miliard ->3.384 sec. Cu memoria stati foarte bine. Eu am folosit un alt algoritm de calculare a rezultatului. Ceva gen cu constanta 8. E mai laborioasa rezolvarea, mancatoare si de memorie mai multa dar e mai eficienta zic eu! Ma mai gandeam si la alta rezolvare nu stiu daca e mai rapida ca asta e in aceeasi complexitate dar cu constanta 4 (ceva cu sectiunea de aur). Oricum rezolvarea pe ansamblu e buna!
Daca vrei ceva mai rapid dar si mai complicat, poti implementa algoritmul „fast doubling” descris pe pagina:
No comment!!! Link-ul e f edificator nici nu stiam ca exista asha ceva. Ms mult. Astept cu interes si a doua rezolvare + implementare! ca am zis ca vreau 2 rezolvari nu una!