GUJ Discussões   :   últimos tópicos   |   categorias   |   GUJ Respostas

Calcule quantos zeros à direita tem o fatorial de 1 bilhão


#1

Quantos dígitos zeros à direita tem o fatorial de 1 bilhão?

Por exemplo, 10! = 3628800 tem 2 zeros à direita, 77! = 1,4518309202828586963407078408631e+113 (ou melhor, 145183092028285869634070784086308284983740379224208358846781574688061991349156420080065207861248000000000000000000 tem 18 zeros à direita, 100! = 9,3326215443944152681699238856267e+157 tem 24 zeros à direita, etc.

(Dica: não é para calcular o fatorial de 1 bilhão diretamente, que não vai caber na sua máquina.)

Isso não é lição de casa. Só estou perguntando aqui para ver como é que vocês costumam resolver tais coisas.


#2

Para quem quiser testar sua rotina, o fatorial de 1000000 tem 249998 zeros, o fatorial de 1000000000000 tem 249999999997 zeros e o fatorial de 3141592653590 tem 785398163387 zeros.


#3

package fatorial;
public class Main {
    private final static long CONST = 3141592653590L;
    public static void main(String[] args)
    {
        long nZeros = 0;
        long loop = 1;
        long count = -1;
        while (count != 0)
        {
            count = (CONST / pow(5, loop));
            nZeros += count;
            loop++;
        }
        System.out.println("Numero de Zeros a Direita para " + CONST + ": " + nZeros);
    }
    private static long pow (long n, long e)
    {
        long r = n;
        for (long i=1;i<e;i++)
            r*=n;
        return r;
    }
}

run:
Numero de Zeros a Direita para 3141592653590: 785398163387
CONSTRUÍDO COM SUCESSO (tempo total: 0 segundos)


#4

Parabéns, é isso mesmo.


#5

Caros amigos, não seria muito mais simples converter o resultado do fatorial em uma String e sair perconrrendo a mesma e a cada 0 incrementar uma variavel?


#6

Experimente fazer isso com 1 bilhão. O fatorial de 1 bilhão tem quase 8,6 bilhões de algarismos, ou seja, não vai caber em nenhuma máquina. Isso tudo para você descobrir que ele tem apenas 249.999.998 zeros à direita.


#7

Calcular o fatorial de cem mil já demora bastante, imagina o de 1 bilhão ...

E o número 1.000.000.000! (fatorial de 1 bilhão) nem cabe em uma String ...


#8

1 bilhão != 1 milhão (ou você acha que o ganhador da mega-sena consegue pagar as dívidas da Previdência Social?)

O fatorial de 1 milhão, casualmente, tem 5565703 dígitos, e cabe em uma String. Agora o tal fatorial de 1 bilhão não cabe.


#9

É, tem toda razão, é bem diferente.

Mas já arrumei isto.


#10

o mais simples mesmo seria usar regex. por exemplo:

String.valueOf(10002).replaceAll("[^0]", "").length()

#11

Ah, você queria contar quantos zeros existem no fatorial, não importando se estão à direita ou não. Nesse caso, o problema é mais complexo.

Digamos que eu queira saber quantos zeros existem em 30!

30! = 265252859812191058636308480000000

Para saber a quantidade de dígitos zero à direita, é só saber quantas vezes o número 10 divide o fatorial de n!.
Mas para saber se em uma determinada posição há um dígito zero, é um bocadinho mais complicado. Vou pensar a respeito.

265252859812191[0]586363[0]848[0000000]


#12

entendi, mas nesse caso eu ainda trabalharia com string:

   		StringBuilder fatorial = new StringBuilder ("45183092028285869634070784086308284983740379224208358846781574688061991349156420080065207861248000000000000000000");
    		int zerosDireita = 0;
    		while (fatorial.charAt(fatorial.length()-1) == '0'){
    			zerosDireita++;
    			fatorial.delete(fatorial.length()-1, fatorial.length());
    		}

#13

Concordo com o bob...
A solução seria trabalhar com String..


#14

jukkinha já respondeu, a resposta tem uma fórmula fechada, não precisa calcular todos os elementos do fatorial para fazer a conta. Fora que já respondemos aqui no GUJ:

http://www.guj.com.br/posts/list/15/119727.java#648682


#15