Cosa dovrebbe sapere un programmatore Java sui numeri di Fibonacci

Spesso durante le interviste, soprattutto presso aziende straniere, alle persone possono essere poste domande sugli algoritmi e, in una situazione di stress, ricordare freneticamente qualcosa non è sempre facile. Pertanto, è necessario prepararsi. Per cominciare, rinfrescatevi almeno la memoria con gli algoritmi di base. Oggi analizzeremo un fenomeno come i numeri di Fibonacci e le varianti più comuni dei problemi ad essi correlati. I numeri di Fibonacci sono una sequenza di numeri naturali che inizia con i numeri zero e uno, e ogni numero successivo è uguale alla somma dei due precedenti: F = {0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, ...}
F ₀ = 0, F ₁ = 1, F _n = F _{n - 1} + F _{n - 2} ;
n ≥ 0, n ∈ Z

Vale la pena notare che a volte viene omesso 0 e la serie inizia con 1 1 2 3... Di norma, nelle condizioni del problema viene immediatamente specificato con quali primi due numeri inizia la serie (0.1 o 1.1), quindi considereremo ulteriormente le soluzioni per entrambi i casi.

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?

1. 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.

2. 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 .

Tuttavia, il metodo ricorsivo non è consigliato perché, a differenza dei metodi precedenti, che vengono eseguiti in tempo lineare O(n), il completamento del metodo ricorsivo può richiedere molto più tempo. Perché? Il metodo ricorsivo può richiedere molto tempo, poiché durante il processo di calcolo la funzione verrà chiamata più volte dallo stesso argomento. Ad esempio, quando si valuta getFibonacciValue(7), la funzione effettuerà chiamate ricorsive a getFibonacciValue(5) e getFibonacciValue(6), entrambe le chiamate ricorsive chiameranno getFibonacciValue(4)), che risulterà nel chiamare le stesse operazioni più volte. Durante il colloquio, puoi mostrare questo metodo come soluzione, ma allo stesso tempo parlare dei suoi difetti e offrire in cambio un altro metodo. Vale anche la pena notare che il tipo int in Java ti consente di memorizzare da -2147483648 a 2147483647, quindi potrai calcolare solo i primi 46 numeri di Fibonacci: se proviamo a ottenere il successivo 47, si verificherà un overflow e otterremo un numero negativo. Se utilizziamo il tipo di dati long anziché int, saremo in grado di calcolare correttamente i primi 91 numeri di Fibonacci. Per calcolare i successivi numeri di Fibonacci, è necessario utilizzare la classe BigInteger, che implementa la logica per la memorizzazione e le operazioni aritmetiche di numeri veramente GRANDI.