Serie di Fibonacci

Come primo (classico) esempio, utilizziamo la serie di Fibonacci $f(n)$, che è definita, per un numero naturale $n$, nel seguente modo

$$\begin{eqnarray*} f(0)&=&1 \\ f(1)&=&1 \\ f(n)&=&f(n-1)+f(n-2) \end{eqnarray*}$$

Un semplice modo di implementare il calcolo della serie è riportato in Figura . Purtroppo si può dimostrare che la funzione richiamata due volte (#(1)), non fa calcoli indipendenti, e infatti si ottiene un tempo di esecuzione esponenziale. Per esempio per calcolare $f(5)$ utilizzando fibo1 di Figura , abbiamo bisogno di calcolare più volte la stessa funzione

$$\begin{eqnarray*} f(5)&=&f(4)+f(3) \\ f(5)&=&[f(3)+f(2)]+[f(2)+f(1)] \\ f(5)&=... ...] \\ f(5)&=&[[[f(1)+f(0)]+f(1)]+[f(1)+f(0)]]+[[f(1)+f(0)]+f(1)] \end{eqnarray*}$$

Figura: Calcolo della serie di Fibonacci

Per evitare di ricalcolare più volte la medesima funzione, si può utilizzare la programmazione dinamica. In questo caso, bisogna tabulare le soluzioni parziali, ed utilizzarle quando se ne ha la necessità. Nel nostro caso bisogna introdurre un vettore f[] con un numero di elementi pari $n+1$ (in quanto abbiamo anche lo 0), che mantenga i risultati parziali. L'algoritmo risultante è dato in Figura . Possiamo a questo punto valutare il numero di chiamate che i due differenti algoritmi operano al variare del numero $n$. In Tabella si mostra come nel caso dell'utilizzo della DP il numero di chiamate (il che implica il tempo impiegato) sia lineare e non esponenziale come avviene per la funzione semplice fibo1.

Questo primo esempio mostra quindi che se la soluzione del problema generale si può scomporre nella composizione di problemi parziali non indipendenti, si ha bisogno della tabulazione dei risultati parziali per poter ridurre il tempo di esecuzione.

    

Tabella: Contronto tra fibo1() e fibo2()

Numero $n$	Numero di chiamate	Numero di chiamate
da calcolare	di fibo1	di fibo2
5	15	12
10	177	22
20	21891	42
30	2692537	62

Figura: Calcolo della serie di Fibonacci con DP