Factorial Trailing Zeroを見つけたときに矛盾した結果が発生しました

Question

nに後続ゼロの数を返すために書き込むコードは2つあります。最初のバージョンは入力1808548329に対して452137080を返し、2番目のバージョンは入力1808548329に対して452137076を返します。なぜ違いがあるのだろうか？第2版​​の出力は正しいです。 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

これはbaseの値でinteger overflowによるものです。

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

出力：：n/baseとbase印刷するには、わずかにあなたのコードを変更する

あなたがここに見ることができるように

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 

を、1220703125からbase増加し、ときn = 1 Thenステートメントbase *= 5実行それは6103515625となり、最大32ビットの符号なし整数（2^32）を正確にだけオーバーシュートしますであり、これは中間の間違った値b（OOPS）として表示されます。

一方、再帰的解は、連続的に減少するnの値のみを使用します。したがって、オーバーフローはありません。

簡単な解決策は、baseを長く指定することです（つまり、long base = 5）。それは452137076の正しい値を返します。

別の解決策は、再帰的なソリューションに似 n、使用のみにループを変更することになります

：階乗を含む問題で、オーバーフローが与えられていると、あなたがより高い精度の演算を検討する必要がありますことを

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

注意をBigIntegerなどです。