Java版超大整数阶乘算法代码详解-10,0000级

当计算超过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;
		//设个位为 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级的全部内容,希望对大家有所帮助。感兴趣的朋友可以继续参阅本站:

java中幂指数值的运算代码解析

Java编程实现对十六进制字符串异或运算代码示例

Java编程实现基于用户的协同过滤推荐算法代码示例

如有不足之处,欢迎留言指出。感谢朋友们对本站的支持!

您可能感兴趣的文章:

  • 详解Java实现的k-means聚类算法
  • Java语言字典序排序算法解析及代码示例
  • Java实现Floyd算法求最短路径
  • Java递归算法遍历部门代码示例
  • Java使用异或运算实现简单的加密解密算法实例代码
  • JAVA实现感知器算法
  • Java实现的双向匹配分词算法示例
  • Java编程实现二项分布的采样或抽样实例代码
(0)

相关推荐

  • JAVA实现感知器算法

    简述 随着互联网的高速发展,A(AI)B(BigData)C(Cloud)已经成为当下的核心发展方向,假如三者深度结合的话,AI是其中最核心的部分.所以如果说在未来社会,每个人都必须要学会编程的话,那么对于程序员来说,人工智能则是他们所必须掌握的技术(科技发展真tm快). 这篇文章介绍并用JAVA实现了一种最简单的感知器网络,不纠结于公式的推导,旨在给大家提供一下学习神经网络的思路,对神经网络有一个大概的认识. 感知器网络模型分析 首先看一张图 如果稍微对神经网络感兴趣的一定对这张图不陌生,这张

  • Java实现的双向匹配分词算法示例

    本文实例讲述了Java实现的双向匹配分词算法.分享给大家供大家参考,具体如下: 目前比较流行的几大分词算法有:基于字符串匹配的分词方法.基于理解的分词方法和基于统计的分词方法.本文采用的是基于字符串匹配法. 正向最大匹配分词: 该算法是基于分词词典实现,从字符串左侧进行分割匹配,如果词典存在则返回分割出来的词语并将该词从之前的字符串中切除,循环进行切割直到字符串大小为0. 例如:str = "我们都是西北农林科技大学信息工程学院的学生.",(假设我们定义最大切割长度max = 8,也就

  • Java语言字典序排序算法解析及代码示例

    字典序法就是按照字典排序的思想逐一产生所有排列. 在数学中,字典或词典顺序(也称为词汇顺序,字典顺序,字母顺序或词典顺序)是基于字母顺序排列的单词按字母顺序排列的方法. 这种泛化主要在于定义有序完全有序集合(通常称为字母表)的元素的序列(通常称为计算机科学中的单词)的总顺序. 对于数字1.2.3......n的排列,不同排列的先后关系是从左到右逐个比较对应的数字的先后来决定的.例如对于5个数字的排列 12354和12345,排列12345在前,排列12354在后.按照这样的规定,5个数字的所有的

  • Java编程实现二项分布的采样或抽样实例代码

    本文研究的主要是Java编程实现二项分布的采样或抽样,下面是具体实现代码. 如下程序为n=100,p=0.9的二项分布采样,共采样10000次 package function; import org.apache.commons.math3.distribution.BetaDistribution; import org.apache.commons.math3.distribution.BinomialDistribution; import org.apache.commons.math

  • 详解Java实现的k-means聚类算法

    需求 对MySQL数据库中某个表的某个字段执行k-means算法,将处理后的数据写入新表中. 源码及驱动 kmeans_jb51.rar 源码 import java.sql.*; import java.util.*; /** * @author tianshl * @version 2018/1/13 上午11:13 */ public class Kmeans { // 源数据 private List<Integer> origins = new ArrayList<>()

  • Java递归算法遍历部门代码示例

    递归是一个非常有用的知识点.写点实例帮助自己记忆 中间有过程代码 首先一个javapojo类 package com.qcf.po; import java.util.HashSet; import java.util.Set; public class Depart { private long id; private String name; private String destion; //用户 Set<User> users=new HashSet<User>(); //

  • Java实现Floyd算法求最短路径

    本文实例为大家分享了Java实现Floyd算法求最短路径的具体代码,供大家参考,具体内容如下 import java.io.FileInputStream; import java.io.FileNotFoundException; import java.util.Scanner; public class TestMainIO { /** * @param args * @throws FileNotFoundException */ public static void main(Stri

  • Java使用异或运算实现简单的加密解密算法实例代码

    Java简单的加密解密算法,使用异或运算 实例1: package cn.std.util; import java.nio.charset.Charset; public class DeEnCode { private static final String key0 = "FECOI()*&<MNCXZPKL"; private static final Charset charset = Charset.forName("UTF-8"); pr

  • Java版超大整数阶乘算法代码详解-10,0000级

    当计算超过20以上的阶乘时,阶乘的结果值往往会很大.一个很小的数字的阶乘结果就可能超过目前个人计算机的整数范围.如果需求很大的阶乘,比如1000以上完全无法用简单的递归方式去解决.在网上我看到很多用C.C++和C#写的一些关于大整数阶乘的算法,其中不乏经典但也有很多粗糙的文章.数组越界,一眼就可以看出程序本身无法运行.转载他人文章的时候,代码倒是仔细看看啊.唉,粗糙.过年了,在家闲来蛋疼,仔细分析分析,用Java实现了一个程序计算超大整数阶乘.思想取自网上,由我个人优化和改进. 这个方法采用"数

  • Java中EnumMap代替序数索引代码详解

    本文研究的主要是Java中EnumMap代替序数索引的相关内容,具体介绍如下. 学习笔记<Effective Java 中文版 第2版> 经常会碰到使用Enum的ordinal方法来索引枚举类型. public class Herb { public enum Type { ANNUAL, PERENNIAL, BIENNIAL }; private final String name; private final Type type; Herb(String name, Type type)

  • java 中模式匹配算法-KMP算法实例详解

    java 中模式匹配算法-KMP算法实例详解 朴素模式匹配算法的最大问题就是太低效了.于是三位前辈发表了一种KMP算法,其中三个字母分别是这三个人名的首字母大写. 简单的说,KMP算法的对于主串的当前位置不回溯.也就是说,如果主串某次比较时,当前下标为i,i之前的字符和子串对应的字符匹配,那么不要再像朴素算法那样将主串的下标回溯,比如主串为"abcababcabcabcabcabc",子串为"abcabx".第一次匹配的时候,主串1,2,3,4,5字符都和子串相应的

  • Java语言中的内存泄露代码详解

    Java的一个重要特性就是通过垃圾收集器(GC)自动管理内存的回收,而不需要程序员自己来释放内存.理论上Java中所有不会再被利用的对象所占用的内存,都可以被GC回收,但是Java也存在内存泄露,但它的表现与C++不同. JAVA中的内存管理 要了解Java中的内存泄露,首先就得知道Java中的内存是如何管理的. 在Java程序中,我们通常使用new为对象分配内存,而这些内存空间都在堆(Heap)上. 下面看一个示例: public class Simple { public static vo

  • Java编程Webservice指定超时时间代码详解

    WebService是一种跨编程语言和跨操作系统平台的远程调用技术 所谓远程调用,就是一台计算机a上的一个程序可以调用到另外一台计算机b上的一个对象的方法,譬如,银联提供给商场的pos刷卡系统(采用交互提问的方式来加深大家对此技术的理解). 远程调用技术有什么用呢?商场的POS机转账调用的转账方法的代码是在银行服务器上,还是在商场的pos机上呢?什么情况下可能用到远程调用技术呢?例如,amazon,天气预报系统,淘宝网,校内网,百度等把自己的系统服务以webservice服务的形式暴露出来,让第

  • java时间日期使用与查询代码详解

    只要格式正确,直接比较字符串就可以了呀,精确到秒的也一样 String s1 = "2003-12-12 11:30:24"; String s2 = "2004-04-01 13:31:40"; int res = s1.compareTo(s2); 求日期差 SimpleDateFormat df = new SimpleDateFormat("yyyy-MM-dd HH:mm:ss"); Date begin=df.parse("

  • Java编程实现快速排序及优化代码详解

    普通快速排序 找一个基准值base,然后一趟排序后让base左边的数都小于base,base右边的数都大于等于base.再分为两个子数组的排序.如此递归下去. public class QuickSort { public static <T extends Comparable<? super T>> void sort(T[] arr) { sort(arr, 0, arr.length - 1); } public static <T extends Comparabl

  • java多线程Thread的实现方法代码详解

    之前有简单介绍过java多线程的使用,已经Thread类和Runnable类,为了更好地理解多线程,本文就Thread进行详细的分析. start() 我们先来看看API中对于该方法的介绍: 使该线程开始执行:Java 虚拟机调用该线程的 run 方法. 结果是两个线程并发地运行:当前线程(从调用返回给 start 方法)和另一个线程(执行其 run 方法). 多次启动一个线程是非法的.特别是当线程已经结束执行后,不能再重新启动. 用start方法来启动线程,真正实现了多线程运行,这时无需等待r

  • Java动态代理(设计模式)代码详解

    基础:需要具备面向对象设计思想,多态的思想,反射的思想: Java动态代理机制的出现,使得Java开发人员不用手工编写代理类,只要简单地指定一组接口及委托类对象,便能动态地获得代理类.代理类会负责将所有的方法调用分派到委托对象上反射执行,在分派执行的过程中,开发人员还可以按需调整委托类对象及其功能,这是一套非常灵活有弹性的代理框架.通过阅读本文,读者将会对Java动态代理机制有更加深入的理解.本文首先从Java动态代理的运行机制和特点出发,对其代码进行了分析,推演了动态生成类的内部实现. 代理模

  • Java的静态类型检查示例代码详解

    关于静态类型检查和动态类型检查的解释: 静态类型检查:基于程序的源代码来验证类型安全的过程: 动态类型检查:在程序运行期间验证类型安全的过程: Java使用静态类型检查在编译期间分析程序,确保没有类型错误.基本的思想是不要让类型错误在运行期间发生. 在各色各样的编程语言中,总共存在着两个类型检查机制:静态类型检查和动态类型检查. 静态类型检查是指通过对应用程序的源码进行分析,在编译期间就保证程序的类型安全. 动态类型检查是在程序的运行过程中,验证程序的类型安全.在Java中,编译期间使用静态类型

随机推荐