當(dāng)計算超過20以上的階乘時，階乘的結(jié)果值往往會很大。一個很小的數(shù)字的階乘結(jié)果就可能超過目前個人計算機(jī)的整數(shù)范圍。如果需求很大的階乘，比如1000以上完全無法用簡單的遞歸方式去解決。在網(wǎng)上我看到很多用c、c++和c#寫的一些關(guān)于大整數(shù)階乘的算法，其中不乏經(jīng)典但也有很多粗糙的文章。數(shù)組越界，一眼就可以看出程序本身無法運(yùn)行。轉(zhuǎn)載他人文章的時候，代碼倒是仔細(xì)看看啊。唉，粗糙。過年了，在家閑來蛋疼，仔細(xì)分析分析，用java實現(xiàn)了一個程序計算超大整數(shù)階乘。思想取自網(wǎng)上，由我個人優(yōu)化和改進(jìn)。
這個方法采用“數(shù)組進(jìn)位”算法。在超越計算機(jī)變量取值范圍的情況下，將多位數(shù)相乘轉(zhuǎn)化為一位數(shù)相乘。如11！=39916800，若需求12的階乘，則需要將39916800與12相乘，可利用乘法分配率。乘法豎式如下圖所示：
使用一個數(shù)組來保存階乘每一位的結(jié)果，一個數(shù)組元素保存一位數(shù)。例如：將11的階乘的結(jié)果399
16800保存到數(shù)組的8個元素中，要計算12的階乘就用每個數(shù)組元素中的值去乘以12，并將結(jié)果保存到原來的數(shù)組元素中。接下來去判斷每個數(shù)組元素是否需要進(jìn)位，通過進(jìn)位操作使數(shù)組中的每個元素保存的數(shù)都只有一位數(shù)，示意圖如下：
理論上講，只要計算機(jī)內(nèi)存空間允許就可以保存任意多位的階乘結(jié)果，不再受變量的取值范圍的限制，只受到操作系統(tǒng)的尋址能力和計算機(jī)內(nèi)存的限制。友情提示：如果要求的階乘數(shù)字很大則可以將數(shù)組定義為long類型，以避免在計算單位數(shù)的乘積時出現(xiàn)溢出的情況。
實現(xiàn)代碼如下：
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
|
public class biginteger { /** * 計算進(jìn)位 * @param bit 數(shù)組 * @param pos 用于判斷是否是數(shù)組的最高位 */ private void carry(int[] bit, int pos) { int i ,carray = 0; for (i = 0 ; i<= pos ;i++)//從0到pos逐位檢查是否需要進(jìn)位 { bit[i] += carray; //累加進(jìn)位 if(bit[i] <= 9) //小于9不進(jìn)位 { carray = 0; } else if(bit[i] >9 && i<pos)//大于9，但不是最高位 { carray = bit[i]/10; //保存進(jìn)位值 bit[i] = bit[i]%10; //得到該位的一位數(shù) } else if(bit[i] > 9 && i >= pos)//大于9，且是最高位 { while(bit[i] > 9)//循環(huán)向前進(jìn)位 { carray = bit[i]/10; //計算進(jìn)位值 bit[i] = bit[i] % 10; //當(dāng)前的第一位數(shù) i ++ ; bit[i] = carray; //在下一位保存進(jìn)位值 } } } } /** * 大整數(shù)階乘 * @param biginteger 所計算的大整數(shù) */ private void bigfactorial(int biginteger) { int pos =0; // int digit; //數(shù)據(jù)長度 int a , b ; int m = 0 ; //統(tǒng)計輸出位數(shù) int n = 0 ; //統(tǒng)計輸出行數(shù) double sum = 0; //階乘位數(shù) for (a = 1 ; a <= biginteger ; a ++)//計算階乘位數(shù) { sum += math.log10(a); } digit = (int)sum + 1; //數(shù)據(jù)長度 int[] fact = new int[digit]; //初始化一個數(shù)組 fact[0] = 1; //設(shè)個位為 1 for (a = 2 ; a <= biginteger ; a++ )//將2^biginteger逐個與原來的積相乘 { for (b = digit-1 ; b >= 0 ; b--)//查找最高位{} { if( fact[b] != 0 ) { pos = b ; //記錄最高位 break; } } for (b = 0; b <= pos ; b++) { fact[b] *= a ; //每一位與i乘 } carry(fact,pos); } for (b = digit-1 ; b >= 0 ; b --) { if(fact[b] != 0) { pos = b ; //記錄最高位 break; } } system.out.println(biginteger +"階乘結(jié)果為："); for (a = pos ; a >= 0 ; a --)//輸出計算結(jié)果 { system.out.print(fact[a]); m++; if(m % 5 == 0) { system.out.print(" "); } if(40 == m ) { system.out.println(""); m = 0 ; n ++; if(10 == n ) { system.out.print("\n"); n = 0; } } } system.out.println("\n"+"階乘共有: "+(pos+1)+" 位"); } public void dobigfactorial(int biginteger) { int timebegin=(int) system.currenttimemillis(); this.bigfactorial(biginteger); int timefinishi=(int) system.currenttimemillis(); int time = timefinishi-timebegin; system.out.println("計算耗時: " + time +"毫秒" ); } public static void main(string[] args) { biginteger bi = new biginteger(); bi.dobigfactorial(100000); }} |
計算10,0000的階乘，顯示結(jié)果如下：
這樣的結(jié)果，控制臺顯然已經(jīng)無法保存內(nèi)容了。10萬的階乘有45萬位之多，這就相當(dāng)于一本有45萬字的小說一樣。對比1000的階乘結(jié)果如下：
控制臺可以完整顯示。
總結(jié)
以上就是本文關(guān)于java版超大整數(shù)階乘算法代碼詳解-10,0000級的全部內(nèi)容，希望對大家有所幫助。如有不足之處，歡迎留言指出。感謝朋友們對本站的支持！
原文鏈接：http://www.open-open.com/home/space-135360-do-blog-id-9620.html
