Olimpiadi di Informatica 2010
Giornate preparatorie
Dipartimento di Informatica
Università di Torino
marzo 2010
13 – Programmazione dinamica:
i numeri di Fibonacci.
(versione 19/12/2015)
12/19/2015
E. Giovannetti -- OI09.
1
I numeri rossi sulla Mole Antonelliana a Natale
Che numeri sono ?
19/12/2015 10:16
E. Giovannetti - AlgELab-09-10 - Lez.28
2
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;
...
19/12/2015 10:16
E. Giovannetti - AlgELab-09-10 - Lez.28
3
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.
19/12/2015 10:16
E. Giovannetti - AlgELab-09-10 - Lez.28
4
(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.
19/12/2015 10:16
E. Giovannetti - AlgELab-09-10 - Lez.28
5
L'albero dei conigli
La riproduzione dei conigli può essere descritta
dall'albero seguente:
19/12/2015 10:16
E. Giovannetti - AlgELab-09-10 - Lez.28
6
I numeri rossi sulla Mole Antonelliana
fib(0) = 0
fib(1) = 1
fib(n) = fib(n-1) + fib(n-2)
19/12/2015 10:16
fib 0
1
2
3
4
5
6
7
8
9
10
11
12
13
...
E. Giovannetti - AlgELab-09-10 - Lez.28
=
0
1
1
2
3
5
8
13
21
34
55
89
144
233
...
7
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 !
19/12/2015 10:16
E. Giovannetti - AlgELab-09-10 - Lez.28
8
Rappresentazione grafica delle eq. di ricorrenza
(albero di ricorsione)
fib(1)
=
1
+
fib(n)
=
fib(n-1)
19/12/2015 10:16
E. Giovannetti - AlgELab-09-10 - Lez.28
fib(n-2)
9
liv. 0
liv. 1
fib(n-2)
19/12/2015 10:16
fib(n)
=
+
+
+
fib(n-3)
fib(n-3)
E. Giovannetti - AlgELab-09-10 - Lez.28
fib(n-4)
10
fib(n)
liv. 0
+
+
liv. 1
liv. 2
=
+
+
+
+
+
liv. 3
fib(n-3) fib(n-4) fib(n-4) fib(n-5)
fib(n-4) fib(n-5) fib(n-5) fib(n-6)
eccetera
19/12/2015 10:16
E. Giovannetti - AlgELab-09-10 - Lez.28
11
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);
}
19/12/2015 10:16
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.
19/12/2015 10:16
E. Giovannetti - AlgELab-09-10 - Lez.28
13
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.
19/12/2015 10:16
E. Giovannetti - AlgELab-09-10 - Lez.28
14
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
INVARIANTE
ultimo è 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++;
19/12/2015 10:16
E. Giovannetti - AlgELab-09-10 - Lez.28
15
Test del ciclo
• Si esce quando i = n: in tal caso, evidentemente,
ultimo è l'n-esimo numero di Fibonacci; quindi:
while(i < n)
Inizializzazione
0 è 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;
19/12/2015 10:16
E. Giovannetti - AlgELab-09-10 - Lez.28
16
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;
19/12/2015 10:16
E. Giovannetti - AlgELab-09-10 - Lez.28
17
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;
19/12/2015 10:16
E. Giovannetti - AlgELab-09-10 - Lez.28
18
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;
}
19/12/2015 10:16
E. Giovannetti - AlgELab-09-10 - Lez.28
19
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;
}
19/12/2015 10:16
E. Giovannetti - AlgELab-09-10 - Lez.28
20
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;
}
19/12/2015 10:16
E. Giovannetti - AlgELab-09-10 - Lez.28
21
Esercizio
Si scriva una versione della procedura sequenzaDiFib che
restituisca un array di BigInteger.
19/12/2015 10:16
E. Giovannetti - AlgELab-09-10 - Lez.28
22
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.
19/12/2015 10:16
E. Giovannetti - AlgELab-09-10 - Lez.28
23