Fatorial de números grandes

20 de dezembro de 2008 5 respostas

luis.txt 20 de dezembro de 2008

Pessoal,

Estou precisando calcular fatorial de números grandes.. Mais precisamente o último dígito menos significativo diferente de zero desse fatorial.
Ex:
fat 5 --> 120 --> ultimo digito diferente de 0 --> 2

Já fiz em C, mas com números grandes, tenho problemas. Entao estou tentando em java.

Uso a seguinte classe:

import java.math.BigInteger; 
import java.util.Scanner;
 
 public class Main {
 
   public static void main(String[] args) {     
	 System.out.println("Fatorial 1000 --> "+fatorial("1000"));     
   } 

   static public BigInteger fatorial(String n) {     
     BigInteger um = new BigInteger("1");
     BigInteger resultado = um;
     BigInteger contador = um;
     BigInteger limite = new BigInteger(n);     
     while( contador.compareTo(limite) <=0){
       resultado = resultado.multiply(contador);
       contador = contador.add(um);
     }
     return resultado;
   }

 }

Funciona ok, mas não está atendendo ao tempo q tenho para resolver o problema,
me disseram q é possível resolver este problema por log.

Alguem sabe algum caminho de resolver este problema de maneira mais rápida?

Valeu pessoal!

5 Respostas

renzonuccitelli 20 de dez. de 2008

Se vc precisa somente do algarismo menos significativo, basta sempre guardá-lo e multiplicar pelo próximo número do fatorial, em vez de calcular o fatoria em si…

renzonuccitelli 20 de dez. de 2008

Tipo, pra dizer a verdade, para fatoriais maiores ou iguais a 5 sempre terá o algarismo significativo igual a zero, já que sempre haverá pelo menos um fator de 10 multiplicando o número. Mas se vc kiser uma classe que realmente multiplicasse os número, olhá ela aí:

public class ChecadorDeAlgarismoMenosSignificativoFatorial {
	
	public long getAlgarismo(long fatorial){
		long algarismo=1;
		for(long i=2;i<=fatorial;++i)
			algarismo=(algarismo*(i%10))%10;
		return algarismo;
	}
	
	static public void main(String[] a){
		ChecadorDeAlgarismoMenosSignificativoFatorial c=new ChecadorDeAlgarismoMenosSignificativoFatorial();
		System.out.println(c.getAlgarismo(1000));
	}

}

renzonuccitelli 20 de dez. de 2008

a ta, agora que vi que era o ultimo algarismo diferente de 0, foi mal…hehe

renzonuccitelli 20 de dez. de 2008

Alterando a classe para fazer o que vc quer

public class ChecadorDeAlgarismoMenosSignificativoFatorial {
	
	public long getAlgarismo(long fatorial){
		long algarismo=1;
		for(long i=2;i<=fatorial;++i){
			algarismo*=i;
			while(algarismo%10==0)
				algarismo/=10;
			algarismo=algarismo%10;
		}
		
		return algarismo;
	}
	
	static public void main(String[] a){
		ChecadorDeAlgarismoMenosSignificativoFatorial c=new ChecadorDeAlgarismoMenosSignificativoFatorial();
		System.out.println(c.getAlgarismo(5));
	}

}

como vc quer algarismo sig diferente de zero, basta "retirar" os fatores de 10 que multiplicam o número. Fazendo isso toda vez que se precede a multiplicação, além de não afetar a solução do problema, evita os estouros de variáveis. Não sei se essa é a melhor solução, mas funciona melhor que calcular todo o fatorial de números grandes.

Espero ter ajudado.

luis.txt 21 de dez. de 2008

valeu pessoal!

Criado 20 de dezembro de 2008

Ultima resposta 21 de dez. de 2008

Respostas 5

Participantes 2

5 Respostas

Topicos relacionados