当计算超过20以上的阶乘时,阶乘的结果值往往会很大。一个很小的数字的阶乘结果就可能超过目前个人计算机的整数范围。如果需求很大的阶乘,比如1000以上完全无法用简单的递归方式去解决。在网上我看到很多用c、c++和c#写的一些关于大整数阶乘的算法,其中不乏经典但也有很多粗糙的文章。数组越界,一眼就可以看出程序本身无法运行。转载他人文章的时候,代码倒是仔细看看啊。唉,粗糙。过年了,在家闲来蛋疼,仔细分析分析,用java实现了一个程序计算超大整数阶乘。思想取自网上,由我个人优化和改进。
这个方法采用“数组进位”算法。在超越计算机变量取值范围的情况下,将多位数相乘转化为一位数相乘。如11!=39916800,若需求12的阶乘,则需要将39916800与12相乘,可利用乘法分配率。乘法竖式如下图所示:
使用一个数组来保存阶乘每一位的结果,一个数组元素保存一位数。例如:将11的阶乘的结果399
16800保存到数组的8个元素中,要计算12的阶乘就用每个数组元素中的值去乘以12,并将结果保存到原来的数组元素中。接下来去判断每个数组元素是否需要进位,通过进位操作使数组中的每个元素保存的数都只有一位数,示意图如下:
理论上讲,只要计算机内存空间允许就可以保存任意多位的阶乘结果,不再受变量的取值范围的限制,只受到操作系统的寻址能力和计算机内存的限制。友情提示:如果要求的阶乘数字很大则可以将数组定义为long类型,以避免在计算单位数的乘积时出现溢出的情况。
实现代码如下:
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 { /** * 计算进位 * @param bit 数组 * @param pos 用于判断是否是数组的最高位 */ private void carry( int [] bit, int pos) { int i ,carray = 0 ; for (i = 0 ; i<= pos ;i++) //从0到pos逐位检查是否需要进位 { bit[i] += carray; //累加进位 if (bit[i] <= 9 ) //小于9不进位 { carray = 0 ; } else if (bit[i] > 9 && i<pos) //大于9,但不是最高位 { carray = bit[i]/ 10 ; //保存进位值 bit[i] = bit[i]% 10 ; //得到该位的一位数 } else if (bit[i] > 9 && i >= pos) //大于9,且是最高位 { while (bit[i] > 9 ) //循环向前进位 { carray = bit[i]/ 10 ; //计算进位值 bit[i] = bit[i] % 10 ; //当前的第一位数 i ++ ; bit[i] = carray; //在下一位保存进位值 } } } } /** * 大整数阶乘 * @param biginteger 所计算的大整数 */ private void bigfactorial( int biginteger) { int pos = 0 ; // int digit; //数据长度 int a , b ; int m = 0 ; //统计输出位数 int n = 0 ; //统计输出行数 double sum = 0 ; //阶乘位数 for (a = 1 ; a <= biginteger ; a ++) //计算阶乘位数 { sum += math.log10(a); } digit = ( int )sum + 1 ; //数据长度 int [] fact = new int [digit]; //初始化一个数组 fact[ 0 ] = 1 ; //设个位为 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 + "阶乘结果为:" ); for (a = pos ; a >= 0 ; a --) //输出计算结果 { 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的阶乘,显示结果如下:
这样的结果,控制台显然已经无法保存内容了。10万的阶乘有45万位之多,这就相当于一本有45万字的小说一样。对比1000的阶乘结果如下:
控制台可以完整显示。
总结
以上就是本文关于java版超大整数阶乘算法代码详解-10,0000级的全部内容,希望对大家有所帮助。如有不足之处,欢迎留言指出。感谢朋友们对本站的支持!
原文链接:http://www.open-open.com/home/space-135360-do-blog-id-9620.html