Java版超大整數階乘算法-10,0000級

Yangcl 11年前發布 | 14K 次閱讀

當計算超過20以上的階乘時，階乘的結果值往往會很大。一個很小的數字的階乘結果就可能超過目前個人計算機的整數范圍。如果需求很大的階乘，比如1000以上完全無法用簡單的遞歸方式去解決。在網上我看到很多用C、C++和C#寫的一些關于大整數階乘的算法，其中不乏經典但也有很多粗糙的文章。數組越界，一眼就可以看出程序本身無法運行。轉載他人文章的時候，代碼倒是仔細看看啊。唉，粗糙。過年了，在家閑來蛋疼，仔細分析分析，用Java實現了一個程序計算超大整數階乘。思想取自網上，由我個人優化和改進。</span>
這個方法采用 “數組進位” 算法。在超越計算機變量取值范圍的情況下，將多位數相乘轉化為一位數相乘。如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);
}

}</pre>計算10,0000的階乘，顯示結果如下：




      這樣的結果，控制臺顯然已經無法保存內容了。10萬的階乘有45萬位之多，這就相當于一本有45萬字的小說一樣。對比1000的階乘結果如下：




控制臺可以完整顯示。













</span>























</span>