一道笔试题，毫无思路，求高人指点~

Question

估算50000的阶乘的数量级？

Answer 1

int n =; 
int sum = 1; if (n < 0) 
{ 
System.out.println("n is overflow"); 
return ; 
} 
else if (n == 0) 
{ 
n = 0; 
} 
else { 
for (int i = 1; i < n ; i ++) 
{ 
sum = sum * i; 
if(sum>50000)
输出n
当然可以int型放不下那么大，但思路是这样的
} 

Answer 2

楼主是去应聘 数学应用类 还是 科学计算类 的职位么？请参见 斯特灵公式（取n阶乘近似值的数学公式）：
http://zh.wikipedia.org/wiki/%E6%96%AF%E7%89%B9%E6%9E%97%E5%85%AC%E5%BC%8F

Answer 3

应聘的Java工程师，这算是一道智力题吧，原题就是那样写的，没有别的条件了。
祝大家中秋节快乐！

Answer 4

所谓的“数量级”指的是什么？Stirling 公式的精度不差的！
如果要数量级的话，Stirling 公式可以获得，算法效率 O(1)
如果需要更高精度的话，可以使用 log 法计算，算法效率 O(N)
如果需要精确值的话，那就看你的数学功底了，以及归纳能力了下面是 Stirling 公式和 log 法的代码，计算非精确值的话是瞬间秒杀！public class Test {    public static void main(String[] args) {
        stirlingFactorial(50000);
        logFactorial(50000);
    }    /**
     * Stirling:
     * n! = sqrt(2 * pi * n) * pow(n / e, n)
     * @param n
     */
    public static void stirlingFactorial(int n) {
        double a = n * Math.log10(n / Math.E);
        double s = 0.5 * Math.log10(2 * Math.PI * n);
        double base10 = a + s;
        int exponent = (int)base10;
        double base = Math.pow(10, base10 - exponent);
        System.out.println(n + "! = " + base + " * 10^" + exponent);
    }    /**
     * n! = 1 * 2 * 3 * ... * (n - 1) * n
     * log(n!) = log(1) + log(2) + log(3) + ... + log(n - 1) + log(n)
     * @param n
     */
    public static void logFactorial(int n) {
        double sum = 0;
        for(int i = 1; i <= n; i++) {
            sum += Math.log10(i);
        }
        int exponent = (int)sum;
        double base = Math.pow(10, sum - exponent);
        System.out.println(n + "! = " + base + " * 10^" + exponent);
    }
}上面程序输出：Stirling 公式
50000! = 3.347314930703388 * 10^213236log 法
50000! = 3.3473205027452186 * 10^213236

Answer 5

精确值的话，我截取了前 1000 位：33473205095971448369154760940714864779127732238104
54807730100321990168022144365641697381231071916930
87984804381902082998936163847430666937426305728453
63784038325756282123359987268244078235972356040853
85444137338375356856553637116832740516607615516592
14061560754612942017905674796654986292422200225415
53510718159801615476451810616674970217996537474972
54113933819163882350063030764425687485727139465108
19098749096434862685892298078700310310089628611545
53979911612940652327396971497211031261142860733793
50968783735581183060955172890660383359253285163596
17308852798119573994952994503063544424784926410289
90069559634883529900557676550929175475920788044807
62256241516513045904631806851740676636001232955645
40657242251754734281831210291957155937874236411171
94513838593038006413132976312508980623953869845352
83626745909739251873477917386980548744182185648438
50349196433374384607147670018127809768669571553722
96285550289272206781394438418019284262150410723283
83318031478197026786795372029783990819120751438532精确值的话可以看看下面的代码，在 Intel Core Duo T8100 / 2.1GHz 上计算 50000 的阶乘需要 3.167s这段代码我经过很长时间的调优，基本的算法是这样的：从上图可以看出，把所有的奇数提出来，先计算奇数的乘积，从右边开始算，右边的计算结果可以为其左边的乘积作缓存从而提高运算效率。偶数 2 的冪在所有的奇数计算完成后使用二进制左位位就可以了。参考代码如下：import java.math.BigInteger;public class Test {    public static void main(String args[]) {
        long t1, t0 = System.currentTimeMillis();
        BigInteger bi = factorial(50000);
        t1 = System.currentTimeMillis();
        System.out.printf("time: %.3fs%n", (t1 - t0) / 1000.0);
        String str = bi.toString();
        output(str, 50);
    }    public static BigInteger factorial(int n) {
        if(n < 2) {
            return BigInteger.ONE;
        }
        int[] oddCount = new int[Integer.numberOfTrailingZeros(Integer.highestOneBit(n))];
        int shift = init(oddCount, n);
        BigInteger result = BigInteger.ONE;
        BigInteger bg = BigInteger.ONE;
        BigInteger tmp = BigInteger.ONE;        int max = oddCount[oddCount.length - 1];
        int offset = (oddCount[0] + 1) & 1;
        int oddStart = 1;
        while(oddStart <= max) {
            tmp = tmp.multiply(new BigInteger(String.valueOf(2 * oddStart + 1)));
            if(oddCount[offset] == oddStart) {
                offset++;
                bg = bg.multiply(tmp);
                tmp = BigInteger.ONE;
                result = result.multiply(bg);
            }
            oddStart++;
        }
        return result.shiftLeft(shift);
    }    private static int init(int[] oddCount, int n) {
        int s = n;
        int r = 0;
        int k = oddCount.length;
        while(k > 0) {
            s >>= 1;
            oddCount[--k] = n - s - 1;
            n = s;
            r += s;
        }
        return r;
    }    private static void output(String str, int lineLength) {
        char[] chs = str.toCharArray();
        int offset = 0;
        while (offset < chs.length) {
            int max = Math.min(chs.length - offset, lineLength);
            System.out.println(new String(chs, offset, max));
            offset += max;
        }
    }
}上述代码中的 output 是故意加上去的，否则一个长度为 20 多万个字符的字符串光输出就会把你的电脑给搞死。虽然计算只花了 3.167 秒，但是将计算结果转换为字符串的 toString 花了 19 秒。

Answer 6

如果是应聘非数学工作的话，那么是脑筋急转弯么？这个题如果不查资料的话，只能硬算，是考你知不知道BigInteger类？
还是考官脑子有问题？

Answer 7

我晕，被人抢先了。在下想贴的就是log法的说。