In 1202, Leonardo da Pisa (comunemente noto come Fibonacci. Cercatelo su Wikipedia. Ha un ruolo fondamentale per l'Europa medioevale.) studiò un problema relativo alla riproduzione dei conigli. Fece le seguenti assunzioni semplificatorie:
La popolazione inizia il primo mese con una coppia di conigli neonati. I conigli raggiungono l'età riproduttiva dopo un mese. Ogni mese, ciascun paio di conigli in età riproduttiva si accoppia. Esattamente dopo un mese dall'accoppiamento, nascono un coniglio maschio e una femmina. I conigli non muoiono mai né smettono di riprodursi. Fibonacci voleva calcolare quante coppie di conigli sarebbero state presenti all'n-esimo mese. Il secondo mese, la coppia iniziale raggiunge l'età riproduttiva e si accoppia. Nel terzo mese, nasce una coppia di conigli e sono presenti due coppie; la coppia iniziale torna ad accoppiarsi. Al quarto mese, nasce un'altra coppia di conigli al paio iniziale, mentre il secondo paio raggiunge l'età riproduttiva e si accoppia. Abbiamo un totale di tre coppie. Dopo un anno, ci sono 144 coppie.
Benchè l'assunzione di Fibonacci che i conigli siano immortali sia irrealistica, il suo modello descrive piuttosto bene la riproduzione di una specie in un ambiente privo di redatori: quando i conigli europei furono introdotti in Australia a metà del 19-esimo secolo, non c'era alcun predatore in grado di ridurne seriamente la popolazione. Nello spazio di 50 anni, i conigli avevano completamente eliminato diverse specie di piante in tutto il continente, modificando l'ecosistema australiano in modo irreversibile e trasformando una gran parte delle terre erbose nelle aree erose, praticamente inabitabili, che costituiscono l'odierno Outback. In questo esempio useremo la semplice idea di contare coppie di conigli per introdurre la tecnica computazionale di costruire soluzioni complesse a partire da elementi più piccoli.
Una relazione di ricorrenza è un modo di definire gli elementi di una sequenza a partire dal volore dei termini precedenti. Nel caso dei conigli di Fibonacci, in ogni mese ci saranno tutti i conigli che erano vivi il mese precedente più i neonati. L'osservazione chiave è che il numero di coppie di neonati è uguale al numero di coppie che erano presenti due mesi prima e che si sono accoppiati il mese precedente. Di conseguenza, se $F(n)$ rappresenta il numero di coppie vive nel mese n-esimo, otteniamo la sequenza di Fibonacci calcolando $F(n)$ attraverso la relazione di ricorrenza $ F(0) = 0,\, F(1) = 1,\, F(n) = F(n-1) + F(n-2)$ (con $F(1)\,=\,F(2)\,=\,1$ per iniziare la sequenza). Benchè la sequenza porti il nome di Fibonacci, era già nota ai matematici indiani più di duemila anni fa.
Mario Merz
Soluzione recursiva¶
Sfrutta la possibilità di una funzione di chiamare se stessa. Lenta: calcola più volte gli stessi valori. Restituisce un solo $F(n)$.
def fib_recur(n):
if n == 0:
return 0
elif n == 1:
return 1
else:
return fib_recur(n-1) + fib_recur(n-2)
# Per avere la lista dei primi 19 numeri di Fibonacci partiamo da:
list1 = [x for x in range(20)]
# Per avere gli **indici** dei numeri di Fibonacci pari nei primi 19 numeri:
list2 = [i for i in list1 if fib_recur(i) % 2 == 0]
list2
Per valutare il tempo richiesto per trovare la risposta possiamo usare il comando "magico" %timeit.
%timeit list2 = [i for i in list1 if fib_recur(i) % 2 == 0]
Si può ottenere il risultato anche producendo tutta la lista e poi filtrandola:
list2_new = [fib_recur(i) for i in list1]
list2_new = [i for i in list2_new if i% 2 == 0]
list2_new
Soluzione costruendo la lista degli $F(n)$ fino al valore cercato¶
Calcola ciascun valore una sola volta. Restituisce tutta la lista fino a $F(n)$.
def fib_to(n):
fibs = [0, 1]
for i in range(2, n+1):
fibs.append(fibs[-1] + fibs[-2])
return fibs
list4 = fib_to(20)
print(list4)
Tempo richiesto:
%timeit list4 = fib_to(20)
# Per avere i numeri di Fibonacci pari nei primi 19 numeri:
print([i for i in list4 if i % 2 == 0])
Ricordiamo che il comando enumerate restituisce (sotto forma di iteratore) sia l'indice che il valore degli elementi di una lista.
list(enumerate(list4))
# Per avere gli indici dei numeri di Fibonacci pari nei primi 19 numeri:
print([t[0] for t in enumerate(list4) if t[1] % 2 == 0])
Soluzione recursiva 2¶
Non calcola tutta la lista.
def fib_recur_fast(n):
a, b = 0, 1
for i in range(n):
a, b = b, a+b
return a
Tempo richiesto per il calcolo del singolo $F(n)$:
%timeit fib_recur_fast(20)
fib_recur_fast(20)
Per avere tutta la lista e poi filtrarla:
list5 = [fib_recur_fast(i) for i in list1]
list5 = [i for i in list5 if i% 2 == 0]
list5
Soluzione recursiva 3¶
Provate a capire come calcola i numeri di Fibonacci la funzione seguente. Che strutture dati utilizza? Verificate che restituisca la risposta corretta. Valutate se è una soluzione veloce oppure lenta.
def fib_memo(n, computed = {0: 0, 1: 1}):
if n not in computed:
computed[n] = fib_memo(n-1, computed) + fib_memo(n-2, computed)
return computed[n]
Problema 1¶
Dati due interi positivi n≤40 e k≤5, scrivete una funzione che restituisca: Il numero totale di coppie di conigli che saranno presenti dopo n mesi, se all'inizio abbiamo una coppia e ogni coppia di conigli in età riproduttiva ( età ≥ 1) produce una cucciolata di k coppie di conigli (invece di una sola).
Problema 2¶
Modificate la funzione che calcola la relazione di ricorrenza di Fibonacci per adattarla al caso in cui tutti i conigli muoiono dopo un numero fisso m≥0 di mesi.