Нас могут попросить написать программу для вычисления факториала во время упражнений по кодированию на собеседованиях Java. Всегда лучше иметь представление о том, как построить такую факториальную программу.
1. Что такое факториал?
Факториал числа — это произведение всех положительных целых чисел до 1 в порядке убывания. Факториал числа n обозначается как «n!». Например, мы можем записать факториал числа 5 как:
5! => 5 * 4 * 3 * 2 * 1 => 120
Факториал нуля 0! равен 1. Просто запомните это.
2. Вычислить факториал с помощью итерации
Простая и самая базовая версия для нахождения факториала числа.
public static long factorialIterative(long n) {long r = 1;for(long i = 1; i <= n; i++) {r *= i;}return r;}3. Вычислить факториал с помощью рекурсии
Использование простой рекурсии может быть не очень хорошей идеей из-за ее низкой производительности, но рекурсия может быть очень хорошей реализацией для поиска факториала очень больших чисел. Это также общепризнанный ответ.
public static long factorialRecursive(long n) {return n == 1 ? 1 : n * factorialRecursive(n - 1);}4. Вычислите факториал с помощью Stream API
Мы можем использовать Java Stream API для вычисления факториала наиболее эффективным способом, как показано ниже.
public static long factorialStreams(long n) {return LongStream.rangeClosed(1, n).reduce(1,(long a, long b) -> a * b);}- Здесь метод LongStream.rangeClosed(2, n) создает поток длинных строк с содержимым [2, 3, … , n].
- reduce(a, b) -> a * b означает, что каждая пара a и b – умножает их и возвращает результат. Затем результат переносится в a для следующего раунда.
- Значение «1», используемое в сокращенном методе, используется в качестве начального значения переменной a для самой первой итерации.
5. Вычислить факториал очень больших чисел
Если мы запустим любой из приведенных выше примеров для чисел > 20, мы получим неверный вывод из-за ограничений типа данных long.
System.out.println(factorialRecursive(20)); // 2432902008176640000System.out.println(factorialRecursive(21)); // -4249290049419214848
Рассчитанные значения просто превышают то, что может храниться в течение длительного времени.
Класс BigInteger может выделить столько памяти, сколько ему нужно для хранения всех битов данных, которые ему поручают хранить. Очевидно, если в системе есть столько памяти, то только тогда.
public static BigInteger getFactorialOfLargeNumber(int num) {BigInteger result = BigInteger.ONE;for(int i = 1; i <= num; i++) {result = result.multiply(BigInteger.valueOf(i));}return result;}Теперь мы можем получить факториал любого числа, каким бы большим оно ни было.
System.out.println(getFactorialOfLargeNumber(22)); // 1124000727777607680000System.out.println(getFactorialOfLargeNumber(32)); // 263130836933693530167218012160000000System.out.println(getFactorialOfLargeNumber(132)); // Indeed a very long number is printed - Try yourself.