Dúvida sonbre Fatorial

Programação Java
#1

Olá pessoal, seguinte

Estou utilzando esse método para calcular fatorial:

public long fatorial(int n) { if(n==0||n==1) { return 1; } else { return n*fatorial(n-1); } }

Ok, ele funciona perfeitamente para entradas de números pequenos. Mas conforme as entradas vão aumentando de valor o método começa a retornar números long negativos(que acho que é porque estourou o long) e após certp número ele começa a retornar 0.

Alguém sabe me explicar por qual motivo isso acontece e se existe alguma forma de consertar meu algoritmo de forma que ele consiga realizar o fatorial de números maiores?

Muito obrigado pela ajuda!

#2

Capitão, como está pretendendo usar a recursão, deve ter em mente que:

Fat(n) => 1, se n=0 E
n*Fat(n-1), se n>0

Então o algoritmo seria:

FatRec(N:inteiro)
SE (n=0)
ENTÃO returne 1;
SENÃO retorne n*FatRec(N-1);

E atenção: soluções recursivas são frequentemente mais lentas! :shock:
Em uma analise de algoritmos, faz diferença!

Espero ter ajudado! :wink:

#3

Ok, obrigado pela dica!

Mas quanto aos número longos. Por exeplo se formos executar o método com;

fatorial(70), ele retorna 0, enquanto na verdade ele deveria resultar o resultado da multiplicação 70696867666564*65…21!

Alguém sabe como fazer?

Obrigado! :smiley:

#4

Não use recursão, use for.

#5

Sem recursividade:

public static int fatorial(int n) {
		if (n == 0) {
			return 1;
		}

		int f = 1;

		while (n > 1) {
			f = f * n;
			--n;
		}

		return f;
}

O máximo que consegui com esse algoritmo foi 25!.. Você pode usar o BigInteger se precisar de mais, embora esta classe imponha algumas restrições.

[]'s

#6

[quote=capitao]Olá pessoal, seguinte

Estou utilzando esse método para calcular fatorial:

public long fatorial(int n) { if(n==0||n==1) { return 1; } else { return n*fatorial(n-1); } }

Ok, ele funciona perfeitamente para entradas de números pequenos. Mas conforme as entradas vão aumentando de valor o método começa a retornar números long negativos(que acho que é porque estourou o long) e após certp número ele começa a retornar 0.

Alguém sabe me explicar por qual motivo isso acontece e se existe alguma forma de consertar meu algoritmo de forma que ele consiga realizar o fatorial de números maiores?

Muito obrigado pela ajuda![/quote]

O maior int é 2 elevado a 31 menos 1 (2147483647) , e o maior long é 2 elevado a 63 menos 1 (9223372036854775807). Como você deve ter percebido, esses números são menores que 70!, que é (segundo a calculadora do Windows) 1,1978571669969891796072783721689 vezes 10 elevado a 100.

Se você fizer as contas com double, vai conseguir calcular fatoriais até 170! (7,2574156153079989673967282111293e+306 segundo a calculadora do Windows, 7.257415615307994E306 usando o Java e double)

Se quiser fatoriais de números maiores, use java.math.BigInteger. Por exemplo, usando BigInteger, 170! vai dar
7257415615307998967396728211129263114716991681296451376543577798900561843401706157852350749242617459511490991237838520776666022565442753025328900773207510902400430280058295603966612599658257104398558294257568966313439612262571094946806711205568880457193340212661452800000000000000000000000000000000000000000

#7

Isso mesmo!

Muito Obrigado pelas contribuições!!!

:stuck_out_tongue: :stuck_out_tongue: :stuck_out_tongue: :stuck_out_tongue: :stuck_out_tongue: :stuck_out_tongue: :stuck_out_tongue:

#8

Thingol, eu tentei fazer o método com BigInteger mas não consegui… Pesquisei em alguns exemplos de como se manipula essa classe, mas não consegui adaptá-la ao meu problema.

Desculpa ser esse tipo chato de pidão, mas como você faria o método fatorial usando BigInteger?

Obrigado!

#9