F = {0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, ...}
F 0 = 0, F 1 = 1, F n = F n - 1 + F n - 2 ;
n ≥ 0, n ∈ Z
Ottenere i primi n numeri di Fibonacci in Java
Supponiamo di avere il compito di ottenere i primi n numeri di Fibonacci.-
caso 0.1:
Ci arriva un certo numero n:
int[] arr = new int[n]; arr[0] = 0; arr[1] = 1; for (int i = 2; i < arr.length; ++i) { arr[i] = arr[i - 1] + arr[i - 2]; }
Creiamo un array di dimensione n. I primi due elementi saranno uguali a zero e uno, e gli elementi rimanenti si otterranno seguendo questo ciclo e utilizzando i numeri precedenti dell'array.
E mostriamo:
for (int i = 0; i < arr.length; ++i) { System.out.println(arr[i]); }
Imposta int n = 10;
E otteniamo:
0 1 1 2 3 5 8 13 21 34
-
per il caso 1.1 la soluzione in realtà non è diversa:
int[] arr = new int[n]; arr[0] = 1; arr[1] = 1; for (int i = 2; i < arr.length; ++i) { arr[i] = arr[i - 1] + arr[i - 2]; }
Tutto quello che dovevamo cambiare era il primo elemento dell'array arr[0]: da 0 a 1. Di conseguenza, i primi 10 elementi saranno:
1 1 2 3 5 8 13 21 34 55
Primi n numeri di Fibonacci via streaming
Ma vogliamo dimostrare il nostro livello. Vediamo quindi come sarebbe questa soluzione utilizzando stream .-
per 0,1:
Stream.iterate(new int[]{0, 1}, arr -> new int[]{arr[1], arr[0]+ arr[1]}) .limit(n) .map(y -> y[0]) .forEach(x -> System.out.println(x));
Il metodo iterativo statico della classe Stream restituisce un flusso ordinato infinito creato applicando la funzione all'array iniziale arr. Nel nostro caso la funzione è quella di impostare la regola per comporre ogni nuovo array, basandosi su quello precedente. Di conseguenza, otterremo un flusso di array:
{0,1} {1,1} {1, 2} {2, 3} {3, 5} {5, 8} {8, 13} {13, 21} {21, 34} {34, 55} …..
Ma ce ne saranno un numero infinito, e quindi utilizzando .limit(n) riduciamo il numero di elementi al primo n (nel nostro caso a 10).
Tuttavia, non abbiamo bisogno di uno stream di array, quindi usando .map(y -> y[0]) selezioniamo il primo elemento di ogni array e otteniamo uno stream con i numeri di cui abbiamo bisogno e lo stampiamo sulla console usando forEach .
Sembra più bello, vero?
con i primi elementi 1,1 anche questo codice sarà quasi lo stesso:Stream.iterate(new int[]{1, 1}, arr -> new int[]{arr[1], arr[0]+ arr[1]}) .limit(n) .map(y -> y[0]) .forEach(x -> System.out.println(x));
Anche in questo caso le differenze stanno nell'elemento iniziale: al posto di {0, 1} impostiamo {1, 1}
In realtà, i risultati saranno gli stessi dell’esempio precedente.
Somma dei numeri di Fibonacci
E se ci chiedessero di calcolare la somma dei numeri di Fibonacci fino all'ennesimo elemento compreso? Ciò non dovrebbe crearci alcuna difficoltà. Prendiamo una soluzione con uno stream e sostituiamo forEach con un paio di altri metodi:-
per 0,1:
int n = 10; int result = Stream.iterate(new int[]{0, 1}, arr -> new int[]{arr[1], arr[0]+ arr[1]}) .limit(n) .map(t -> t[0]) .mapToInt(Integer::intValue) .sum(); System.out.println(result);
Utilizzando .mapToInt(Integer::intValue) convertiamo il nostro flusso in un IntStream numerico e utilizziamo il suo metodo .sum() per ottenere la somma di tutti gli elementi.
- per il caso con 1,1 elementi iniziali, invece di {0, 1} impostiamo {1, 1}.
Ottenere l'ennesimo numero della serie di Fibonacci
A volte ti viene chiesto di stampare non una serie di numeri, ma specificatamente l'ennesimo numero della serie di Fibonacci. Di norma, ciò non fa altro che semplificare il compito, poiché è possibile adattare facilmente le soluzioni precedenti a questo scopo. Bene, che ne dici di risolvere il problema attraverso la ricorsione?-
per 0,1:
public int getFibonacciValue(int n) { if (n <= 1) { return 0; } else if (n == 2) { return 1; } else { return getFibonacciValue(n - 1) + getFibonacciValue(n - 2); } }
Per eseguire l'algoritmo con 0,1, è necessario specificare che quando proviamo a ottenere il primo elemento, otteniamo 0, e il secondo - 1. Infatti, come nelle soluzioni precedenti, dobbiamo impostare i primi due elementi.
-
l'implementazione per 1.1 sarà leggermente diversa:
public int getFibonacciValue(int n) { if (n == 0) { return 0; } else if (n == 1) { return 1; } else { return getFibonacciValue(n - 1) + getFibonacciValue(n - 2); } }
In questo caso, dobbiamo solo impostare il primo elemento su 1, poiché il secondo elemento sarà lo stesso e la risposta del metodo sarà la stessa.
Allo stesso tempo, impostiamo la reazione del metodo su 0, perché se non la impostiamo, quando 2 arriva come argomento, lo stesso metodo verrà chiamato ricorsivamente, ma con argomento 0. Successivamente, verrà avviato lo stesso metodo , ma con numeri negativi, e così via fino all'infinito negativo. Di conseguenza, riceveremo un StackOverflowError .
GO TO FULL VERSION