Hoje vamos falar sobre fatoriais e as formas mais comuns de encontrar fatoriais. Esta é uma das funções mais básicas que um programador precisa conhecer e ser capaz de trabalhar. Bem, vamos começar. O fatorial do número n, denotado como n!, é o valor do produto (multiplicação) de todos os números naturais de 1 a n. Aqui está o que parece (vamos atualizar seus conhecimentos de matemática):
1! = 1 2! = 1 * 2 = 2 3! = 1 * 2 * 3 = 6 4! = 1 * 2 * 3 * 4 = 24 5! = 1 * 2 * 3 * 4 * 5 = 120
E há mais uma pequena regra para 0:
!0 = 1
Se quisermos calcular a diferença entre 6! e 4!:
6!-4! = 1⋅2⋅3⋅4⋅5⋅6 - 1⋅2⋅3⋅4 = 720 - 24 = 696
Vamos ver como isso ficaria quando implementado na programação. Exploraremos algumas maneiras de fazer cálculos de fatorial em Java.
Solução ordinária em programa fatorial
Aqui está um programa fatorial simples usando loop:
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);
}
}
Nossa saída no console será:
O fatorial de 7 é: 5040
E mais um exemplo para esclarecer as coisas:
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;
}
Nada difícil aqui: usamos o número passado como tamanho do nosso loop, no qual multiplicamos por todos os números anteriores até chegar em f. E no principal:
System.out.println(getFactorial(6) - getFactorial(4));
Testando o código, vemos que obtemos o resultado desejado: 696.
Solução recursiva
A recursão acontece quando um método chama a si mesmo. Tal método é chamado de método recursivo. Como regra, consiste em duas partes:- Uma condição de encerramento — quando a condição de encerramento for satisfeita, o método deve parar de chamar a si mesmo e começar a transmitir valores. Afinal, se não houver condição de terminação, teremos um loop infinito, com o método chamando a si mesmo repetidamente até obtermos um StackOverflowError .
- Qualquer que seja a lógica que a situação exija, mais uma chamada recursiva, mas com um valor de entrada diferente.
public static int getFactorial(int f) { // finding factorial of number using recursive solution
if (f <= 1) {
return 1;
}
else {
return f * getFactorial(f - 1);
}
}
Nossa condição de término de recursão será quando atingirmos 1. Se o parâmetro não for 1, multiplicamos o valor atual pelo resultado da próxima chamada recursiva ao método (para o qual passamos o valor atual menos 1).
Solução com um fluxo
Qualquer pessoa que não esteja familiarizada com a funcionalidade Stream do Java ou que queira refrescar a memória se beneficiará com a leitura aqui .
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();
}
}
Aqui usamos a classe especial IntStream , que nos fornece recursos adicionais ao trabalhar com um fluxo de valores int. Para criar tal stream, usamos seu método estático rangeClosed , que gera valores de 2 a f, inclusive, em incrementos de 1. Em seguida, usamos o método reduce para combinar todos os valores. Mais especificamente, mostramos como queremos combinar os valores. Por fim, obtemos o valor resultante usando o método getAsInt do terminal .
Usando BigInteger
Em Java, a classe BigInteger costuma ser usada para lidar com números, especialmente números BIG. De fato, se usarmos int , o fatorial máximo que podemos manipular sem perda de dados é 31. Para o tipo de dados longo , o fatorial máximo é 39. Mas e se precisarmos do fatorial de 100? Vamos adaptar as soluções anteriores para BigInteger.solução comum
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;
}
O algoritmo é essencialmente o mesmo, mas aqui usamos os recursos de BigInteger: BigInteger.ONE é o valor inicial 1 e multiple() é usado para multiplicar o valor fatorial anterior e o número atual.
Solução recursiva
public static BigInteger getFactorial(int f) {
if (f <= 1) {
return BigInteger.valueOf(1);
}
else {
return BigInteger.valueOf(f).multiply(getFactorial(f - 1));
}
}
A lógica geral da solução não muda, exceto que alguns métodos são adicionados para trabalhar com BigInteger.
Solução com um fluxo
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();
}
}
Tudo é essencialmente o mesmo, mas com BigInteger. A classe Stream nos fornece o método mapToObj , que usamos para converter valores int em BigInteger para depois multiplicá-los com eles mesmos usando o método de multiplicação (e get() foi adicionado para obter um objeto do wrapper Optional ). Se executarmos qualquer um desses três métodos com um argumento de 100, evitaremos um estouro de pilha e obteremos o resultado correto:
9332621544394415268169923885626670049071596826438162146859296389521759999322991560894146397615651828625369792082722375825 11852109168640000000000000000000000000
GO TO FULL VERSION