Java版超大整數(shù)階乘算法代碼詳解-10,0000級(jí)
當(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é)果如下:

這樣的結(jié)果,控制臺(tái)顯然已經(jīng)無法保存內(nèi)容了。10萬的階乘有45萬位之多,這就相當(dāng)于一本有45萬字的小說一樣。對(duì)比1000的階乘結(jié)果如下:

控制臺(tái)可以完整顯示。
總結(jié)
以上就是本文關(guān)于Java版超大整數(shù)階乘算法代碼詳解-10,0000級(jí)的全部?jī)?nèi)容,希望對(duì)大家有所幫助。感興趣的朋友可以繼續(xù)參閱本站:
《Java編程實(shí)現(xiàn)對(duì)十六進(jìn)制字符串異或運(yùn)算代碼示例》
《Java編程實(shí)現(xiàn)基于用戶的協(xié)同過濾推薦算法代碼示例》
如有不足之處,歡迎留言指出。感謝朋友們對(duì)本站的支持!
相關(guān)文章
Java 異步回調(diào)機(jī)制實(shí)例分析
這篇文章主要介紹了Java 異步回調(diào)機(jī)制實(shí)例解析的相關(guān)資料,需要的朋友可以參考下2017-02-02
Java基本數(shù)據(jù)類型存儲(chǔ)在JVM中的存儲(chǔ)位置介紹
這篇文章主要介紹了Java基本數(shù)據(jù)類型存儲(chǔ)在JVM中的存儲(chǔ)位置,具有很好的參考價(jià)值,希望對(duì)大家有所幫助,如有錯(cuò)誤或未考慮完全的地方,望不吝賜教2023-07-07
Java實(shí)現(xiàn)Map集合遍歷的四種常見方式與用法分析
這篇文章主要介紹了Java實(shí)現(xiàn)Map集合遍歷的四種常見方式與用法,結(jié)合實(shí)例形式較為詳細(xì)的分析了java針對(duì)Map集合鍵值對(duì)遍歷的常見使用技巧與相關(guān)操作注意事項(xiàng),需要的朋友可以參考下2018-01-01
java 實(shí)現(xiàn)回調(diào)代碼實(shí)例
本文主要介紹Java的回調(diào)機(jī)制,并附實(shí)例代碼以供大家參考學(xué)習(xí),有需要的小伙伴可以看下2016-07-07
Springboot上傳文件時(shí)提示405問題及排坑過程
這篇文章主要介紹了Springboot上傳文件時(shí)提示405問題及排坑過程,具有很好的參考價(jià)值,希望對(duì)大家有所幫助。如有錯(cuò)誤或未考慮完全的地方,望不吝賜教2022-07-07
使用kotlin集成springboot開發(fā)的超詳細(xì)教程
目前大多數(shù)都在使用java集成 springboot進(jìn)行開發(fā),本文演示僅僅將 java換成 kotlin,其他不變的情況下進(jìn)行開發(fā),需要的朋友可以參考下2021-09-09

