Днес ще говорим за факториели и най-често срещаните начини за намиране на факториели. Това е една от най-основните функции, които програмистът трябва Howто да знае, така и да може да работи. Е, да започваме. Факториелът на числото n, означаван като n!, е стойността на произведението (умножението) на всички естествени числа от 1 до n. Ето How изглежда (нека опресним знанията ви по математика):
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
Нека да видим How ще изглежда това, когато се приложи в програмирането. Ще проучим няколко начина How да правим изчисления на факториел в Java.
Обикновено решение във факториална програма
Ето една проста факториална програма, използваща цикъл:
class FactorialExample{
public static void main(String args[]){
int i,fact=1;
int number=7;// our number to do the necessary calculations in class Factorial
for(i=1;i<=number;i++){
fact=fact*i;
}
System.out.println("Factorial of "+number+" is: "+fact);
}
}
Нашият изход на конзолата ще бъде:
Факториел на 7 е: 5040
И още един пример за подреждане на нещата:
public static int getFactorial(int f) {
int result = 1;
for (int i = 1; i <= f; i++) {
result = result * i; // finding factorial of number using loops
}
return result;
}
Тук няма нищо трудно: използваме предаденото число като размер на нашия цикъл, в който умножаваме по всички предишни числа, докато стигнем до f. И основно:
System.out.println(getFactorial(6) - getFactorial(4));
Тествайки codeа, виждаме, че получаваме желания резултат: 696.
Рекурсивно решение
Рекурсия се случва, когато метод се извиква сам. Такъв метод се нарича рекурсивен метод. По правило се състои от две части:- Прекратяващо condition — когато conditionто за прекратяване е изпълнено, методът трябва да спре да се извиква и да започне да предава стойности нагоре. В крайна сметка, ако няма condition за прекратяване, тогава ще имаме безкраен цикъл, като методът се извиква многократно, докато получим StackOverflowError .
- Каквато и логика да изисква ситуацията плюс рекурсивно извикване, но с различна входна стойност.
public static int getFactorial(int f) { // finding factorial of number using recursive solution
if (f <= 1) {
return 1;
}
else {
return f * getFactorial(f - 1);
}
}
Нашето condition за прекратяване на рекурсията ще бъде, когато достигнем 1. Ако параметърът не е 1, тогава умножаваме текущата стойност по резултата от следващото рекурсивно извикване на метода (към който предаваме текущата стойност минус 1).
Решение с поток
Всеки, който не е запознат с функционалността Stream на Java or всеки, който иска да опресни паметта си, ще има полза да прочете тук .
public static int getFactorial(int f) { // finding factorial of number using Stream
if (f <= 1) {
return 1;
}
else {
return IntStream.rangeClosed(2, f).reduce((x, y) -> x * y).getAsInt();
}
}
Тук използваме специалния клас IntStream , който ни дава допълнителни възможности при работа с поток от int стойности. За да създадем такъв поток, използваме неговия статичен метод rangeClosed , който генерира стойности от 2 до f, включително, на стъпки от 1. След това използваме метода за намаляване, за да комбинираме всички стойности. По-конкретно, ние му показваме How искаме да комбинираме ценностите. Накрая получаваме получената стойност с помощта на метода getAsInt на терминала .
Използване на BigInteger
В Java класът BigInteger често се използва за обработка на числа, особено ГОЛЕМИ числа. Наистина, ако използваме int , тогава максималният факториел, с който можем да се справим без загуба на данни, е 31. За дългия тип данни максималният факториел е 39. Но Howво ще стане, ако имаме нужда от факториел от 100? Нека адаптираме предишните решения към BigInteger.
Обикновено решение
public static BigInteger getFactorial(int f) { // finding factorial of number using BigInteger
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.
Решение с поток
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() беше добавен, за да получим обект от опционалната обвивка). Ако изпълним някой от тези три метода с аргумент 100, тогава ще избегнем препълване на стека и ще получим правилния резултат:
9332621544394415268169923885626670049071596826438162146859296389521759999322991560894146397615651828625369792082722375825 11852109168640000000000000000000000000
GO TO FULL VERSION