您好,登錄后才能下訂單哦!
這篇文章給大家分享的是有關(guān)Java中超大整數(shù)階乘算法的示例分析的內(nèi)容。小編覺(jué)得挺實(shí)用的,因此分享給大家做個(gè)參考,一起跟隨小編過(guò)來(lái)看看吧。
這個(gè)方法采用“數(shù)組進(jìn)位”算法。在超越計(jì)算機(jī)變量取值范圍的情況下,將多位數(shù)相乘轉(zhuǎn)化為一位數(shù)相乘。如11!=39916800,若需求12的階乘,則需要將39916800與12相乘,可利用乘法分配率。乘法豎式如下圖所示:
使用一個(gè)數(shù)組來(lái)保存階乘每一位的結(jié)果,一個(gè)數(shù)組元素保存一位數(shù)。例如:將11的階乘的結(jié)果399
16800保存到數(shù)組的8個(gè)元素中,要計(jì)算12的階乘就用每個(gè)數(shù)組元素中的值去乘以12,并將結(jié)果保存到原來(lái)的數(shù)組元素中。接下來(lái)去判斷每個(gè)數(shù)組元素是否需要進(jìn)位,通過(guò)進(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è)與原來(lái)的積相乘 { 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)無(wú)法保存內(nèi)容了。10萬(wàn)的階乘有45萬(wàn)位之多,這就相當(dāng)于一本有45萬(wàn)字的小說(shuō)一樣。對(duì)比1000的階乘結(jié)果如下:
控制臺(tái)可以完整顯示。
感謝各位的閱讀!關(guān)于“Java中超大整數(shù)階乘算法的示例分析”這篇文章就分享到這里了,希望以上內(nèi)容可以對(duì)大家有一定的幫助,讓大家可以學(xué)到更多知識(shí),如果覺(jué)得文章不錯(cuò),可以把它分享出去讓更多的人看到吧!
免責(zé)聲明:本站發(fā)布的內(nèi)容(圖片、視頻和文字)以原創(chuàng)、轉(zhuǎn)載和分享為主,文章觀點(diǎn)不代表本網(wǎng)站立場(chǎng),如果涉及侵權(quán)請(qǐng)聯(lián)系站長(zhǎng)郵箱:is@yisu.com進(jìn)行舉報(bào),并提供相關(guān)證據(jù),一經(jīng)查實(shí),將立刻刪除涉嫌侵權(quán)內(nèi)容。