Fattoriale nella programmazione Java

Oggi parleremo di fattoriali. Questa è una delle funzioni più basilari che un programmatore deve conoscere e allo stesso tempo essere in grado di lavorarci. Quindi iniziamo. Il fattoriale di n è il valore del prodotto (moltiplicazione) di tutti i numeri naturali da 1 a n, che viene indicato come n! Cosa sembra:

1! =  1
2! =  1 * 2 = 2
3! =  1 * 2 * 3 = 6
4! =  1 * 2 * 3 * 4 = 24
5! =  1 * 2 * 3 * 4 * 5  = 120

E un'altra piccola regola, per 0:

!0  = 1

Se vogliamo, ad esempio, ottenere la differenza fattoriale 6! e 4!:

6!-4! = 1⋅2⋅3⋅4⋅5⋅6 - 1⋅2⋅3⋅4 = 720 - 24 = 696

Diamo un'occhiata a come sarebbe in Java e comprendiamo diversi modi in cui è possibile calcolare il fattoriale.

La solita soluzione

public static int getFactorial(int f) {
  int result = 1;
  for (int i = 1; i <= f; i++) {
     result = result * i;
  }
  return result;
}

Niente di complicato: usiamo il numero ricevuto come dimensione del nostro ciclo, in cui moltiplichiamo per tutti i numeri precedenti fino a raggiungere f. E in principale:

System.out.println(getFactorial(6) - getFactorial(4));

Controlliamo e otteniamo il risultato desiderato: 696.

Soluzione ricorsiva

La ricorsione esegue una logica chiamando un metodo su se stesso. Questo metodo è chiamato ricorsivo. Tipicamente è composto da due parti:

1. condizione di uscita del metodo, al raggiungimento della quale il metodo dovrebbe smettere di chiamare se stesso e iniziare a passare i valori verso l'alto. Altrimenti, otterremo un ciclo infinito chiamando un metodo su se stesso e, di conseguenza, un StackOverflowError .

2. alcune elaborazioni (logiche) necessarie in una data situazione + chiamata stessa, ma con un valore in entrata diverso.

Il nostro esempio ideale di ricorsione oggi è trovare il fattoriale:

public static int getFactorial(int f) {
  if (f <= 1) {
     return 1;
  }
  else {
     return f * getFactorial(f - 1);
  }
}

Impostiamo la condizione per uscire dalla ricorsione quando raggiunge 1. Se l'argomento non è 1, moltiplichiamo il valore corrente per il risultato della successiva chiamata a questo metodo (dove inviamo il valore corrente -1).

Soluzione con Stream

Per chi non conosce la funzionalità streaming o per chi vuole rinfrescarsi la memoria, sarà utile leggere questo .

public static int getFactorial(int f) {
  if (f <= 1) {
     return 1;
  }
  else {
     return IntStream.rangeClosed(2, f).reduce((x, y) -> x * y).getAsInt();
  }
}

Qui utilizziamo una classe speciale IntStream, che fornisce funzionalità aggiuntive quando si lavora con il flusso da valori int. Per creare un flusso di questo tipo, utilizziamo il suo metodo statico rangeClosed, che crea valori da 2 a f compreso con un passaggio di 1. Successivamente, combiniamo tutti i valori utilizzando il metodo reduce, ovvero mostriamo in esso come vogliamo combinarli. Infine, otteniamo il valore risultante utilizzando il metodo terminale getAsInt.

Utilizzando BigInteger

In Java, la classe BigInteger viene spesso utilizzata per gestire i numeri, soprattutto quelli BIG . Dopotutto, se usiamo int, il fattoriale massimo che possiamo prendere senza perdere dati è 31, per lungo tempo - 39. Ma cosa succede se abbiamo bisogno di un fattoriale di 100? Diamo un'occhiata alle soluzioni precedenti, ma utilizzando BigInteger.

La solita soluzione

public static BigInteger getFactorial(int f) {
  BigInteger result = BigInteger.ONE;
  for (int i = 1; i <= f; i++)
     result = result.multiply(BigInteger.valueOf(i));
  return result;
}

L'algoritmo di conteggio è essenzialmente lo stesso, ma qui utilizziamo le funzionalità di BigInteger: BigInteger.ONE - per impostare il valore iniziale su 1. moltiplicazione - moltiplicazione tra il valore fattoriale precedente e il numero corrente.

Soluzione ricorsiva

public static BigInteger getFactorial(int f) {
  if (f <= 1) {
     return BigInteger.valueOf(1);
  }
  else {
     return BigInteger.valueOf(f).multiply(getFactorial(f - 1));
  }
}

La logica generale della soluzione non cambia, tranne per il fatto che vengono aggiunti alcuni metodi per lavorare con BigInteger.

Soluzione con Stream

public static BigInteger getFactorial(int f) {
  if (f < 2) {
     return BigInteger.valueOf(1);
  }
  else {
     return IntStream.rangeClosed(2, f).mapToObj(BigInteger::valueOf).reduce(BigInteger::multiply).get();
  }
}

Essenzialmente tutto è uguale, ma con BigInteger. Nello stream ora abbiamo il metodo mapToObj, con il quale convertiamo i valori int in BigInteger per poi moltiplicarli successivamente tra loro utilizzando multiply (beh, abbiamo aggiunto get per prendere un oggetto dal wrapper opzionale ). Se eseguiamo uno qualsiasi di questi tre metodi con argomento 100, non avremo un overflow e otterremo:

93326215443944152681699238856266700490715968264381621468592963895217599993229915608941463976156518286253697920827223758251185210916864000000000000000000000000