Il conteggio degli zeri finali dei numeri è il risultato fattuale

Question

Sto cercando di contare gli zeri finali di numeri risultanti da fattoriali (il che significa che i numeri diventano piuttosto grandi). Il codice seguente prende un numero, calcola il fattoriale del numero e conta gli zeri finali. Tuttavia, quando il numero è pari a 25 !, numZeros non funziona.

public static void main(String[] args) { 
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); 
    double fact; 
    int answer; 

    try { 
     int number = Integer.parseInt(br.readLine()); 
     fact = factorial(number); 
     answer = numZeros(fact); 
    } 
    catch (NumberFormatException e) { 
     e.printStackTrace(); 
    } catch (IOException e) { 
     e.printStackTrace(); 
    } 
} 

public static double factorial (int num) { 
    double total = 1; 
    for (int i = 1; i <= num; i++) { 
     total *= i; 
    } 
    return total; 
} 

public static int numZeros (double num) { 
    int count = 0; 
    int last = 0; 

    while (last == 0) { 
     last = (int) (num % 10); 
     num = num/10; 
     count++; 
    } 

    return count-1; 
} 

Non sto preoccupando l'efficienza di questo codice, e so che ci sono diversi modi per rendere l'efficienza di questo codice migliore. Quello che sto cercando di capire è perché il conteggio degli zeri finali di numeri superiori a 25! non funziona.

Qualche idea?

Answer 1

Il vostro compito non è quello di calcolare il fattoriale, ma il numero di zeri. Una buona soluzione utilizza la formula da http://en.wikipedia.org/wiki/Trailing_zeros (che si può provare a dimostrare)

def zeroes(n): 
    i = 1 
    result = 0 
    while n >= i: 
     i *= 5 
     result += n/i # (taking floor, just like Python or Java does) 
    return result 

spera che possiate tradurre questo a Java. Questo calcola semplicemente [n/5] + [n/25] + [n/125] + [n/625] + ... e si ferma quando il divisore diventa più grande di n.

NON utilizzare BigIntegers. Questo è un bozosort. Tali soluzioni richiedono secondi di tempo per grandi numeri.

Answer 2

Hai solo bisogno di sapere quanti 2 e 5 ci sono nel prodotto. Se stai contando gli zero finali, in realtà stai contando "Quante volte dieci divide questo numero?". se rappresenti n! come q * (2^a) * (5^b) dove q non è divisibile per 2 o 5. Quindi prendere solo il minimo di a e b nella seconda espressione ti darà quante volte 10 divide il numero. Effettivamente la moltiplicazione è eccessiva.

Modifica: il conteggio dei due è anche eccessivo, quindi è necessario solo i cinque.

E per qualche pitone, credo che questo dovrebbe funzionare:

def countFives(n): 
    fives = 0 
    m = 5 
    while m <= n: 
     fives = fives + (n/m) 
     m = m*5 
    return fives 

Answer 3

è possibile utilizzare un DecimalFormat per formattare grandi numeri. Se si formatta il numero in questo modo si ottiene il numero in scientific notation quindi ogni numero sarà come 1.4567E7 questo renderà il vostro lavoro molto più facile. Perché il numero dopo la E - il numero di caratteri dietro il. sono il numero di zeri finali che penso.

Non so se questo è il modello esatto necessario. Si può vedere come formare i modelli here

DecimalFormat formater = new DecimalFormat("0.###E0"); 

Answer 4

Il tipo double ha limitato la precisione, quindi se i numeri si sta lavorando diventano troppo grande il doppio sarà solo un'approssimazione. Per ovviare a questo è possibile utilizzare qualcosa come BigInteger per farlo funzionare per numeri interi arbitrariamente grandi.

Answer 5

Java raddoppia il massimo di un massimo di 9 * 10^18 dove 25! è 1.5 * 10^25. Se vuoi essere in grado di avere fattoriali così alti potresti voler usare BigInteger (simile a BigDecimal ma non fa decimali).

Answer 6

Ho scritto molto rapidamente, penso che risolva il problema con precisione. Ho usato la classe BigInteger per evitare che il cast da doppio a intero, che potrebbe causare problemi a. L'ho provato su molti grandi numeri oltre 25, come 101, che restituivano con precisione 24 zeri.

L'idea alla base del metodo è che se ne prendi 25! quindi il primo calcolo è 25 * 24 = 600, quindi puoi battere immediatamente due zeri e poi fare 6 * 23 = 138. Quindi calcola il fattoriale rimuovendo gli zeri mentre procede.

public static int count(int number) { 
    final BigInteger zero = new BigInteger("0"); 
    final BigInteger ten = new BigInteger("10"); 
    int zeroCount = 0; 
    BigInteger mult = new BigInteger("1"); 
    while (number > 0) { 
     mult = mult.multiply(new BigInteger(Integer.toString(number))); 
     while (mult.mod(ten).compareTo(zero) == 0){ 
      mult = mult.divide(ten); 
      zeroCount += 1; 
     } 
     number -= 1; 
    } 
    return zeroCount; 
} 

Dal momento che lei ha detto che non si cura di tempo di esecuzione a tutti (non che il mio primo era particolarmente efficiente, solo un po 'di più) questo fa proprio il fattoriale e quindi conta gli zeri, quindi è cenceptually semplice :

public static BigInteger factorial(int number) { 
    BigInteger ans = new BigInteger("1"); 
    while (number > 0) { 
     ans = ans.multiply(new BigInteger(Integer.toString(number))); 
     number -= 1; 
    } 
    return ans; 
} 

public static int countZeros(int number) { 
    final BigInteger zero = new BigInteger("0"); 
    final BigInteger ten = new BigInteger("10"); 
    BigInteger fact = factorial(number); 
    int zeroCount = 0; 
    while (fact.mod(ten).compareTo(zero) == 0){ 
     fact = fact.divide(ten); 
     zeroCount += 1; 
    } 
} 

Answer 7

I miei 2 centesimi: evitare di lavorare con il doppio poiché sono soggetti a errori. Un tipo di dato migliore in questo caso è BigInteger, e qui c'è un piccolo metodo che vi aiuterà a:

public class CountTrailingZeroes { 

    public int countTrailingZeroes(double number) { 
     return countTrailingZeroes(String.format("%.0f", number)); 
    } 

    public int countTrailingZeroes(String number) { 
     int c = 0; 
     int i = number.length() - 1; 

     while (number.charAt(i) == '0') { 
      i--; 
      c++; 
     } 

     return c; 

    } 

    @Test 
    public void $128() { 
     assertEquals(0, countTrailingZeroes("128")); 
    } 

    @Test 
    public void $120() { 
     assertEquals(1, countTrailingZeroes("120")); 
    } 

    @Test 
    public void $1200() { 
     assertEquals(2, countTrailingZeroes("1200")); 
    } 

    @Test 
    public void $12000() { 
     assertEquals(3, countTrailingZeroes("12000")); 
    } 

    @Test 
    public void $120000() { 
     assertEquals(4, countTrailingZeroes("120000")); 
    } 

    @Test 
    public void $102350000() { 
     assertEquals(4, countTrailingZeroes("102350000")); 
    } 

    @Test 
    public void $1023500000() { 
     assertEquals(5, countTrailingZeroes(1023500000.0)); 
    } 
} 

Answer 8

Ecco come l'ho fatta, ma con grande> 25 fattoriale lungo capacità non è sufficiente e deve essere utilizzata la classe BigInteger, con la strega non ho familiarità ancora :)

public static void main(String[] args) { 
    // TODO Auto-generated method stub 
    Scanner in = new Scanner(System.in); 
    System.out.print("Please enter a number : "); 
    long number = in.nextLong(); 
    long numFactorial = 1; 

    for(long i = 1; i <= number; i++) { 
     numFactorial *= i; 
    } 
    long result = 0; 
    int divider = 5; 
    for(divider =5; (numFactorial % divider) == 0; divider*=5) { 
     result += 1; 
    } 

    System.out.println("Factorial of n is: " + numFactorial); 
    System.out.println("The number contains " + result + " zeroes at its end."); 

    in.close(); 

} 

} 

Answer 9

il meglio con logaritmica tempo la complessità è la seguente:

public int trailingZeroes(int n) { 
    if (n < 0) 
     return -1; 

    int count = 0; 
    for (long i = 5; n/i >= 1; i *= 5) { 
     count += n/i; 
    } 

    return count; 
} 

spudoratamente copiato da http://www.programcreek.com/2014/04/leetcode-factorial-trailing-zeroes-java/

Answer 10

ho avuto lo stesso problema da risolvere in Javascript, e mi s come:

var number = 1000010000; 
var str = (number + '').split(''); //convert to string 
var i = str.length - 1; // start from the right side of the array 
var count = 0; //var where to leave result 
for (;i>0 && str[i] === '0';i--){ 
    count++; 
} 
console.log(count) // console shows 4 

Questa soluzione fornisce il numero di zeri finali.

var number = 1000010000; 
 
var str = (number + '').split(''); //convert to string 
 
var i = str.length - 1; // start from the right side of the \t array 
 
var count = 0; //var where to leave result 
 
for (;i>0 && str[i] === '0';i--){ 
 
\t count++; 
 
} 
 
console.log(count)