Numeri di Fibonacci
I numeri di Fibonacci prendono il nome da una sfida matematica che Fibonacci lanciò a un suo collega.
Il problema tratta la proverbiale velocità con cui i conigli si riproducono:
- il 1° mese è presente una coppia di conigli
- una coppia di conigli diventa matura all'inizio del 2° mese di vita
- la gestazione dura un mese
- ogni parto produce una coppia maschio-femmina di conigli
- ogni coniglio sopravvive e si riproduce per sempre...
Calcolare il numero di conigli dopo 10 mesi.
Soluzione
Siano a, b, c, ... i nomi dei conigli appena nati e A, B, C ... i nomi dei conigli dopo il primo mese di vita
Si osserva che ogni mese sono presenti i conigli già presenti il mese precedente più quelli appena nati, che sono in numero uguale ai conigli presenti due mesi prima!
I numeri di Fibonacci sono proprio la successione 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, ... cioè il numero di coppie di conigli per ogni mese.
Algoritmo ricorsivo
La formulazione ricorsiva dei numeri di Fibonacci è molto comoda perché sinteticafibonacci(1) = 1
fibonacci(2) = 1
fibonacci(n) = fibonacci(n-1)+fibonacci(n-2) // altrimenti
fibonacci(2) = 1
fibonacci(n) = fibonacci(n-1)+fibonacci(n-2) // altrimenti
Codifica
FUNZIONE fibonacci(INTERO n): INTERO
INIZIO
SE (n <= 2) ALLORA
fibonacci=1
ALTRIMENTI
fibonacci=fibonacci(n-1)+fibonacci(n-2)
FINE
INIZIO
SE (n <= 2) ALLORA
fibonacci=1
ALTRIMENTI
fibonacci=fibonacci(n-1)+fibonacci(n-2)
FINE
Esempio
Per calcolare fibonacci(5) si seguono i passifibonacci(5) = fibonacci(4)+fibonacci(3)
= [fibonacci(3)+fibonacci(2)]+[fibonacci(2)+fibonacci(1)]
= {[fibonacci(2)+fibonacci(1)]+1}+[1+1]
= {[1+1]+1}+[1+1]
= 5
= [fibonacci(3)+fibonacci(2)]+[fibonacci(2)+fibonacci(1)]
= {[fibonacci(2)+fibonacci(1)]+1}+[1+1]
= {[1+1]+1}+[1+1]
= 5
Calcolo della complessità
Se consideriamo che il tempo di attesa è proporzionale al numero di chiamate ricorsive allora calcoliamo quest'ultimo valore- T(1) = 1
- T(2) = 1
- T(3) = 1+T(2)+T(1) = 1+ 1+ 1 = 3
- T(4) = 1+T(3)+T(2) = 1+ 3+ 1 = 5
- T(5) = 1+T(4)+T(3) = 1+ 5+ 3 = 9
- T(6) = 1+T(5)+T(4) = 1+ 9+ 5 = 15
- T(7) = 1+T(6)+T(5) = 1+15+ 9 = 25
- T(8) = 1+T(7)+T(6) = 1+25+15 = 41
- T(9) = 1+T(8)+T(7) = 1+41+25 = 67
- ...
Sembra una sequenza strana ma se accettiamo una certa approssimazione
- T(1) = 1
- T(2) = 1
- T(3) = 1+T(2)+T(1) ≥ 2*T(1)+1 = 3 = 22-1
- T(4) = 1+T(3)+T(2) ≥ 2*T(2)+1 = 3
- T(5) = 1+T(4)+T(3) ≥ 2*T(3)+1 ≥ 7 = 23-1
- T(6) = 1+T(5)+T(4) ≥ 2*T(4)+1 ≥ 7
- T(7) = 1+T(6)+T(5) ≥ 2*T(5)+1 ≥ 15 = 24-1
- T(8) = 1+T(7)+T(6) ≥ 2*T(6)+1 ≥ 15
- T(9) = 1+T(8)+T(7) ≥ 2*T(7)+1 ≥ 31 = 25-1
- ...
Quindi
T(n) ≥ 2n/2-1.
Il tempo di attesa è maggiore di un tempo esponenziale, anche se con esponente n/2 piuttosto che n, quindi per n molto grande T(n) è O(2n).
Il tempo di attesa per calcolare l'n-esimo numero di Fibonacci, utilizzando l'algoritmo ricorsivo, è esponenziale!
Algoritmo iterativo
A partire dai valori noti (1, 1) si calcola, mese dopo mese, un nuovo valore finché non si giunge al mese richiestoCodifica
FUNZIONE fibonacci(INTERO n): INTERO
INIZIO
INTERO i, a, b, c
SE (N <= 2) ALLORA
fibonacci=1
ALTRIMENTI
INIZIO
a=1
b=1
PER i DA 3 A n CON PASSO +1
INIZIO
c=a+b
a=b
b=c
FINE
fibonacci=c
FINE
FINE
INIZIO
INTERO i, a, b, c
SE (N <= 2) ALLORA
fibonacci=1
ALTRIMENTI
INIZIO
a=1
b=1
PER i DA 3 A n CON PASSO +1
INIZIO
c=a+b
a=b
b=c
FINE
fibonacci=c
FINE
FINE
Esempio
Per calcolare fibonacci(5) si seguono i passifibonacci(1) = 1
fibonacci(2) = 1
fibonacci(3) = fibonacci(2)+fibonacci(1) = 1+1 = 2
fibonacci(4) = fibonacci(3)+fibonacci(2) = 2+1 = 3
fibonacci(5) = fibonacci(4)+fibonacci(3) = 3+2 = 5
fibonacci(2) = 1
fibonacci(3) = fibonacci(2)+fibonacci(1) = 1+1 = 2
fibonacci(4) = fibonacci(3)+fibonacci(2) = 2+1 = 3
fibonacci(5) = fibonacci(4)+fibonacci(3) = 3+2 = 5
Calcolo della complessità
Si tratta di un algoritmo con un'iterazione semplice, senza chiamate ricorsive, quindi T(n) = c1+c2n, O(n).Allora il tempo di attesa per calcolare l'n-esimo numero di Fibonacci, utilizzando l'algoritmo iterativo, è lineare!
