Algoritmi

I numeri di Fibonacci

La serie di Fibonacci e le sue proprietà.

Tale serie si deve a d un certo Leonardo, detto Bigollo, conosciuto anche col nome paterno di "fillio Bonacci" o Fibonacci,figlio d'un borghese uso a trafficare nel Mediterraneo,visse fin da piccolo nei paesi arabi e apprese i principi dell'algebra, il calcolo, dai maestri di Algeri, cui era stato affidato dal padre, esperto computista.
Più tardi, sempre esercitando la mercatura, Leonardo viaggiò in Siria, Egitto, Grecia, conoscendo i massimi matematici musulmani. Da queste esperienze nacque il Liber Abaci, un colossale trattato che dischiuse all'Occidente i misteri delle nove "figure" indiane e del segno sconosciuto ai greci e ai latini, "quod arabice zephirum appellantur", che indica un numero vuoto come un soffio di vento: zefito appunto, zefr, o zero.
La sua particolare serie si deve ad un torneo tra abachisti e algoritmisti, indetto nel 1223 a Pisa, dall'imperatore Federico II di Svevia, tale torneo fu vinto dal fibonacci grazie proprio alla sua serie.

Ma vediamo di cosa si tratta: la sequenza di Fibonacci è ricorsiva, se si pone F(0) = 0 e F(1) = 1, la sequenza viene data dalla formula

F(n) = F(n-1) + F(n-2)

generando numeri di questo tipo:

Ecco elencate alcune proprietà che ha questa sequenza:

1) Il quadrato di ogni numero di Fibonacci differisce di uno dal prodotto dei due numeri di fianco ad esso. La differenza è, alternativamente, più o meno, via via che la serie continua.

Il quadrato del 4° numero di Fibonacci è 9, che differisce di -1 dal prodotto del 3° e del 5° numero, che è 2*5=10. Il quadrato del 5° numero, 25, invece, differisce di +1 da 3*8=24.

2) Sommando i primi n numeri di Fibonacci ed aggiungendo 1, il risultato è sempre uguale al numero (n+2) di Fibonacci, ovvero al numero due volte dopo all'ultimo addizionato.
Ad esempio, sommando i primi 6 numeri di Fibonacci si ottiene 20, che è uguale al 8 numero di Fibonacci (21) -1.

3) Se invece di sommare tutti i numeri se ne somma uno si ed uno no, il risultato è sempre uguale al numero successivo all'ultimo addizionato.
Quindi sommando uno ogni due i primi 9 numeri si ottiene: 1+2+5+13+34 = 55 , il decimo numero.

4) Se si somma il quadrato dell'n° numero con il quadrato del suo successivo si ottiene il 2n+1° numero della sequenza.
Il quarto numero è 3, il quinto 5. La somma dei due quadrati è 3*3 + 5*5 = 9 + 25 = 34, ovvero il nono numero.

5) Ogni terzo numero di Fibonacci F(3n) è divisibile per 2, ogni quarto numero F(4n) è divisibile per 3, ogni quinto numero F(5n) è divisibile per 5, ogni sesto per 8, e così via, essendo i divisori i numeri della sequenza di Fibonacci.

6) Per quattro numeri di Fibonacci consecutivi qualsiasi, chiamati A, B, C, D, è sempre valida la seguente relazione: C^2 - B^2 = A * D.

Prendendo i numeri di Fibonacci dal quarto al settimo abbiamo: A=3, B=5, C=8, D=13. Come scritto nella formula, 64 - 25 = 3 * 13 = 39.

7) A parte il caso banale dello zero e dell'uno, l'unico numero di Fibonacci quadrato perfetto è F(12), che è proprio 12*12=144. L'unico cubo è F(6) = 8.

Di seguito riporto un programma in fortran 90per il calcolo della serie di fibonacci.
Dati i due numeri F(0) ed F(1) valuta la serie e fornisce l'n-simo numero di fibonacci richiesto.

! --------------------------------------------------
SUBROUTINE scambia(x,y)
! --------------------------------------------------

IMPLICIT NONE
! - - - arg types - - -
INTEGER :: x,y
! - - - local declarations - - -
INTEGER :: z

! - - - begin - - -
z = x
x = y
y = z

RETURN

END SUBROUTINE

! --------------------------------------------------
PROGRAM SCAMBIO
! --------------------------------------------------

IMPLICIT NONE
! - - - local declarations - - -
INTEGER :: a,b

! - - - begin - - -
WRITE (*,901) "Inserisci due numeri interi: "
READ (*,902) a
READ (*,902) b
WRITE (*,903) "Prima dello scambio: a=",a,", b=",b,"."
CALL scambia(a, b)
WRITE (*,903) "Dopo lo scambio: a=",a,", b=",b,"."
STOP

901 FORMAT (99A)
902 FORMAT (I,A,I)
903 FORMAT (A,I0,A,I0,A)
END PROGRAM

• » Invia tramite EMAIL
• » Versione per la STAMPA
• » Le vostre opinioni

I link correlati all'argomento

• L'algoritmo dei minimi quadrati
• L'algoritmo di Eulero
• L'algoritmo di eliminazione di Gauss
• L'algoritmo della Secante