User Эллеонора Керри
Эллеонора Керри
41 уровень

Факториал в Java-программировании

Статья из группы Java Developer
Сегодня мы поговорим о факториалах. Это одна из самых базовых функций, которые программисту нужно знать, а заодно — уметь с этим работать. Итак, приступим. Факториал в Java-программировании - 1Факториал числа n — это значение произведения (умножения) всех натуральных чисел от 1 до n, которое обозначается как n! Как это выглядит:

1! =  1
2! =  1 * 2 = 2
3! =  1 * 2 * 3 = 6
4! =  1 * 2 * 3 * 4 = 24
5! =  1 * 2 * 3 * 4 * 5  = 120
И ещё одно небольшое правило, для 0:

!0  = 1
Если мы хотим, к примеру, получить разницу факториалов 6! и 4!:

6!-4! = 1⋅2⋅3⋅4⋅5⋅6 - 1⋅2⋅3⋅4 = 720 - 24 = 696
Давайте взглянем, как это будет выглядеть в Java и разберемся с несколькими способами того, как можно вычислить факториал.

Обычное решение


public static int getFactorial(int f) {
  int result = 1;
  for (int i = 1; i <= f; i++) {
     result = result * i;
  }
  return result;
}
Ничего сложного: используем пришедшее число как размер нашего цикла, в котором умножаем на все предыдущие числа, пока не дойдём до f. И в main:

System.out.println(getFactorial(6) - getFactorial(4));
Проверяем и получаем искомый результат: 696.

Рекурсивное решение

Рекурсия — это выполнения некоторой логики путем вызова методом самого себя. Такой метод называют рекурсивным. Как правило он состоит из двух частей:
  1. условие выхода из метода, при достижении которого метод должен перестать вызывать самого себя и начать отдавать значения наверх. Ведь иначе мы получим бесконечный цикл из вызова методом самого себя и как следствие — StackOverflowError.

  2. некоторая обработка (логика), необходимая в данной ситуации + вызов самого себя, но уже с другим входящим значением.

Идеальным примером для рекурсии у нас сегодня и послужит нахождение факториала:

public static int getFactorial(int f) {
  if (f <= 1) {
     return 1;
  }
  else {
     return f * getFactorial(f - 1);
  }
}
Задаем условие выхода из рекурсии при достижении 1. Если же аргумент не 1, то умножаем текущее значение на результат выполнения следующего захождения в данный метод (куда мы посылаем текущее значение -1).

Решение со Stream

Для не знающих stream функционал или для желающих освежить его в памяти, будет полезно прочитать вот это.

public static int getFactorial(int f) {
  if (f <= 1) {
     return 1;
  }
  else {
     return IntStream.rangeClosed(2, f).reduce((x, y) -> x * y).getAsInt();
  }
}
Тут мы используем специальный класс IntStream , дающий дополнительные возможности при работе со stream из int значений. Для создания такого stream мы используем его статический метод rangeClosed, который создаёт значения с 2 до f включительно с шагом 1. Далее мы объединяем все значения с помощью метода reduce, а именно — показываем в нем, как мы хотим их объединить. Наконец, мы получаем результирующее значение с помощью терминального метода getAsInt.

Применение BigInteger

В Java часто для обработки чисел, особенно БОЛЬШИХ, используется класс BigInteger. Ведь если мы используем int, то максимальный факториал, который мы можем взять без потери данных, — 31, для long — 39. А что если нам нужен будет факториал 100? Давайте же рассмотрим предыдущие варианты решения, но с использованием BigInteger. Факториал в Java-программировании - 2

Обычное решение


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;
}
Алгоритм подсчёта по сути тот же, но здесь мы используем возможности BigInteger: BigInteger.ONE — для задания стартового значения 1. multiply — умножение между предыдущим значением факториала и текущим числом.

Рекурсивное решение


public static BigInteger getFactorial(int f) {
  if (f <= 1) {
     return BigInteger.valueOf(1);
  }
  else {
     return BigInteger.valueOf(f).multiply(getFactorial(f - 1));
  }
}
Общая логика решения не изменяется, разве что добавляются некоторые методы для работы с BigInteger. Факториал в Java-программировании - 3

Решение cо 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();
  }
}
По сути всё то же самое, но с BigInteger. В stream у нас появился метод mapToObj, которым мы преобразуем значения int в BigInteger, чтобы в дальнейшем перемножить их между собой с помощью multiply (ну и добавился get для взятия объекта из обёртки Optional). Если же мы запустим любой из этих трёх методов с аргументом 100, то у нас не случится переполнения и мы получим:

93326215443944152681699238856266700490715968264381621468592963895217599993229915608941463976156518286253697920827223758251185210916864000000000000000000000000
Комментарии (13)
TO VIEW ALL COMMENTS OR TO MAKE A COMMENT,
GO TO FULL VERSION
Людмила Уровень 30 Гомель
7 мая 2021
Вот не понимаю почему во всех примерах что встречала начинают в цикле с 1 , а нес 2. Конечно это мелочь, результат получается тот же, но ведь 1*2*3*4, это не 1*1*2*3*4. int result = 1; for (int i = 1; i <= f; i++) { result = result * i; _________________________ int a = 1; for (int i = 2; i <= n; i++) { a = a * i;
Андрей Чубов Уровень 28 Новочеркасск Россия
19 апреля 2021
result = result.multiply(BigInteger.valueOf(i)); Почему в этом коде result изменяется раз класс BigInteger immutable?
Александр Плохой Уровень 41 Москва Россия
25 июня 2020
получение на вход отрицательных чисел не учтено, кэша нет(будет все время долго считаться) - так себе решение
Ann Уровень 26 Самара Россия
25 июня 2020
На мой взгляд, женщина на титульном фото такая страшная, что статью даже открывать не хочется. Портит настроение. Неужели никого более приятного нельзя было найти? Или это символ отношения большинства людей к факториалам?
Serp2015 Уровень 41 Тольятти Россия
25 июня 2020
Ссылки не работают, поправьте.