Перейти к основному содержимому

Вычислить факториал в Java

· 3 мин. чтения

1. Обзор​

Учитывая неотрицательное целое число n , факториал - это произведение всех положительных целых чисел, меньших или равных n .

В этом кратком руководстве мы рассмотрим различные способы вычисления факториала для заданного числа в Java .

2. Факториал для чисел до 20​

2.1. Факториал с использованием цикла for​

Давайте рассмотрим базовый алгоритм факториала с использованием цикла for : 

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

Приведенное выше решение отлично работает для чисел до 20 . Но если мы попробуем что-то большее, чем 20, это потерпит неудачу, потому что результаты будут слишком большими, чтобы поместиться в long , что приведет к переполнению.

Давайте посмотрим еще несколько, отметив, что каждый из них будет работать только для небольших чисел.

2.2. Факториал с использованием потоков Java 8​

Мы также можем использовать Java 8 Stream API для довольно простого вычисления факториалов:

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

В этой программе мы сначала используем LongStream для перебора чисел от 1 до n . Затем мы использовали метод reduce() , который использует значение идентичности и функцию-аккумулятор для шага сокращения.

2.3. Факториал с использованием рекурсии​

И давайте посмотрим еще один пример факториальной программы, на этот раз с использованием рекурсии:

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

2.4. Факториал с использованием математики Apache Commons​

В Apache Commons Math есть класс CombinatoricsUtils со статическим методом факториала , который мы можем использовать для вычисления факториала.

Чтобы включить Apache Commons Math, мы добавим зависимость commons -math3 в наш pom :

<dependency>
    <groupId>org.apache.commons</groupId>
    <artifactId>commons-math3</artifactId>
    <version>3.6.1</version>
</dependency>

Давайте рассмотрим пример с использованием класса CombinatoricsUtils : 

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

Обратите внимание, что тип возвращаемого значения — long , как и в наших собственных решениях.

Здесь это означает, что если вычисленное значение превышает Long.MAX_VALUE , генерируется исключение MathArithmeticException .

Чтобы стать больше, нам понадобится другой тип возвращаемого значения.

3. Факториал для чисел больше 20​

3.1. Факториал с использованием BigInteger​

Как обсуждалось ранее, тип данных long можно использовать для факториалов только при n <= 20 .

Для больших значений n мы можем использовать класс BigInteger из пакета java.math , который может содержать значения до 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. Факториал с использованием гуавы​

Библиотека Guava от Google также предоставляет служебный метод для вычисления факториалов для больших чисел.

Чтобы включить библиотеку, мы можем добавить ее зависимость от guava в наш pom :

<dependency>
    <groupId>com.google.guava</groupId>
    <artifactId>guava</artifactId>
    <version>31.0.1-jre</version>
</dependency>

Теперь мы можем использовать метод статического факториала из класса BigIntegerMath для вычисления факториала заданного числа:

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

4. Вывод​

В этой статье мы увидели несколько способов вычисления факториалов с использованием ядра Java, а также нескольких внешних библиотек.

Мы впервые увидели решения, использующие тип данных long для вычисления факториалов чисел до 20 . Затем мы увидели несколько способов использования BigInteger для чисел больше 20.

Код, представленный в этой статье, доступен на Github .