LA SEQUENZA DI fIBONACCI

Posted on 5 giugno 2021. Filed under: Senza categoria |

Secondo articolo sull’informatica applicata alla matematica.

Oggi vedremo la sequenza di Fibonacci. Sicuramente è un argomento che non tutti i comuni mortali conoscono, ma che abbiamo almeno la password per la matematica e/o l’astronomia e/o informatica

Prima di tutto vediamo chi è Fibonacci e cosa è questa sequenza.

Leonardo Pisano detto Fibonacci (Pisa, settembre 1170 circa – Pisa, 1242 ) è stato un matematico italiano.

È considerato uno dei più grandi matematici di tutti i tempi. Con altri dell’epoca contribuì alla rinascita delle scienze esatte dopo la decadenza dell’età tardo-antica e dell’Alto Medioevo. Con lui, in Europa, ci fu l’unione fra i procedimenti della geometria greca euclidea (gli Elementi) e gli strumenti matematici di calcolo elaborati dalla scienza araba (in particolare egli studiò per la parte algebrica il Liber embadorum dello studioso ebreo spagnolo Abraham ibn ‛Ezra).

Fibonacci è noto soprattutto per la sequenza di numeri da lui individuata e conosciuta, appunto, come "successione di Fibonacci" in cui ogni termine, a parte i primi due, è la somma dei due che lo precedono.

Una particolarità della sequenza o successione di Fibonacci è che il rapporto fra le coppie di termini successivi tende molto rapidamente al numero 1,61803…, noto con il nome di rapporto aureo o sezione aurea.

 

L’intento di Leonardo Fibonacci era quello di trovare una legge matematica che descrivesse la crescita di una popolazione di conigli.

Assumendo per ipotesi che:

  • si disponga di una coppia di conigli appena nati
  • questa prima coppia diventi fertile al compimento del primo mese e dia alla luce una nuova coppia al compimento del secondo mese;
  • le nuove coppie nate si comportino in modo analogo;
  • le coppie fertili dal secondo mese di vita in poi diano alla luce una coppia di figli al mese;

si verifica quanto segue:

  • dopo un mese una coppia di conigli sarà fertile,
  • dopo due mesi ci saranno due coppie di cui una sola fertile,
  • nel mese seguente, terzo mese dal momento iniziale, ci saranno 2+1=3 coppie perché solo la coppia fertile avrà generato; di queste tre, due saranno le coppie fertili, quindi nel mese seguente (quarto mese dal momento iniziale) ci saranno 3+2=5 coppie

In questo esempio, il numero di coppie di conigli di ogni mese esprime la successione di Fibonacci.

 

La sequenza di Fibonacci la troviamo nella realtà, nella quotidianità, ci circonda tanto che andiamo a fare la spesa, tanto che andiamo a lavorare o torniamo a casa.

Ecco alcuni casi pratici:

– spirali delle conchiglie

– Foglie delle piante

– Fiori

– I rami degli alberi

– Spirali delle galassie

– Fiocco di neve

e così via.

Sembrerebbe che anche i nostri polmoni con le aorte e vene che portano sangue, essendo come gli alberi seguano la sequenza di Fibonacci.

 

Visualizza immagine di origine

 

 

Visualizza immagine di origine

Vediamo ora matematicamente come ottenere questi numeri.

I primi numeri sono: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89 …

Ossia 1+1 = 2

Il precedente di 2 è 1 e quindi 1+2=3

Il precedente di 3 è 2, quindi 2+3=5

Il precedente di 5 è 3, quindi 3+5=8

Il precedente di 8 è 5, quindi 5+8= 13

Il precedente di 13 è 8, quindi 8+13=21

Il precedente di 21 è 13, quindi 13+21=34

Il precedente di 34 è 21, quindi 21+34= 55

Il precedente di 55 + 34, quindi 34+55= 89 e così via.

Il nuovo numero si ottiene con la somma dei due numeri precedenti.

Vediamo ora come tradurre questo concetto matematico in un qualunque linguaggio di programmazione.

Io userò VB.NET ma è facile convertirlo in qualunque altro linguaggio.

Ma a cosa serve aver un programma che mi calcola la sequenza di Fibonacci?

Vediamo.

I numeri di Fibonacci sono importanti nell’analisi computazionale in fase di esecuzione dell’algoritmo di Euclide per determinare il più grande divisore comune di due interi: l’input del caso peggiore per questo algoritmo è una coppia di numeri di Fibonacci consecutivi.
I numeri di Fibonacci sono usati in una versione polifase dell’algoritmo di ordinamento unione in cui una lista non ordinamento è divisa in due liste le cui lunghezze corrispondono a numeri di Fibonacci sequenziali , dividendo la lista in modo che le due parti abbiano lunghezze nella proporzione approssimativa φ. Un’implementazione su nastro dell’ordinamento di unione polifase è stata descritta in The Art of Computer Programming.
Un albero di Fibonacci è un albero binario i cui alberi figlio (ricorsivamente) differiscono in altezza esattamente di 1. Quindi è un albero AVLe uno con il minor numero di nodi per una data altezza – l’albero AVL "più sottile". Questi alberi hanno un certo numero di vertici che è un numero di Fibonacci meno uno, un fatto importante nell’analisi degli alberi AVL.
I numeri di Fibonacci sono usati da alcuni generatori di numeri pseudocasuali.
I numeri di Fibonacci sorgono nell’analisi della struttura dati dell’heap di Fibonacci.
Un metodo di ottimizzazione unidimensionale, denominato tecnica di ricerca di Fibonacci, utilizza numeri di Fibonacci.
La serie numerica di Fibonacci è utilizzata per la compressione con perdita opzionale nel formato di file audio IFF 8SVX utilizzato sui computer Amiga. La serie numerica compands l’onda audio originale simile ai metodi logaritmici come μ-law.
Sono anche utilizzati nella pianificazione del poker, che è un passo nella stima in progetti di sviluppo software che utilizzano la metodologia Scrum.

Alcune di queste le vedremo in prossimi articoli.

Vediamo ora il codice per scrivere la sequenze di Fibonacci.

Useremo diversi metodi.

Quello che andremo a ottenere con i vari metodi sarà questo:

image

Ecco il codice:

Dim n1 As Integer
Dim n2 As Integer
n1 = 1
n2 = 1
Console.WriteLine("{0}", n1)
While n2 < FinoAQualeNumeroSiVuoleArrivare
    Console.WriteLine(n2)
    n2 = n2 + n1
    n1 = n2 – n1
End While
Console.ReadLine()

 

Secondo metodo:

For i As Integer = 0 To QuantiNumeriScrivere
    Console.WriteLine(Fibonacci(i))
Next

………..

Function Fibonacci(ByVal n As Integer) As Integer
    Dim a As Integer = 0
    Dim b As Integer = 1

    ‘ Add up numbers.
    For i As Integer = 0 To n – 1
        Dim temp As Integer = a
        a = b
        b = temp + b
    Next

    Return a
End Function

 

 

Terzo metodo:

Dim a As Integer = 0
Dim b As Integer = 1
Dim fib As Integer

Do
    Console.WriteLine(a.ToString)
    fib = a + b
    a = b
    b = fib
Loop While a <= FinoAQualeNumeroSiVuoleArrivare

 

Esistono poi altri metodi, ma non voglio diluire l’articolo.

 

Abbiamo visto quindi come “informatizzare” una serie numerica vecchia di 800 anni.

Alla prossima!

Make a Comment

Rispondi

Inserisci i tuoi dati qui sotto o clicca su un'icona per effettuare l'accesso:

Logo di WordPress.com

Stai commentando usando il tuo account WordPress.com. Chiudi sessione /  Modifica )

Google photo

Stai commentando usando il tuo account Google. Chiudi sessione /  Modifica )

Foto Twitter

Stai commentando usando il tuo account Twitter. Chiudi sessione /  Modifica )

Foto di Facebook

Stai commentando usando il tuo account Facebook. Chiudi sessione /  Modifica )

Connessione a %s...

Liked it here?
Why not try sites on the blogroll...