Oblicz silnie w Javie

1. Przegląd

Biorąc pod uwagę nieujemną liczbę całkowitą n , silnia jest iloczynem wszystkich dodatnich liczb całkowitych mniejszych lub równych n .

W tym krótkim samouczku zbadamy różne sposoby obliczania silni dla danej liczby w Javie .

2. Silnia dla liczb do 20

2.1. Silnia za pomocą pętli for

Zobaczmy podstawowy algorytm silni wykorzystujący pętlę for :

public long factorialUsingForLoop(int n) { long fact = 1; for (int i = 2; i <= n; i++) { fact = fact * i; } return fact; }

Powyższe rozwiązanie będzie działać dobrze w przypadku liczb do 20 . Ale jeśli spróbujemy czegoś większego niż 20, to się nie powiedzie, ponieważ wyniki byłyby zbyt duże, aby zmieścić się w długim , powodując przepełnienie.

Zobaczmy jeszcze kilka, zauważając, że każdy z nich będzie działał tylko dla małych liczb.

2.2. Silnia przy użyciu strumieni Java 8

Możemy również użyć Java 8 Stream API do dość łatwego obliczania silni:

public long factorialUsingStreams(int n) { return LongStream.rangeClosed(1, n) .reduce(1, (long x, long y) -> x * y); }

W tym programie najpierw używamy LongStream do iteracji po liczbach od 1 do n . Następnie użyliśmy funkcji redukuj () , która wykorzystuje wartość tożsamości i funkcję akumulatora dla kroku redukcji.

2.3. Silnia przy użyciu rekursji

Zobaczmy kolejny przykład programu silni, tym razem wykorzystującego rekurencję:

public long factorialUsingRecursion(int n) { if (n <= 2) { return n; } return n * factorialUsingRecursion(n - 1); }

2.4. Silnia przy użyciu Apache Commons Math

Apache Commons Math ma klasę CombinatoricsUtils ze statyczną metodą silni , której możemy użyć do obliczenia silni.

Aby uwzględnić Apache Commons Math, dodamy zależność commons-math3 do naszego pom :

 org.apache.commons commons-math3 3.6.1 

Zobaczmy przykład wykorzystujący klasę CombinatoricsUtils :

public long factorialUsingApacheCommons(int n) { return CombinatoricsUtils.factorial(n); }

Zwróć uwagę, że jego typ zwrotu jest długi , podobnie jak nasze rozwiązania stworzone w domu.

Oznacza to, że jeśli obliczona wartość przekracza Long.MAX_VALUE , generowany jest wyjątek MathArithmeticException .

Aby uzyskać większy, będziemy potrzebować innego typu zwrotu.

3. Silnia dla liczb większych niż 20

3.1. Silnia przy użyciu BigInteger

Jak omówiono wcześniej, długi typ danych może być używany do silni tylko dla n <= 20 .

Dla dużych wartości N , można użyć BigInteger klasy z java.math opakowania, które mogą posiadać wartości do 2 ^ Integer.MAX_VALUE :

public BigInteger factorialHavingLargeResult(int n) { BigInteger result = BigInteger.ONE; for (int i = 2; i <= n; i++) result = result.multiply(BigInteger.valueOf(i)); return result; }

3.2. Silnia przy użyciu guawy

Biblioteka Google Guava zapewnia również narzędzie do obliczania silni dla większych liczb.

Aby dołączyć bibliotekę, możemy dodać jej zależność od guawy do naszego pom :

 com.google.guava guava 25.1-jre 

Teraz możemy użyć statycznej metody silni z klasy BigIntegerMath, aby obliczyć silnię podanej liczby:

public BigInteger factorialUsingGuava(int n) { return BigIntegerMath.factorial(n); }

4. Wniosek

W tym artykule widzieliśmy kilka sposobów obliczania silni przy użyciu rdzenia Javy, a także kilku bibliotek zewnętrznych.

Po raz pierwszy zobaczyliśmy rozwiązania wykorzystujące długi typ danych do obliczania silni liczb do 20 . Następnie widzieliśmy kilka sposobów używania BigInteger dla liczb większych niż 20.

Kod przedstawiony w tym artykule jest dostępny na Github.