【面试算法】Java求阶乘，高精度

题目描述
给定一个数N（0<=N<=10000），计算N！（要求高精度）

输入描述
多个测试数据，每次输入一个测试数据

输出描述
每组用一行输出N！

示例
输入

1
2
3

输出

1
2
6

思路：其实刚开始的时候，觉得这个题目很简单，但是发现这个题目真正考察的是高精度的计算！

首先得了解高精度的计算，其次要了解高精度计算中进位的处理应该是先做运算，然后再判断进位。(在java中直接使用api即可)

其次你要知道的是：
当你的传入待计算阶乘的值num大于16，阶乘结果就会超过int的最大值范围
num大于20，就会超出long的最大值范围，num大于20就要去使用大数操作。
还需注意的是：你超出20的那部分用大数计算，但是20以内的那部分还需要用long来计算。

java.math.BigInteger.multiply(BigInteger val) 返回一个BigInteger，其值是 (this * val)
a.multiply(b); 返回的是a*b

代码展示：

 //考虑了大数的情况

public static void main(String[] args){
        BigInteger x = factorial(30);
        System.out.println(x);
    }

    public static BigInteger factorial(int num) {
        if(num < 0) {
            throw new IllegalArgumentException("num must be signless integral.");
        }
        if(num < 2) {
            return BigInteger.ONE;
        }
        // 小于等于 16 时可以使用 int 进行计算
        if(num <= 16) {
            return intFractorial(num);
        }

        // 小于等于 20 时可以使用 long 进行计算
        if(num <= 20) {
            return longFractorial(num);
        }

        // 大于 20 时需要采用 BigInteger 进行计算
        return bigIntegerFactorial(num);
    }

    private static BigInteger intFractorial(int num) {
        int result = 1;
        while(num > 0) {
            result *= num--;
        }
        return BigInteger.valueOf(result);
    }

    private static BigInteger longFractorial(int num) {
        long result = 1L;
        while(num > 0) {
            result *= num--;
        }
        return BigInteger.valueOf(result);
    }

    private static BigInteger bigIntegerFactorial(int num) {
        BigInteger result = longFractorial(20);
        while(num > 20) {
            result = result.multiply(BigInteger.valueOf(num--));
        }
        return result;
    }

知识回顾：
阶乘的递归实现：

//递归实现
    public static long cal(int i){
        if (i == 1) {
            return 1;
        } else {
            return cal(i-1) * i;
        }
    }

阶乘的非递归实现：

public static long getFactorial(int num){
        long temp = 1;
        for(int i=1;i<=num;i++){
            temp *= i;
        }
        return temp;
    }

题目的C语言解答版本：

#include<iostream>
using namespace std;
const int length=100000;//这个值经过多次调整，才过了10000！

int main()
{
    int a[length];//定义一个数组来存储结果
    for(int i=0; i<length; i++)//将数组中所有元素置为0；
        a[i]=0;
    a[0] = 1;//首位置为1；
    int n;
    cin>>n;//输入要计算阶乘的数
    for(int i=2; i<=n; i++)
    {//开始计算阶乘
        int jinwei = 0;
        int j =0;
        int temp;
        while(j<length)
        {//考虑进位及进位的处理
            temp = jinwei;
            jinwei = (a[j]*i+jinwei)/10;
            a[j] = (a[j]*i + temp)%10;
            j++;
        }
    }
    int k=length-1;
    while(!a[k])
    {//将为0的数全跳过，不输出
        k--;
    }
    while(k>=0)
    {//输出正确的阶乘结果
        cout<<a[k];
        k--;
    }
    return 0;
}

解析：

jinwei = (a[j]*i+jinwei)/10;  保留的是进位
a[j] = (a[j]*i + temp)%10;  这个则是保留除进位之外的值
不理解的话，可以举个例子套进去试试看：假设n=3，那么
    (1*2+0)/10 = 0     进位为0 
    (1*2+0)%10 = 3     个位为3

使用BigDecimal进行精确运算(实现加减乘除运算)---熟悉api的使用

    /**
     * 提供精确加法计算的add方法
     * @param value1 被加数
     * @param value2 加数
     * @return 两个参数的和
     */
    public static double add(double value1,double value2){
        BigDecimal b1 = new BigDecimal(Double.valueOf(value1));
        BigDecimal b2 = new BigDecimal(Double.valueOf(value2));
        return b1.add(b2).doubleValue();
    }
    /**
     * 提供精确减法运算的sub方法
     * @param value1 被减数
     * @param value2 减数
     * @return 两个参数的差
     */
    public static double sub(double value1,double value2){
        BigDecimal b1 = new BigDecimal(Double.valueOf(value1));
        BigDecimal b2 = new BigDecimal(Double.valueOf(value2));
        return b1.subtract(b2).doubleValue();
    }

    /**
     * 提供精确乘法运算的mul方法
     * @param value1 被乘数
     * @param value2 乘数
     * @return 两个参数的积
     */
    public static double mul(double value1,double value2){
        BigDecimal b1 = new BigDecimal(Double.valueOf(value1));
        BigDecimal b2 = new BigDecimal(Double.valueOf(value2));
        return b1.multiply(b2).doubleValue();
    }

    /**
     * 提供精确的除法运算方法div
     * @param value1 被除数
     * @param value2 除数
     * @param scale 精确范围
     * @return 两个参数的商
     * @throws IllegalAccessException
     */
    public static double div(double value1,double value2,int scale) throws IllegalAccessException{
        //如果精确范围小于0，抛出异常信息
        if(scale<0){
            throw new IllegalAccessException("精确度不能小于0");
        }
        BigDecimal b1 = new BigDecimal(Double.valueOf(value1));
        BigDecimal b2 = new BigDecimal(Double.valueOf(value2));
        return b1.divide(b2, scale).doubleValue();
    }