Serie di Fibonacci in Java

1. Panoramica

In questo tutorial, esamineremo la serie di Fibonacci.

Nello specifico, implementeremo tre modi per calcolare l' ennesimo termine della serie di Fibonacci, l'ultimo essendo una soluzione a tempo costante.

2. Serie di Fibonacci

La serie di Fibonacci è una serie di numeri in cui ogni termine è la somma dei due termini precedenti . I primi due termini sono 0 e 1 .

Ad esempio, i primi 11 termini della serie sono 0, 1, 1, 2, 3, 5, 8, 13, 21, 34 e 55 .

In termini matematici, la sequenza S n dei numeri di Fibonacci è definita dalla relazione di ricorrenza:

S(n) = S(n-1) + S(n-2), with S(0) = 0 and S(1) = 1

Vediamo ora come calcolare l' ennesimo termine della serie di Fibonacci. I tre metodi su cui ci concentreremo sono ricorsivi, iterativi e utilizzano la formula di Binet.

2.1. Metodo ricorsivo

Per la nostra prima soluzione, esprimiamo semplicemente la relazione di ricorrenza direttamente in Java:

public static int nthFibonacciTerm(int n) { if (n == 1 || n == 0) { return n; } return nthFibonacciTerm(n-1) + nthFibonacciTerm(n-2); }

Come possiamo vedere, controlliamo se n è uguale a 0 o 1. Se è vero, restituiamo quel valore. In ogni altro caso, chiamiamo ricorsivamente la funzione per calcolare il (n-1) esimo termine e (n-2) esimo termine e restituire la loro somma.

Sebbene il metodo ricorsivo sia semplice da implementare, vediamo che questo metodo esegue molti calcoli ripetuti. Ad esempio, per calcolare il 6 ° termine, effettuiamo chiamate per calcolare il 5 ° e il 4 ° termine. Inoltre, la chiamata per calcolare il 5 ° termine effettua una chiamata per calcolare nuovamente il 4 ° termine. A causa di questo fatto, il metodo ricorsivo fa molto lavoro ridondante.

A quanto pare, questo rende esponenziale la sua complessità temporale; O (Φn) per essere esatti.

2.2. Metodo iterativo

Nel metodo iterativo, possiamo evitare i calcoli ripetuti eseguiti nel metodo ricorsivo. Invece, calcoliamo i termini della serie e memorizziamo i due termini precedenti per calcolare il successivo.

Diamo un'occhiata alla sua implementazione:

public static int nthFibonacciTerm(int n) { if(n == 0 || n == 1) { return n; } int n0 = 0, n1 = 1; int tempNthTerm; for (int i = 2; i <= n; i++) { tempNthTerm = n0 + n1; n0 = n1; n1 = tempNthTerm; } return n1; }

In primo luogo, controlliamo se il termine da calcolare è lo 0 ° termine o il 1 ° termine. In tal caso, restituiamo i valori iniziali. Altrimenti, calcoliamo il 2 ° termine usando n0 e n1 . Quindi, modifichiamo i valori delle variabili n0 e n1 per memorizzare rispettivamente il 1 ° e il 2 ° termine. Continuiamo a ripetere finché non abbiamo calcolato il termine richiesto.

Il metodo iterativo evita il lavoro ripetitivo memorizzando gli ultimi due termini di Fibonacci in variabili. La complessità temporale e spaziale del metodo iterativo è rispettivamente O (n) e O (1) .

2.3. Formula di Binet

Abbiamo definito solo l' ennesimo numero di Fibonacci in termini dei due precedenti. Ora, esamineremo la formula di Binet per calcolare l' ennesimo numero di Fibonacci in tempo costante.

I termini di Fibonacci mantengono un rapporto chiamato sezione aurea denotato da Φ , il carattere greco pronunciato "phi" .

Per prima cosa, diamo un'occhiata a come viene calcolato il rapporto aureo :

Φ = ( 1 + √5 )/2 = 1.6180339887...

Ora, diamo un'occhiata alla formula di Binet :

Sn = Φⁿ–(– Φ⁻ⁿ)/√5

In realtà, questo significa che dovremmo essere in grado di ottenere l' ennesimo numero di Fibonacci con solo un po 'di aritmetica.

Esprimiamo questo in Java:

public static int nthFibonacciTerm(int n) { double squareRootOf5 = Math.sqrt(5); double phi = (1 + squareRootOf5)/2; int nthTerm = (int) ((Math.pow(phi, n) - Math.pow(-phi, -n))/squareRootOf5); return nthTerm; }

Per prima cosa calcoliamo squareRootof5 e phi e li memorizziamo in variabili. Successivamente, applichiamo la formula di Binet per ottenere il termine richiesto.

Poiché qui abbiamo a che fare con numeri irrazionali, otterremo solo un'approssimazione. Di conseguenza, dovremo mantenere più cifre decimali per numeri di Fibonacci più alti per tenere conto dell'errore di arrotondamento.

Vediamo che il metodo precedente calcola l' ennesimo termine di Fibonacci in tempo costante, o O (1).

3. Conclusione

In questo breve articolo, abbiamo esaminato la serie di Fibonacci. Abbiamo esaminato una soluzione ricorsiva e una soluzione iterativa. Quindi, abbiamo applicato la formula di Binet per creare una soluzione a tempo costante.

Come sempre, il codice sorgente completo degli esempi funzionanti è disponibile su GitHub.