用Java實現大數階乘
隨著計算機硬件的不斷升級，大數計算已不再是問題。但在某些場合下，我們還是需要自己編寫程序來處理大數計算問題。比如在一些面試題中，可能會涉及到大數階乘的計算問題。本文將介紹使用Java來實現大數階乘的方
隨著計算機硬件的不斷升級，大數計算已不再是問題。但在某些場合下，我們還是需要自己編寫程序來處理大數計算問題。比如在一些面試題中，可能會涉及到大數階乘的計算問題。本文將介紹使用Java來實現大數階乘的方法。
計算Java提供的數據類型可以處理的最大范圍
在開始介紹大數階乘的具體實現前，我們需要先了解一下Java提供的數據類型可以處理的數據范圍。Java中提供了兩種基本數據類型：int和long。它們分別占用4個字節和8個字節。它們所能表示的數值范圍如下：
- int：-2,147,483,648 ~ 2,147,483,647，最多可計算12的階乘。
- long：-9,223,372,036,854,775,808 ~ 9,223,372,036,854,775,807，最多可計算20的階乘。
如果我們要計算更大范圍的數字的階乘（例如50的階乘），就需要使用自定義的數字類型來表示這個數字了。
使用鏈表表示法自定義數字類型
為了表示一個大數，我們可以使用鏈表的方式，將每一位數字從低到高存儲到鏈表中。如下所示：
數字：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) {
val;
}
// 重新 toString 方法，方便最后輸出整個鏈表
@Override
public String toString() {
StringBuilder b new StringBuilder();
(val);
ListNode nextNode next;
while (null ! nextNode) {
(",").append();
nextNode ;
}
return ();
}
}
實現大數相乘
在實現大數階乘之前，我們需要先掌握如何實現大數相乘。我們可以把一個大于等于10的數字拆分為多個小于10的數字，然后對每個小數字分別進行計算，最后將它們的結果相加。具體步驟如下：
- 將數字進行拆分，將一個大于等于10的數字，拆分為多個小于10的數字。
- 將每一個小于10的數字和我們的大數相乘。
- 將相乘的結果進行累加，即得到最終結果。
拆分數字的具體實現可以參考下面的代碼：
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;
}
實現大數相乘的代碼如下：
private ListNode multipleSingleNum(ListNode ln, int num) {
ListNode result new ListNode(0);
ListNode currentNode result;
int carryBit 0; // 進位
while (null ! ln) {
int mVal * num carryBit;
carryBit mVal / 10;
mVal mVal % 10;
ListNode theNode new ListNode(mVal);
theNode;
currentNode ;
ln ;
}
// 注意最后要看看是否還有有效的進位沒有處理
if (carryBit > 0) {
new ListNode(carryBit);
}
return ;
}
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;
}
當兩個大數長度不一致時，我們可以在短的那條大數前補0，使它與另一個大數長度一樣。具體實現可以參考下面的代碼：
private ListNode addTwoNumbers(ListNode l1, ListNode l2) {
int firstNodeVal ;
int carryBit firstNodeVal / 10; // 進位
firstNodeVal firstNodeVal % 10; // 當前位的值
ListNode result new ListNode(firstNodeVal); // 最后的計算結果
ListNode computePoint result; // 指向當前的計算節點
l1 ; // 移到下一個節點
l2 ; // 移到下一個節點
while (null ! l1 || null ! l2) {
int l1Val null l1? ;
int l2Val null l2? ;
int sum l1Val l2Val carryBit; // 計算和，要加上進位
carryBit sum / 10; // 重新計算進位
sum sum % 10; // 當前位的和
new ListNode(sum);
computePoint ; // 移到下一個節點
l1 null l1? ; // 移到下一個節點
l2 null l2? ; // 移到下一個節點
}
// 如果最后進位有結余，則需要將其設置到新節點中
if (carryBit > 0) {
new ListNode(carryBit);
}
return result;
}
測試
我們分別計算10、20、50的階乘，并驗證運行結果是否正確。具體代碼如下：
public static void main(String[] args) {
Solution solution new Solution();
int n1 10;
ListNode result1 solution.factorial(n1);
(n1 "! " ());
int n2 20;
ListNode result2 solution.factorial(n2);
(n2 "! " ());
int n3 50;
ListNode result3 solution.factorial(n3);
(n3 "! " ());
}
輸出結果如下：
10! 3628800
20! 2432902008176640000
50! 30414093201713378043612608166064768844377641568960512000000000000
以上就是使用Java實現大數階乘的方法。通過使用鏈表表示法和自定義的大數計算方法，我們可以輕松地處理大數計算問題，并得到準確的結果。