Java版超大整數(shù)階乘算法代碼詳解-10,0000級(jí)

更新時(shí)間：2018年01月08日 11:11:50 作者：Yangcl

這篇文章主要介紹了Java版超大整數(shù)階乘算法代碼詳解-10,0000級(jí)，具有一定借鑒價(jià)值,需要的朋友可以參考下

當(dāng)計(jì)算超過20以上的階乘時(shí)，階乘的結(jié)果值往往會(huì)很大。一個(gè)很小的數(shù)字的階乘結(jié)果就可能超過目前個(gè)人計(jì)算機(jī)的整數(shù)范圍。如果需求很大的階乘，比如1000以上完全無法用簡(jiǎn)單的遞歸方式去解決。在網(wǎng)上我看到很多用C、C++和C#寫的一些關(guān)于大整數(shù)階乘的算法，其中不乏經(jīng)典但也有很多粗糙的文章。數(shù)組越界，一眼就可以看出程序本身無法運(yùn)行。轉(zhuǎn)載他人文章的時(shí)候，代碼倒是仔細(xì)看看啊。唉，粗糙。過年了，在家閑來蛋疼，仔細(xì)分析分析，用Java實(shí)現(xiàn)了一個(gè)程序計(jì)算超大整數(shù)階乘。思想取自網(wǎng)上，由我個(gè)人優(yōu)化和改進(jìn)。

這個(gè)方法采用“數(shù)組進(jìn)位”算法。在超越計(jì)算機(jī)變量取值范圍的情況下，將多位數(shù)相乘轉(zhuǎn)化為一位數(shù)相乘。如11！=39916800，若需求12的階乘，則需要將39916800與12相乘，可利用乘法分配率。乘法豎式如下圖所示：

使用一個(gè)數(shù)組來保存階乘每一位的結(jié)果，一個(gè)數(shù)組元素保存一位數(shù)。例如：將11的階乘的結(jié)果399
16800保存到數(shù)組的8個(gè)元素中，要計(jì)算12的階乘就用每個(gè)數(shù)組元素中的值去乘以12，并將結(jié)果保存到原來的數(shù)組元素中。接下來去判斷每個(gè)數(shù)組元素是否需要進(jìn)位，通過進(jìn)位操作使數(shù)組中的每個(gè)元素保存的數(shù)都只有一位數(shù)，示意圖如下：

理論上講，只要計(jì)算機(jī)內(nèi)存空間允許就可以保存任意多位的階乘結(jié)果，不再受變量的取值范圍的限制，只受到操作系統(tǒng)的尋址能力和計(jì)算機(jī)內(nèi)存的限制。友情提示：如果要求的階乘數(shù)字很大則可以將數(shù)組定義為long類型，以避免在計(jì)算單位數(shù)的乘積時(shí)出現(xiàn)溢出的情況。

實(shí)現(xiàn)代碼如下：

public class BigInteger 
{
	/**
	 * 計(jì)算進(jìn)位
	 * @param bit	 數(shù)組
	 * @param pos 用于判斷是否是數(shù)組的最高位
	 */
	private void carry(int[] bit, int pos)
		{
		int i ,carray = 0;
		for (i = 0 ; i<= pos ;i++)//從0到pos逐位檢查是否需要進(jìn)位
		{
			bit[i] += carray;
			//累加進(jìn)位
			if(bit[i] <= 9)	 //小于9不進(jìn)位
			{
				carray = 0;
			} else if(bit[i] >9 && i<pos)//大于9，但不是最高位
			{
				carray = bit[i]/10;
				//保存進(jìn)位值
				bit[i] = bit[i]%10;
				//得到該位的一位數(shù)
			} else if(bit[i] > 9 && i >= pos)//大于9，且是最高位
			{
				while(bit[i] > 9)//循環(huán)向前進(jìn)位
				{
					carray = bit[i]/10;
					//計(jì)算進(jìn)位值
					bit[i] = bit[i] % 10;
					//當(dāng)前的第一位數(shù)
					i ++ ;
					bit[i] = carray;
					//在下一位保存進(jìn)位值
				}
			}
		}
	}
	/**
	 * 大整數(shù)階乘
	 * @param bigInteger 所計(jì)算的大整數(shù)
	 */
	private void bigFactorial(int bigInteger)
		{
		int pos =0;
		//
		int digit;
		//數(shù)據(jù)長(zhǎng)度
		int a , b ;
		int m = 0 ;
		//統(tǒng)計(jì)輸出位數(shù)
		int n = 0 ;
		//統(tǒng)計(jì)輸出行數(shù)
		double sum = 0;
		//階乘位數(shù)
		for (a = 1 ; a <= bigInteger ; a ++)//計(jì)算階乘位數(shù)
		{
			sum += Math.log10(a);
		}
		digit = (int)sum + 1;
		//數(shù)據(jù)長(zhǎng)度
		int[] fact = new int[digit];
		//初始化一個(gè)數(shù)組 
		fact[0] = 1;
		//設(shè)個(gè)位為 1
		for (a = 2 ; a <= bigInteger ; a++ )//將2^bigInteger逐個(gè)與原來的積相乘
		{
			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 +"階乘結(jié)果為：");
		for (a = pos ; a >= 0 ; a --)//輸出計(jì)算結(jié)果
		{
			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("計(jì)算耗時(shí): " + time +"毫秒" );
	}
	public static void main(String[] args)
		{
		BigInteger bi = new BigInteger();
		bi.doBigFactorial(100000);
	}
}

計(jì)算10,0000的階乘，顯示結(jié)果如下：