Fibonacci non ricorsiva???? :?

[italyanker]

Salve a tutti...

Volevo chiedere se qualcuno mi potrebbe aiutare a implementare sta funzione fibonacci in modo non ricorsivo!...

Io non sto capendo come devo fare...Eppure la versione ricorsiva di una funzione non ricorsiva l'avev capita alquanto bene...Ma adesso???

Che qualcuno mi aiuta a costruire sta Fibonacci(n) ??

Sono confuso! :?

[Awema]

invece di usare funzioni ricorsive si possono utilizzare i vettori, dovrebbe essere così:

c[1] = c[2] = 1;

for(i = 3; i <= n; i++)

c = c[i - 1] + c[i - 2];

return (c[n])

la complessità di questo algoritmo è O(n)

[Awema]

allora com'è andata??

va bene??

[italyanker]

Insomma...

Avrei preferito farlo senza vettori!...

Nessuno conosce un modo per farlo senza vettori???

:?

[ghepX]

Ciao,

da quello che ho capito tu cercavi una algoritmo di fibonacci inplace senza vettori giusto?

fib(N)

prec1 =1

prec2=2

for i=3 tu n do

fb= prec1+prec2

prec1=prec2

prec2=fb

return fb

ho fatto delle prove velocemente e sembra funzionare ... cmq la complessità dimane O(n) e per trovare la complessità giusta non devi fare altro che risolvere la serie che va da 3 ad n di 1 se ipotizzi come operazione costosa solo l'operazione di somma tra interi!

Ciao e fammi sapere se eraquesta la soluzione ch cercavi!

[ghepX]

scusa ma dalla fretta hos scritto tu invece che to

scusa

Ciaoz

[Awema]

ottimo, è molto più semplice, come ho fatto a non pensarci

[italyanker]

carino l'algortmo! :wink: