Java实现50的阶乘（Java大数阶乘的实现）
1、我们先来看看如果通过Java提供的数值类型来计算阶乘，最多能计算到多大数字：
1. 使用 int ，其由 4 个字节表示，数值范围为 : -2147483648 至 2147483647， 最多计算到 12 的阶乘
2. 使用 long , 其由 8 个字节表示，数值范围为 -9223372036854775808 至 9223372036854775807， 最多计算到 20 的阶乘
看样，如果通过java原始的数据类型来计算阶乘，最多能计算到20，如果要计算更大数字的阶乘（比如50），那该如何表示呢？
2、使用自定义数字类型，这里使用链表表示法，即对于一个数字，将每一个数值位从低到高放到一个链表中来表示，示例如下 (注意目前我们只处理正数)：
数字: 1234 链表表示为：1->2->3->4
数字: 788996 链表表示为：7->8->8->9->9->6
对于其Java代码实现，我们定义一个链表节点类：
// 其以一个静态内部类的形式存在
private static class ListNode {
int val; // 链表节点的值
ListNode next; // 下一个节点
public ListNode(int val) {
this.val = val;
}
// 重新 toString 方法，方便最后输出整个链表
@Override
public String toString() {
StringBuilder b = new StringBuilder();
b.append(val);
ListNode nextNode = next;
while(null != nextNode) {
b.append(",").append(nextNode.val);
nextNode = nextNode.next;
}
return b.toString();
}
}
3、如何表示一个大数，我们已经有了具体方案，对于阶乘而言，就是不断让这个大数和一个数字相乘，即 ListNode * n , 这里的乘法该如何计算呢？我们先实现最简单的情况，那就是 n<10 这种情况（即你是单位数），代码如下（注意进位的处理）：
/**
* 对于这个方法，num<10
* @param ln 大数，非空
* @param num
* @return
*/
private ListNode multipleSingleNum(ListNode ln, int num) {
ListNode result = new ListNode(0);
ListNode currentNode = result;
int carryBit = 0; // 进位
while(null != ln) {
int mVal = ln.val * num + carryBit;
carryBit = mVal/10;
mVal = mVal%10;
ListNode theNode = new ListNode(mVal);
currentNode.next = theNode;
currentNode = currentNode.next;
ln = ln.next;
}
// 注意最后要看看是否还有有效的进位没有处理
if(carryBit > 0) {
currentNode.next = new ListNode(carryBit);
}
// 返回结果
return result.next;
}
4、那么对于更大数字（n>=10）的相乘该如何进行呢？我们可以把n拆一下，再参与计算，即：
ListNode * n = ListNode * (n1 + n2 + n3...) = ListNode * n1 + ListNode *n2 + ListNode * n3 .... 其中：n 大于等于10, 拆分的 n1 n2 n3 均小于10
我们先实现这个拆分方法：
/**
* 拆分数字，将一个大于等于10的数字，拆分为多个小于10的数字
* @param num
* @return
*/
private int[] scatterNumber(int num) {
// 注意要除以9.0, 否则两个整数相除一定返回一个整数
int resultLength = (int)Math.ceil(num/9.0);
int[] result = new int[resultLength];
int index = 0;
while(num >= 10) {
result[index] = 9;
num = num - 9;
index++;
}
if(num > 0) {
result[index] = num;
}
return result;
}
5、我们利用上述两步构造一个普遍适用的大数相乘的方法，代码如下：
private ListNode multipleNumber(ListNode ln, int num) {
// 将数字进行拆分
int[] allUsedNums = scatterNumber(num);
ListNode result = new ListNode(0);
for(int usedNum : allUsedNums) {
// 将每一个小于10的数字和我们的大数相乘
ListNode mulResult = multipleSingleNum(ln, usedNum);
// 将相乘的结果进行累加
result = addTwoNumbers(result, mulResult);
}
return result;
}
6、上述步骤中，数字拆分相乘后会返回多个独立的大数 ListNode， 我们调用了 addTwoNumbers 实现结果累加，具体代码如下（整个过程其实就是对齐相加，注意进位的处理）：
private ListNode addTwoNumbers(ListNode l1, ListNode l2) {
int firstNodeVal = l1.val + l2.val;
int carryBit = firstNodeVal/10; // 进位
firstNodeVal = firstNodeVal%10;
ListNode result = new ListNode(firstNodeVal); // 最后的计算结果
ListNode computePoint = result; // 指向当前的计算节点
l1 = l1.next; // 移到下一个节点
l2 = l2.next; // 移到下一个节点
while(null != l1 || null != l2) {
int l1Val = null == l1?0:l1.val;
int l2Val = null == l2?0:l2.val;
int sum = l1Val + l2Val + carryBit; // 计算和，要加上进位
carryBit = sum/10; // 重新计算进位
sum = sum%10; // 当前位的和
computePoint.next = new ListNode(sum);
computePoint = computePoint.next;
l1 = null == l1?null:l1.next;
l2 = null == l2?null:l2.next;
}
// 如果最后进位有结余，则需要将其设置到新节点中
if(carryBit > 0) {
computePoint.next = new ListNode(carryBit);
}
return result;
}
7、测试，我们分别计算 10, 20，50 的阶乘，计算结果如图示。
