04/11/23 E. Giovannetti -- OI09. 1

Olimpiadi di Informatica 2010Giornate preparatorie

Dipartimento di InformaticaUniversità di Torino

marzo 2010

13 – Programmazione dinamica: i numeri di Fibonacci.

(versione 11/04/23)

11/04/23 19:56 E. Giovannetti - AlgELab-09-10 - Lez.28 2

I numeri rossi sulla Mole Antonelliana a Natale

Che numeri sono ?

11/04/23 19:56 E. Giovannetti - AlgELab-09-10 - Lez.28 3

I conigli di Leonardo di Pisa, figlio di Bonaccio.

Leonardo Pisano, o Leonardo Fi(lius)bonacci

•all'istante 0, nessun coniglio: 0 coppie;•alla fine del 1o anno, compra 1 coppia di coniglietti;•alla fine del 2o anno:i coniglietti sono diventati conigli adulti: 1 coppia

•alla fine del 3o anno:la coppia adulta genera una coppia di coniglietti: 2 coppie

•alla fine del 4o anno: la coppia adulta genera una coppia di coniglietti: 3 coppie;

i coniglietti dell'anno prima sono diventati adulti;•alla fine del 5o anno: le 2 coppie adulte generano ciascuna una coppia di coniglietti: 3+2 = 5 coppie;

...

11/04/23 19:56 E. Giovannetti - AlgELab-09-10 - Lez.28 4

Le regole della riproduzione dei conigli.

•Nessun coniglio muore mai (i conigli sono immortali).

•I conigli diventano adulti (e cominciano a riprodursi) soltanto al secondo anno di vita.

•Ogni coppia adulta genera 1 coppia di coniglietti all'anno, per sempre.

11/04/23 19:56 E. Giovannetti - AlgELab-09-10 - Lez.28 5

(continua)

Allora, dopo n anni:num. di coppie = num. di coppie esistenti 1 anno prima + num. di nuove coppie generate;ma:num. di nuove coppie = num. di coppie adulte 1 anno prima =

= num. di coppie esistenti 2 anni prima

quindi:num. di coppie = num. di coppie esistenti 1 anno prima + num. di coppie esistenti 2 anni prima.

11/04/23 19:56 E. Giovannetti - AlgELab-09-10 - Lez.28 6

L'albero dei conigli

La riproduzione dei conigli può essere descritta dall'albero seguente:

11/04/23 19:56 E. Giovannetti - AlgELab-09-10 - Lez.28 7

I numeri rossi sulla Mole Antonelliana

fib 0 = 01 12 13 24 35 56 87 138 219 34

10 5511 8912 14413 233... ...

fib(0) = 0fib(1) = 1fib(n) = fib(n-1) + fib(n-2)

11/04/23 19:56 E. Giovannetti - AlgELab-09-10 - Lez.28 8

L'n-esimo numero di Fibonacci: algoritmo ricorsivo

long fib(int n) { if(n == 0) return 0; else if(n == 1) return 1; else return fib(n-1) + fib(n-2);}

Tempo di calcolo: cresce esponenzialmente con n !La funzione ricalcola molte volte gli stessi valori !

11/04/23 19:56 E. Giovannetti - AlgELab-09-10 - Lez.28 9

Rappresentazione grafica delle eq. di ricorrenza(albero di ricorsione)

+

fib(n-1) fib(n-2)

fib(n) =

fib(1) 1=

11/04/23 19:56 E. Giovannetti - AlgELab-09-10 - Lez.28 10

+fib(n) =

+

fib(n-2) fib(n-3)

+

fib(n-3) fib(n-4)

liv. 0

liv. 1

11/04/23 19:56 E. Giovannetti - AlgELab-09-10 - Lez.28 11

+fib(n) =

+

+

fib(n-3) fib(n-4)

+

fib(n-4) fib(n-5)

+

+

fib(n-4) fib(n-5)

+

fib(n-5) fib(n-6)

liv. 0

liv. 1

liv. 2

liv. 3

eccetera

Ricorsione con memorizzazione.

Memorizziamo i risultati delle chiamate ricorsive, e non ricalcoliamo i valori già calcolati in una chiamata precedente:int* ris;

long fib(int n) { if(n == 0) return 0; if(n == 1) return 1; if(ris[n] == 0) ris[n] = fib(n-1) + fib(n-2); return ris[n];}

long fibmemo(int n) { ris = new int[n+1]; //for(int i = 0; i <= n; i++) ris[i] = 0; return fib(n);}

11/04/23 19:56 E. Giovannetti - AlgELab-09-10 - Lez.28 12

Iterazione

•Si può sostituire la ricorsione con l’iterazione; inoltre è sufficiente tenere solo i due ultimi numeri calcolati.

•L’algoritmo che così si ottiene è in realtà l’algoritmo che si ottiene direttamente pensando al modo in cui effettuiamo il calcolo noi esseri umani.

11/04/23 19:56 E. Giovannetti - AlgELab-09-10 - Lez.28 13

11/04/23 19:56 E. Giovannetti - AlgELab-09-10 - Lez.28 14

L'algoritmo intuitivo

•Infatti, se calcoliamo a mano la sequenza di Fibonacci, usiamo un ovvio algoritmo lineare: sommiamo i due ultimi numeri ottenuti, e otteniamo un nuovo ultimo numero della sequenza, ma non buttiamo via il precedente; invece ...

•... la procedura ricorsiva, per calcolare fib(n-2) + fib(n-1) calcola due volte fib(n-2), a sua volta per calcolare fib(n-2) calcola due volte fib(n-4) ... ripete inutilmente i calcoli !

•Proviamo a implementare l'algoritmo "manuale" intuitivo per mezzo di una procedura iterativa.

11/04/23 19:56 E. Giovannetti - AlgELab-09-10 - Lez.28 15

L'n-esimo numero di Fibonacci: algoritmo iterativo.

•Per calcolare l'n-esimo numero occorre aver calcolato tutti i precedenti, e ad ogni passo si usano gli ultimi due.

•Servono allora tre variabili: i, ultimo, penult

INVARIANTEultimo è l'i-esimo numero di Fibonacci;

penult è l'(i-1)-esimo numero di Fibonacci.

CORPO DEL CICLO ultimo + penult diventa il nuovo ultimo, il vecchio ultimo diventa il nuovo penult: nuovoUltimo = ultimo + penult;penult = ultimo;ultimo = nuovoUltimo;i++;

11/04/23 19:56 E. Giovannetti - AlgELab-09-10 - Lez.28 16

Test del ciclo•Si esce quando i = n: in tal caso, evidentemente, ultimo è l'n-esimo numero di Fibonacci; quindi:

while(i < n)

Inizializzazione0 è lo 0-esimo numero di Fibonacci;1 è ... l'1-esimo numero di Fibonacci;Allora, ricordando l'invariante:ultimo è l'i-esimo numero di Fibonacci,

penult è l'(i-1)-esimo numero di Fibonacci,si vede che l'inizializzazione deve essere:

i = 1;penult = 0;ultimo = 1;

11/04/23 19:56 E. Giovannetti - AlgELab-09-10 - Lez.28 17

La procedura completa

long fibonacci(int n) { long penult = 0; long ultimo = 1; if(n <= 0) return 0; for(int i = 1; i < n; i++) { long nuovoUltimo = ultimo + penult; penult = ultimo; ultimo = nuovoUltimo; } return ultimo;}osserva che vecchio ultimo è uguale a nuovoUltimo - penult quindi si potrebbe scrivere:long nuovoUltimo = ultimo + penult;penult = nuovoUltimo – penult;ultimo = nuovoUltimo;

11/04/23 19:56 E. Giovannetti - AlgELab-09-10 - Lez.28 18

La procedura completa

static long fibonacci(int n) { long penult = 0; long ultimo = 1; if(n <= 0) return 0; for(int i = 1; i < n; i++) { long nuovoUltimo = ultimo + penult; penult = ultimo; ultimo = nuovoUltimo; } return ultimo;}osserva che vecchio ultimo è uguale a nuovoUltimo - penult quindi si potrebbe scrivere:long nuovoultimo = ultimo + penult;penult = nuovoultimo – penult;ultimo = nuovoUltimo;

11/04/23 19:56 E. Giovannetti - AlgELab-09-10 - Lez.28 19

L'n-esimo numero di Fibonacci: algoritmo iterativo.

Versione finale.

static long fibonacci(int n) { long penult = 0; long ultimo = 1; if(n <= 0) return 0; for(int i = 1; i < n; i++) { ultimo = ultimo + penult; penult = ultimo - penult;// = vecchio ultimo } return ultimo;}

11/04/23 19:56 E. Giovannetti - AlgELab-09-10 - Lez.28 20

La sequenza di Fibonacci: versione finale.

Naturalmente se, come nel caso della Mole Antonelliana, vogliamo in output non solo l'n-esimo numero, ma l'intera sequenza dei primi n numeri di Fibonacci, non calcoliamo separatamente ogni numero ! PRECOND: n > 1 static long[] sequenzaDiFib(int n) {// sequenza degli n+1 numeri di Fibonacci da fib(0) a fib(n) n++; long[] a = new long[n]; a[0] = 0; a[1] = 1; for(int i = 2; i < n; i++) a[i] = a[i-1] + a[i-2]; return a; }

11/04/23 19:56 E. Giovannetti - AlgELab-09-10 - Lez.28 21

Numeri di Fibonacci arbitrariamente grandi

Per superare la limitazione della dimensione fissa del tipo long, si può usare la classe BigInteger che permette di trattare interi di grandezza arbitraria (vedi docum. Java):

static BigInteger bigFibonacci(int n) { BigInteger penult = ZERO; BigInteger ultimo = ONE; if(n <= 0) return ZERO; for(int i = 2; i <= n; i++) { ultimo = ultimo.add(penult); penult = ultimo.subtract(penult); } return ultimo; }

11/04/23 19:56 E. Giovannetti - AlgELab-09-10 - Lez.28 22

Esercizio

Si scriva una versione della procedura sequenzaDiFib che restituisca un array di BigInteger.

11/04/23 19:56 E. Giovannetti - AlgELab-09-10 - Lez.28 23

Osservazione

•Ciò vuol dire che la versione ricorsiva di un algoritmo può avere complessità asintoticamente peggiore della versione iterativa ?

•NO ! Nonostante le apparenze, l'algoritmo ricorsivo è un algoritmo DIVERSO da quello iterativo.

•Il fatto è che l'algoritmo ricorsivo PIÙ NATURALE è esponenziale.