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 coppia di conigli sopravvive e si riproduce per sempre…

Calcolare il numero di coppie di conigli dopo 10 mesi.

Analisi

Tramite i pulsanti puoi osservare l’evoluzione della popolazione di conigli fino al sesto mese

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, 89, … cioè il numero di coppie di conigli per ogni mese.

Al decimo mese ci saranno 55 coppie di conigli.

Algoritmo iterativo

A partire dai valori noti (1, 1) si calcola, mese dopo mese, un nuovo valore finché non si giunge al mese richiesto.

Per calcolare fibonacci(5) si seguono i passi

  1. fibonacci(1) = 1
  2. fibonacci(2) = 1
  3. fibonacci(3) = fibonacci(2)+fibonacci(1) = 1+1 = 2
  4. fibonacci(4) = fibonacci(3)+fibonacci(2) = 2+1 = 3
  5. fibonacci(5) = fibonacci(4)+fibonacci(3) = 3+2 = 5

Algoritmo ricorsivo

La formulazione ricorsiva dei numeri di Fibonacci è molto comoda perché sintetica

f(n)=\left \{ \begin{array}{ll} 1 & n=1,2 \\ f(n-1)+f(n-2) & n>2 \end{array}

Esempio: fibonacci(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

Con formula!

Non è necessario alcun algoritmo iterativo o ricorsivo se si utilizza la formula

f(n)=\frac{1}{\sqr{5}} \left [\left (\frac{1+\sqr{5}}{2} \right )^n-\left( \frac{1-\sqr{5}}{2} \right )^n \right ]

Il contributo del secondo termine è così piccolo che può essere trascurato.
Calcola il primo termine e considera l’intero più vicino (arrotonda).

Esercizi

  1. Calcola la somma dei primi n numeri di Fibonacci.
    Visualizza i passi compiuti con una tabella per n da 1 a

    n f(n) Somma
    1 1 1
    2 1 2
    3 2 4
    4 3 7
    5 5 12
    6 8 20
  2. Quanto vale il rapporto tra due numeri di Fibonacci consecutivi?
    Prova per n crescente finché non raggiungi un’approssimazione adeguata

    n f(n) (n+1)°/n° n°/(n+1)°
    1 1
    1 1 1 1
    2 1 2 0,5
    3 2 1,5 0,6…
    4 3 1,6… 0,625
    5 5 1,625 0,6153…
    1,6180339… 0,6180339…

Complessità degli algoritmi

Dopo aver analizzato il problema e individuati i 3 algoritmi discutiamo la loro complessità in tempo.

Algoritmo ricorsivo: il tempo di attesa può essere considerato proporzionale al numero di chiamate ricorsive

  • T(1) = 1
  • T(2) = 1
  • T(3) = 1+T(2)+T(1) = 1+1+1 = 3 > 22-1
  • T(4) = 1+T(3)+T(2) = 1+3+1 = 5 > 22-1
  • T(5) = 1+T(4)+T(3) = 1+5+3 = 9 > 23-1
  • T(6) = 1+T(5)+T(4) = 1+9+5 = 15 > 23-1
  • T(7) = 1+T(6)+T(5) = 1+15+9 = 25 > 24-1
  • T(8) = 1+T(7)+T(6) = 1+25+15 = 41 > 24-1
  • 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).

L’algoritmo ricorsivo per il calcolo dell’n-simo numero di Fibonacci ha complessità esponenziale!

Algoritmo iterativo: si tratta di un algoritmo con un’iterazione semplice, senza chiamate ricorsive, quindi

  • T(n)=c1+c2n
  • T(n) ∈ O(n).

L’algoritmo iterativo per il calcolo dell’n-simo numero di Fibonacci ha complessità lineare!

Con formula: se consideriamo costante il tempo necessario per svolgere le singole operazioni presenti nella formula allora

  • T(n)=c
  • T(n) ∈ O(1).

Se consideriamo che per n molto grande l’operazione di elevamento a potenza potrebbe dipendere dal numero di cifre e che il numero di cifre del risultato cresce proporzionalmente al log di n allora si ottiene una complessità O(log n).

Conclusioni: per il calcolo dell’n-esimo numero di Fibonacci esistono diversi algoritmi con complessità diverse. Al variare di n utilizzeremo l’algoritmo più conveniente!