Fakultät in der Java-Programmierung

Heute werden wir über Fakultäten sprechen. Dies ist eine der grundlegendsten Funktionen, die ein Programmierer kennen und gleichzeitig damit arbeiten muss. Also lasst uns anfangen. Die Fakultät von n ist der Wert des Produkts (Multiplikation) aller natürlichen Zahlen von 1 bis n, der als n bezeichnet wird! Wie es aussieht:

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

Und noch eine kleine Regel, für 0:

!0  = 1

Wenn wir zum Beispiel die Fakultätsdifferenz 6! und 4!:

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

Werfen wir einen Blick darauf, wie dies in Java aussehen würde, und verstehen verschiedene Möglichkeiten, wie Fakultäten berechnet werden können.

Die übliche Lösung

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

Nichts Kompliziertes: Wir verwenden die empfangene Zahl als Größe unseres Zyklus, in dem wir mit allen vorherigen Zahlen multiplizieren, bis wir f erreichen. Und im Wesentlichen:

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

Wir prüfen und erhalten das gewünschte Ergebnis: 696.

Rekursive Lösung

Bei der Rekursion wird eine gewisse Logik ausgeführt, indem eine Methode für sich selbst aufgerufen wird. Diese Methode wird als rekursiv bezeichnet. Typischerweise besteht es aus zwei Teilen:

1. Methoden-Exit-Bedingung, bei deren Erreichen die Methode aufhören soll, sich selbst aufzurufen und mit der Übergabe von Werten beginnen soll. Andernfalls erhalten wir eine Endlosschleife durch den Aufruf einer Methode für sich selbst und als Ergebnis einen StackOverflowError .

2. eine gewisse Verarbeitung (Logik), die in einer bestimmten Situation notwendig ist + sich selbst aufruft, aber mit einem anderen eingehenden Wert.

Unser ideales Beispiel für die Rekursion ist heute das Finden der Fakultät:

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

Wir legen die Bedingung zum Beenden der Rekursion fest, wenn sie 1 erreicht. Wenn das Argument nicht 1 ist, multiplizieren wir den aktuellen Wert mit dem Ergebnis des nächsten Aufrufs dieser Methode (wobei wir den aktuellen Wert -1 senden).

Lösung mit Stream

Für diejenigen, die die Stream-Funktionalität nicht kennen oder ihr Gedächtnis auffrischen möchten, ist es hilfreich, dies zu lesen .

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

Hier verwenden wir eine spezielle Klasse IntStream, die zusätzliche Funktionen beim Arbeiten mit Streams aus int-Werten bietet. Um einen solchen Stream zu erstellen, verwenden wir seine statische Methode „rangeClosed“, die Werte von 2 bis einschließlich f mit einem Schritt von 1 erstellt. Als nächstes kombinieren wir alle Werte mit der Methode „reduce“, nämlich, wir zeigen darin, wie wir wollen sie kombinieren. Schließlich erhalten wir den resultierenden Wert mit der Terminalmethode getAsInt.

Verwenden von BigInteger

In Java wird die BigInteger- Klasse häufig zur Verarbeitung von Zahlen verwendet, insbesondere von BIG-Zahlen . Wenn wir int verwenden, beträgt die maximale Fakultät, die wir ohne Datenverlust verwenden können, schließlich 31, für lange Zeit 39. Aber was ist, wenn wir eine Fakultät von 100 benötigen? Schauen wir uns die vorherigen Lösungen an, verwenden jedoch BigInteger.

Die übliche Lösung

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

Der Zählalgorithmus ist im Wesentlichen derselbe, aber hier nutzen wir die Fähigkeiten von BigInteger: BigInteger.ONE – um den Startwert auf 1 zu setzen. Multiplikation – Multiplikation zwischen dem vorherigen Fakultätswert und der aktuellen Zahl.

Rekursive Lösung

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

Die allgemeine Logik der Lösung ändert sich nicht, außer dass einige Methoden für die Arbeit mit BigInteger hinzugefügt werden.

Lösung mit 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();
  }
}

Im Wesentlichen ist alles gleich, aber mit BigInteger. Im Stream haben wir jetzt die Methode mapToObj, mit der wir int-Werte in BigInteger umwandeln, um sie anschließend per multiply miteinander zu multiplizieren (naja, wir haben get hinzugefügt, um ein Objekt aus dem Optional- Wrapper zu nehmen ). Wenn wir eine dieser drei Methoden mit dem Argument 100 ausführen, kommt es zu keinem Überlauf und wir erhalten:

93326215443944152681699238856266700490715968264381621468592963895217599993229915608941463976156518286253697920827223758251185210916864000000000000000000000000