java - 如何减少查找数字阶乘的最后一个非零数字的运行时间？

Question

我有一个问题，我必须找到一个数字的阶乘的最后一个非零数字。我对 Java 和 C 使用了相同的代码，但两者花费的时间不同。

int lastDigitDiffZero(long n) {

     int dig[] = {1, 1, 2, 6, 4, 2, 2, 4, 2, 8};
     int i=(int) n;

     if (n < 10)
       return dig[i]; 

     if (((n/10)%10)%2 == 0)
       return (6*lastDigitDiffZero(n/5)*dig[(int)n%10]) % 10;
     else
       return (4*lastDigitDiffZero(n/5)*dig[(int)n%10]) % 10;
}

我想知道为什么需要不同的时间，我应该怎么做才能减少运行时间？

Answer 1

请查找优化版本:

private static final int DIG[] = { 1, 1, 2, 6, 4, 2, 2, 4, 2, 8 };

static int lastDigitDiffZero(long n) {
        if (n < 10)
            return DIG[(int) n];
        int t1 = (int) (n % 10);
        int t2 = lastDigitDiffZero(n / 5) * DIG[t1];
        if (((n / 10) % 10) % 2 == 0) {
            return (6 * t2) % 10;
        } else
            return (4 * t2) % 10;
}