Подсчет числа нулей чисел, полученных от factorial

Question

Я пытаюсь подсчитать конечные нули чисел, которые получены из факториалов (что означает, что числа становятся довольно большими). Следующий код принимает число, вычисляет факториал числа и подсчитывает конечные нули. Однако, когда число составляет около 25!, NumZeros не работают.

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; 
} 

Я не беспокоиться об эффективности этого кода, и я знаю, что есть несколько способов, чтобы сделать эффективность этого кода ЛУЧШЕ. То, что я пытаюсь понять, - это то, что подсчет завершающих нулей чисел больше 25! не работает.

Любые идеи?

Answer 1

Ваша задача состоит в том, чтобы не вычислить факториал, но число нулей. Хорошее решение использует формулу из http://en.wikipedia.org/wiki/Trailing_zeros (который вы можете попытаться доказать)

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 

Надеется, что вы можете перевести это на Java. Это просто вычисляет [n/5] + [n/25] + [n/125] + [n/625] + ... и останавливается, когда делитель становится больше n.

НЕ используйте BigIntegers. Это бозосорт. Для таких решений требуются секунды времени для больших чисел.

Answer 2

Вам действительно нужно знать, сколько 2s и 5s есть в продукте. Если вы считаете завершающие нули, то вы на самом деле считаете «Сколько раз десять делят это число?». если вы представляете n! как q * (2^a) * (5^b), где q не делится на 2 или 5. Тогда простое взятие минимума a и b во втором выражении даст вам, сколько раз 10 делит число. Фактически выполнение умножения является излишним.

Редактировать: подсчет двойки также является излишним, поэтому вам действительно нужны только пятеро.

И для некоторого питона, я думаю, что это должно работать:

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

Answer 3

Вы можете использовать DecimalFormat для форматирования больших чисел. Если вы отформатируете свой номер таким образом, вы получите номер в scientific notation, тогда каждый номер будет как 1.4567E7, это сделает вашу работу намного проще. Потому что число после E - количество символов позади. Я думаю, это число конечных нулей.

Я не знаю, нужен ли этот точный шаблон. Вы можете увидеть, как формировать шаблоны here

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

Answer 4

Двойной тип имеет ограниченную точность, поэтому, если эти номера вы работаете с получаете слишком большой двойной будет лишь приблизительным. Чтобы обойти это, вы можете использовать что-то вроде BigInteger, чтобы заставить его работать с произвольно большими целыми числами.

Answer 5

Java удваивает максимальную длину чуть более 9 * 10^18, где 25! 1.5 * 10^25. Если вы хотите иметь факториалы, которые могут быть высокими, вы можете захотеть использовать BigInteger (аналогично BigDecimal, но не делает десятичных знаков).

Answer 6

Я написал это очень быстро, я думаю, что он решает вашу проблему точно. Я использовал класс BigInteger, чтобы избежать этого приведения от двойного к целому числу, которое могло бы вызвать проблемы. Я тестировал его на нескольких больших количествах более 25, таких как 101, которые точно вернули 24 нули.

Идея метода заключается в том, что если вы возьмете 25! то первое вычисление составляет 25 * 24 = 600, поэтому вы можете сразу же отбросить два нуля и затем сделать 6 * 23 = 138. Таким образом, он вычисляет факториальные удаляющие нули по мере их поступления.

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; 
} 

Так как вы сказали, что вы не заботитесь о перспективе времени вообще (не то, что мой первый был особенно эффективен, только немного больше) это один раз делает факториал, а затем подсчитывает нули, так что cenceptually проще :

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

Мои 2 цента: избегайте работать с двойным, поскольку они подвержены ошибкам. Лучше тип данных в этом случае BigInteger, и здесь есть небольшой метод, который поможет вам:

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

Это, как я это сделал, но больше> 25 факторных длинные емкости недостаточно и следует использовать класс BigInteger, с ведьмой я знаком еще нет :)

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

Лучшего с логарифмическая временная сложность заключается в следующем:

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; 
} 

бесстыдно скопирована с http://www.programcreek.com/2014/04/leetcode-factorial-trailing-zeroes-java/

Answer 10

Я была такая же проблема, чтобы решить в Javascript, и я S olved это как:

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 

Это решение дает вам количество завершающих нулей.

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)