Factorielle en programmation Java

Aujourd'hui, nous allons parler de factorielles. C'est l'une des fonctions les plus élémentaires qu'un programmeur doit connaître et en même temps être capable de travailler avec. Alors, commençons. La factorielle de n est la valeur du produit (multiplication) de tous les nombres naturels de 1 à n, notée n ! À quoi il ressemble:

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

Et encore une petite règle, pour 0 :

!0  = 1

Si l’on veut, par exemple, obtenir la différence factorielle 6 ! et 4 ! :

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

Jetons un coup d'œil à ce à quoi cela ressemblerait en Java et comprenons plusieurs manières de calculer la factorielle.

La solution habituelle

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

Rien de compliqué : nous utilisons le nombre reçu comme taille de notre cycle, dans lequel nous multiplions par tous les nombres précédents jusqu'à atteindre f. Et en gros :

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

Nous vérifions et obtenons le résultat souhaité : 696.

Solution récursive

La récursivité fait preuve de logique en appelant une méthode sur elle-même. Cette méthode est dite récursive. Généralement, il se compose de deux parties :

1. condition de sortie de la méthode, une fois atteinte, la méthode doit cesser de s'appeler et commencer à transmettre des valeurs. Sinon, nous obtiendrons une boucle infinie en appelant une méthode sur elle-même et, par conséquent, une StackOverflowError .

2. un certain traitement (logique) nécessaire dans une situation donnée + s'appelant lui-même, mais avec une valeur entrante différente.

Notre exemple idéal de récursion aujourd'hui est de trouver la factorielle :

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

Nous définissons la condition pour quitter la récursion lorsqu'elle atteint 1. Si l'argument n'est pas 1, alors nous multiplions la valeur actuelle par le résultat du prochain appel à cette méthode (où nous envoyons la valeur actuelle -1).

Solution avec flux

Pour ceux qui ne connaissent pas la fonctionnalité stream ou pour ceux qui souhaitent se rafraîchir la mémoire, il sera utile de lire ceci .

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

Ici, nous utilisons une classe spéciale IntStream, qui fournit des fonctionnalités supplémentaires lorsque vous travaillez avec un flux à partir de valeurs int. Pour créer un tel flux, nous utilisons sa méthode statique rangeClosed, qui crée des valeurs de 2 à f inclus avec un pas de 1. Ensuite, nous combinons toutes les valeurs à l'aide de la méthode de réduction, à savoir, nous y montrons comment nous voulons les combiner. Enfin, nous obtenons la valeur résultante en utilisant la méthode du terminal getAsInt.

Utiliser BigInteger

En Java, la classe BigInteger est souvent utilisée pour gérer les nombres, notamment les BIG . Après tout, si nous utilisons int, alors la factorielle maximale que nous pouvons prendre sans perdre de données est de 31, pour longtemps - 39. Mais que se passe-t-il si nous avons besoin d'une factorielle de 100 ? Regardons les solutions précédentes, mais en utilisant BigInteger.

La solution habituelle

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'algorithme de comptage est essentiellement le même, mais ici nous utilisons les capacités de BigInteger : BigInteger.ONE - pour définir la valeur de départ sur 1. multiplier - multiplication entre la valeur factorielle précédente et le nombre actuel.

Solution récursive

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

La logique générale de la solution ne change pas, sauf que certaines méthodes permettant de travailler avec BigInteger sont ajoutées.

Solution avec flux

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();
  }
}

En gros, tout est pareil, mais avec BigInteger. Dans le flux, nous avons maintenant la méthode mapToObj, avec laquelle nous convertissons les valeurs int en BigInteger afin de les multiplier ensuite ensemble à l'aide de multiplie (enfin, nous avons ajouté get pour prendre un objet du wrapper facultatif ). Si nous exécutons l’une de ces trois méthodes avec l’argument 100, alors nous n’aurons pas de débordement et nous obtiendrons :

93326215443944152681699238856266700490715968264381621468592963895217599993229915608941463976156518286253697920827223758251185210916864000000000000000000000000