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 的阶乘，计算结果如图示。