当计算超过20以上的阶乘时,阶乘的结果值往往会很大。一个很小的数字的阶乘结果就可能超过目前个人计算机的整数范围。如果需求很大的阶乘,比如1000以上完全无法用简单的递归方式去解决。在网上我看到很多用C、C++和C#写的一些关于大整数阶乘的算法,其中不乏经典但也有很多粗糙的文章。数组越界,一眼就可以看出程序本身无法运行。转载他人文章的时候,代码倒是仔细看看啊。唉,粗糙。过年了,在家闲来蛋疼,仔细分析分析,用Java实现了一个程序计算超大整数阶乘。思想取自网上,由我个人优化和改进。
这个方法采用“数组进位”算法。在超越计算机变量取值范围的情况下,将多位数相乘转化为一位数相乘。如11!=39916800,若需求12的阶乘,则需要将39916800与12相乘,可利用乘法分配率。乘法竖式如下图所示:
使用一个数组来保存阶乘每一位的结果,一个数组元素保存一位数。例如:将11的阶乘的结果399
16800保存到数组的8个元素中,要计算12的阶乘就用每个数组元素中的值去乘以12,并将结果保存到原来的数组元素中。接下来去判断每个数组元素是否需要进位,通过进位操作使数组中的每个元素保存的数都只有一位数,示意图如下:
理论上讲,只要计算机内存空间允许就可以保存任意多位的阶乘结果,不再受变量的取值范围的限制,只受到操作系统的寻址能力和计算机内存的限制。友情提示:如果要求的阶乘数字很大则可以将数组定义为long类型,以避免在计算单位数的乘积时出现溢出的情况。
实现代码如下:
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;//设个位为 1for (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级的全部内容,希望对大家有所帮助。感兴趣的朋友可以继续参阅本站:
《java中幂指数值的运算代码解析》
《Java编程实现对十六进制字符串异或运算代码示例》
《Java编程实现基于用户的协同过滤推荐算法代码示例》
如有不足之处,欢迎留言指出。感谢朋友们对本站的支持!