Inkonsistente Ergebnisse beim Suchen von faktoriellem Nullpunkt

Question

Hier sind zwei Versionen von Code, den ich schreibe, um die Anzahl der abschließenden Nullen in n zurückzugeben. Die erste Version gibt 452137080 für den Eingang 1808548329 zurück, die zweite Version gibt 452137076 für den Eingang 1808548329 zurück. Fragst du dich, warum es einen Unterschied gibt? Die Ausgabe von der 2. Version ist korrekt.

Quellcode in Java,

public class TrailingZero { 
    public static int trailingZeroes(int n) { 
     int result = 0; 
     int base = 5; 
     while (n/base > 0) { 
      result += n/base; 
      base *= 5; 
     } 

     return result; 
    } 

    public static int trailingZeroesV2(int n) { 
     return n == 0 ? 0 : n/5 + trailingZeroesV2(n/5); 
    } 

    public static void main(String[] args) { 
     // TODO Auto-generated method stub 
     System.out.println(trailingZeroes(1808548329)); 
     System.out.println(trailingZeroesV2(1808548329)); 
    } 
} 

Answer 1

Dies ist auf integer overflow im Wert von base.

Ändern Sie den Code leicht drucken zu n/base und base:

public class TrailingZero { 
    public static int trailingZeroes(int n) { 
     int result = 0; 
     int base = 5; 
     while (n/base > 0) { 
      System.out.println("n = " + n/base + " base = " + base); 
      result += n/base; 
      base *= 5; 
     } 

     return result; 
    } 

    public static int trailingZeroesV2(int n) { 
     return n == 0 ? 0 : n/5 + trailingZeroesV2(n/5); 
    } 

    public static void main(String[] args) { 
     // TODO Auto-generated method stub 
     System.out.println(trailingZeroes(1808548329)); 
     System.out.println(trailingZeroesV2(1808548329)); 
    } 
} 

Ausgang:

n = 361709665 base = 5 
n = 72341933 base = 25 
n = 14468386 base = 125 
n = 2893677 base = 625 
n = 578735 base = 3125 
n = 115747 base = 15625 
n = 23149 base = 78125 
n = 4629 base = 390625 
n = 925 base = 1953125 
n = 185 base = 9765625 
n = 37 base = 48828125 
n = 7 base = 244140625 
n = 1 base = 1220703125 
n = 1 base = 1808548329 <== OOPS 6103515625 overflows 32-bit integer 
n = 3 base = 452807053 
452137080 

Wie man hier sehen kann, base steigt auf 1220703125, wenn n = 1. Dann werden die Anweisung base *= 5 läuft Das macht es 6103515625, die das Maximum 32-Bit unsigned int (2^32) von genauüberschwingt, und das ist, was Sie als der falsche Zwischenwert von b oben sehen (OOPS). Die rekursive Lösung verwendet dagegen nur den Wert n, der kontinuierlich abnimmt. Daher gibt es keinen Überlauf.

Die einfache Lösung besteht darin, base als lang zu deklarieren, d. H. long base = 5. Das wird den richtigen Wert von 452137076 zurückgeben.

wird eine andere Lösung sein, die Schleife zu ändern, um nur n, ähnlich wie die rekursive Lösung zu verwenden:

int base = 5; 
    while (n > 0) { 
     result += n/base; 
     n = n/base; 
    } 

Beachten Sie, dass factorials in Problemen im Zusammenhang, einen Überlauf gegeben und Sie können höhere Genauigkeit Arithmetik betrachten wollen wie BigInteger.