Java中用ArrayList類實現正整數大數相加與相乘

在C語言中我們經常用數組處理大數問題，在java中數組功能逐漸被ArrayList類代替，強大的ArrayList類提供了clear()，equals()等32個方法，所以我們能輕松實現各種類的構造，以下代碼將提供VeryLongInt類的設計：

1. import java.util.ArrayList;  
2. import java.util.Collections;  
3.   
4. class VeryLongInt{  
5.     ArrayList digits;                          //digits字段，存放大數的各位數字   
6.     public VeryLongInt(){  
7.         final int INITIAL_CAPACITY = 500;  
8.         this.digits = new ArrayList(INITIAL_CAPACITY);  
9.     };//無參構造   
10.       
11.     public VeryLongInt(String s){  
12.         this.digits = new ArrayList(s.length());  
13.         for(int i =0; i<s.length();i++){  
14.             char c=s.charAt(i);  
15.             if(c>='0' && c<='9'){  
16.                 this.digits.add(new Integer(c - '0'));  
17.             }  
18.         }  
19.     };//含參構造   
20.       
21.     public String toString(){  
22.         StringBuffer s = new StringBuffer("");  
23.         for(int i=0;i<this.digits.size();i++)  
24.             s.append(this.digits.get(i));  
25.         return s.toString();  
26.     }//將大數轉為字符串形式   
27.       
28.     public void add(VeryLongInt otherVeryLong){  
29.         int largerSize,partialSum,carry=0;  
30.         VeryLongInt sum = new VeryLongInt();  
31.         largerSize = this.digits.size()>otherVeryLong.digits.size() ? this.digits.size():otherVeryLong.digits.size();  
32.         for(int i=0;i<largerSize;i++){  
33.             partialSum = this.least(i)+otherVeryLong.least(i)+carry;  
34.             carry = partialSum / 10;  
35.             sum.digits.add(new Integer(partialSum%10));  
36.         }  
37.         if (carry == 1)  
38.             sum.digits.add(1);  
39.         Collections.reverse(sum.digits);    //反轉sum   
40.         this.digits.clear();  
41.         this.digits = sum.digits;  
42.     }//大數加法   
43.       
44.     public void mult(VeryLongInt otherVeryLong){  
45.         int i = 1;  
46.         if(((Integer)otherVeryLong.digits.get(0)).intValue()==0){  
47.             this.digits.clear();  
48.             this.digits.add(0);  
49.             return ;  
50.         }  
51.         VeryLongInt sum = new VeryLongInt("1");  
52.         VeryLongInt mult = new VeryLongInt(this.toString());  
53.         while(!sum.equal(otherVeryLong)){  
54.             this.add(mult);  
55.             sum.add(new VeryLongInt("1"));  
56.         }  
57.     }//任意大數與單個數字相乘   
58.       
59.     public void multiply(VeryLongInt otherVeryLong){  
60.         int length = otherVeryLong.digits.size();  
61.         VeryLongInt multiply;  
62.         VeryLongInt multiplycopy = new VeryLongInt(this.toString());  
63.         this.digits.clear();  
64.         this.digits.add(0);  
65.         for(int i=0;i<length;i++ ){  
66.             multiply =  new VeryLongInt(multiplycopy.toString());  
67.             multiply.mult(new VeryLongInt((otherVeryLong.digits.get(i)).toString()));  
68.             for(int j=1;j<length-i;j++)  
69.                 multiply.digits.add(0);  
70.             this.add(multiply);  
71.         }  
72.     }//大數與大數相乘   
73.       
74.     public int least(int i ){  
75.         return i>=this.digits.size()?0:((Integer)this.digits.get(this.digits.size()-i-1)).intValue();  
76.     }//返回從低位到高位第i位數字   
77.       
78.     public boolean equal(VeryLongInt v1){  
79.         if (this.digits.size()!=v1.digits.size())  
80.             return false;  
81.         int length = this.digits.size();  
82.         for(int i=length-1;i>=0;i--){  
83.             if (((Integer)this.digits.get(i)).intValue()!=((Integer)v1.digits.get(i)).intValue())  
84.                 return false;  
85.         }  
86.         return true;  
87.     }//判斷兩大數是否相等   
88.       
89. }  
90. public class ArrListDemo{  
91.     public static void main(String args[]){  
92.         VeryLongInt str1 = new VeryLongInt("11114532632462523462362547457357");  
93.         str1.add(new VeryLongInt("0"));  
94.         System.out.println(str1.toString());  
95.         str1.multiply(new VeryLongInt("333333462462346234452643634247"));  
96.         System.out.println(str1.toString());  
97.     }  
98. }  

output：

11114532632462523462362547457357
3704845646029468841285610955774783288521573545337081737305179

附幾點ArrayList類與數組的幾點區別：

1，當構造數組時必須指定初始容量，但是ArrayList不需要，ArrayList類提供了三種構造方法，以便於你選擇是否需要指定初始容量。

2，在數組中插入元素時，必須指定索引值，而在ArrayList類中的add()方法則自動選擇在ArrayList對象的末尾插入元素。

3，ArrayList類中的size()方法返回ArrayList對象中元素個數，而數組中的length字段則保存了數組可以插入的元素的最大值。

4，ArrayList類中的set()方法可以更改指定索引位置的元素，類似與數組中的直接賦值。

5，ArrayList類中的remove()方法可以刪除指定索引位置的元素，而且時間復雜度為O(1)，而數組中實現這一功能則需要移動所刪元素的後半段空間。

6，在數組中查找是否具有某一元素需要進行顯式搜索，而在ArrayList類中只需一個indexOf()方法即可搞定。

當然，數組在一些地方依然有著ArrayList類無法替代的位置：

1，索引運算符可以用來訪問或者修改數組中的元素。

eg：a[i]=a[j+1];

2，數組可以在構造的時候進行初始化。

eg：String []a = {"a","b","c"};

3，我們可以在數組的任意索引位置存儲元素，但是對於ArrayList對象，只能在索引值為0、1、....、size()的位置存儲元素。

4，可以創建任意類型（甚至是原始類型，例如int）的數組。對於ArrayList對象，每個元素的類型必須是Object或其子類。