注册 登录
  • 欢迎访问开心洋葱网站,在线教程,推荐使用最新版火狐浏览器和Chrome浏览器访问本网站,欢迎加入开心洋葱 QQ群
  • 为方便开心洋葱网用户,开心洋葱官网已经开启复制功能!
  • 欢迎访问开心洋葱网站,手机也能访问哦~欢迎加入开心洋葱多维思维学习平台 QQ群
  • 如果您觉得本站非常有看点,那么赶紧使用Ctrl+D 收藏开心洋葱吧~~~~~~~~~~~~~!
  • 由于近期流量激增,小站的ECS没能经的起亲们的访问,本站依然没有盈利,如果各位看如果觉着文字不错,还请看官给小站打个赏~~~~~~~~~~~~~!

java求超大整数阶乘的算法

JAVA相关 水墨上仙 2737次浏览 已收录 手机上查看

下面的代码采用数组的方式来处理大数字的问题

转自:http://www.open-open.com/home/space-135360-do-blog-id-9620.html

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);
	}
}


喜欢 (0)
[开心洋葱]
分享 (0)
关于作者:
水墨上仙
……
加载中……