当计算超过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