Das Zählen von nachgestellten Nullen von Zahlen resultierte aus Fakultät

Question

Ich versuche, nachgestellte Nullen von Zahlen zu zählen, die von faktorials resultieren (was bedeutet, dass die Zahlen ziemlich groß werden). Der folgende Code nimmt eine Zahl an, berechnet die Fakultät der Zahl und zählt die abschließenden Nullen. Wenn die Zahl jedoch ungefähr so ​​groß wie 25 ist, funktionieren NumZeros nicht.

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

Ich bin keine Sorgen über die Effizienz dieses Codes, und ich weiß, dass es mehr Möglichkeiten, besser ist die Effizienz dieses Codes zu machen. Was ich herausfinden will, ist der Grund, warum die nachgestellten Nullen von Zahlen, die größer als 25 sind, gezählt werden! funktioniert nicht.

Irgendwelche Ideen?

Answer 1

Ihre Aufgabe ist es nicht die Fakultät aber die Anzahl der Nullen zu berechnen. Eine gute Lösung verwendet die Formel von http://en.wikipedia.org/wiki/Trailing_zeros (die Sie können versuchen, zu beweisen)

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 

Hoffe, dass Sie diese auf Java übersetzen. Dies berechnet einfach [n/5] + [n/25] + [n/125] + [n/625] + ... und stoppt, wenn der Teiler größer als n wird.

Verwenden Sie KEINE BigIntegers. Dies ist ein Bozosort. Solche Lösungen benötigen Sekunden für große Zahlen.

Answer 2

Sie müssen nur wirklich wissen, wie viele 2s und 5s es in dem Produkt gibt. Wenn Sie nachgestellte Nullen zählen, dann zählen Sie tatsächlich "Wie oft teilen zehn diese Zahl?". wenn du n repräsentierst! als q * (2^a) * (5^b), wobei q nicht durch 2 oder 5 teilbar ist. Wenn Sie dann nur das Minimum von a und b im zweiten Ausdruck nehmen, erhalten Sie die Anzahl der 10 Teile. Eigentlich ist die Multiplikation Overkill.

Edit: Zählen der Zweien ist auch Overkill, so dass Sie nur die Fünfer wirklich brauchen.

Und für einige Python, ich denke, das sollte funktionieren:

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

Answer 3

Sie eine DecimalFormat große Zahlen zu formatieren können. Wenn Sie Ihre Nummer auf diese Weise formatieren, erhalten Sie die Nummer in scientific notation, dann wird jede Nummer wie 1.4567E7 sein, dies wird Ihre Arbeit viel einfacher machen. Weil die Zahl nach dem E - die Anzahl der Zeichen hinter dem. sind die Anzahl der abschließenden Nullen, denke ich.

Ich weiß nicht, ob dies das genaue Muster ist, das benötigt wird. Sie können sehen, wie die Muster here

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

Answer 4

Der doppelte Typ beschränkt ist, Präzision bilden, so dass, wenn sie die Zahlen mit zu groß bekommen arbeiten die doppelte nur eine Annäherung sein wird. Um dies zu umgehen, können Sie etwas wie BigInteger verwenden, um es für beliebig große Ganzzahlen zu verwenden.

Answer 5

Javas Doppel maximal bei etwas über 9 * 10^18 wo als 25! ist 1,5 * 10^25. Wenn Sie in der Lage sein wollen, factorials so hoch zu haben, können Sie BigInteger verwenden (ähnlich BigDecimal, aber keine Dezimalstellen).

Answer 6

Ich schrieb das sehr schnell, ich denke es löst Ihr Problem genau. Ich habe die BigInteger-Klasse verwendet, um zu vermeiden, dass die Umwandlung von Double zu Integer könnte Ihnen Probleme verursachen. Ich habe es an mehreren großen Zahlen über 25 getestet, z. B. 101, die genau 24 Nullen zurückgegeben haben.

Die Idee hinter der Methode ist, dass wenn Sie 25 nehmen! dann ist die erste Berechnung 25 * 24 = 600, also kannst du sofort zwei Nullen abklopfen und dann 6 * 23 = 138 machen. Also berechnet es das faktorielle Entfernen von Nullen, wie es geht.

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

Da Sie sagen, Sie überhaupt über die Laufzeit nicht kümmern (nicht, dass mein erstes war besonders effizient, nur etwas mehr so) dieser tut nur das faktorielle und zählt dann die Nullen, es ist so cenceptually einfacher :

Answer 7

Meine 2 Cent: Vermeiden Sie, doppelt zu arbeiten, da sie fehleranfällig sind. Ein besserer Datentyp ist in diesem Fall BigInteger, und hier gibt es eine kleine Methode, die Ihnen helfen:

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

Dies ist, wie ich gemacht, aber mit größer> 25 faktorielles die lange Kapazität nicht ausreicht, und sollte die Klasse BigInteger, ich bin nicht vertraut noch mit Hexe verwendet werden :)

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

Die besten mit logarithmische Zeitkomplexität ist die folgende:

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

schamlos kopiert von http://www.programcreek.com/2014/04/leetcode-factorial-trailing-zeroes-java/

Answer 10

ich das gleiche Problem in Javascript zu lösen hatte, und ich s olved es mag:

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 

Diese Lösung die Anzahl der Nullen gibt.

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)