回《筆試常見的“階乘”程式設計題，你寫對了麼？》

原帖連結：http://www.cnblogs.com/kym/archive/2009/10/05/1578224.html    

    我機器上沒有C#的開發環境，是以沒法測試作者這個代碼的耗時，不過10000的階乘在5秒内完成，不知道作者的代碼是否能達到？我想起前段時間在HDU做的一道ACM題，題目的時限要求是1秒内能計算10000的階乘（當然這是代碼跑在它的伺服器的時間）。

題目連結：http://acm.hdu.edu.cn/showproblem.php?pid=1042

      如果按照飛林沙文章中那種正常的思路，逐位相乘，再對齊相加，缺點很明顯，如果n值比較大，運算次數将非常多，必定會逾時，1萬的階乘想在1秒内完成肯定無法達成。

    我的思路是把資料分組，每組上限為9999，最多可容納2萬組,每組4位整數，則可以容納8萬位整數（當然，組數可以随你要計算的n的大小進行調整），利用組與組的錯位相乘再相加，可以避免樓主這樣逐位進行運算。

代碼如下：

複制代碼

#include<iostream>

#include<stdio.h>

#include<string>

#include<iomanip>

#include<algorithm>

using namespace std;

#include "time.h"

const int MAX_GROUPS = 20000;//最多2萬組，每組最多4位整數，即最多可容納8萬位整數

const int MAXN = 9999;//每組的上限值

const int GROUP_LEN = 4;//每組的最大長度

class BigInteger

{

private:

    int data[MAX_GROUPS];

    int len;

    void init()

    {

        memset(data,0,sizeof(data));

    }

public:

    BigInteger()

        init();

        len = 0;

    BigInteger(const int b);

    BigInteger(const BigInteger &);

    bool operator > (const BigInteger&)const;

    BigInteger & operator=(const BigInteger &);

    BigInteger & add(const BigInteger &);

    BigInteger & sub(const BigInteger &);

    BigInteger operator+(const BigInteger &) const;

    BigInteger operator-(const BigInteger &) const;

    BigInteger operator*(const BigInteger &) const;

    BigInteger operator/(const int &) const;

    void print();

};

BigInteger::BigInteger(const int num)

    int res,tmp = num;

    len = 0;

    init();

    while(tmp > MAXN)

        res = tmp - tmp / (MAXN + 1) * (MAXN + 1);

        tmp = tmp / (MAXN + 1);

        data[len++] = res;

    data[len++] = tmp;

}

BigInteger::BigInteger(const BigInteger & rhs) : len(rhs.len)

    int i;

    for(i = 0 ; i < len ; i++)

        data[i] = rhs.data[i];

bool BigInteger::operator > (const BigInteger &rhs)const

    int ln;

    if(len > rhs.len)

        return true;

    else if(len < rhs.len)

        return false;

    else if(len == rhs.len)

        ln = len - 1;

        while(data[ln] == rhs.data[ln] && ln >= 0) 

        {

            ln--;

        }

        if(ln >= 0 && data[ln] > rhs.data[ln]) 

            return true;

        else 

            return false;

BigInteger & BigInteger::operator = (const BigInteger &rhs)

    len = rhs.len;

    for(int i = 0 ; i < len ; i++)

    return *this;

BigInteger& BigInteger::add(const BigInteger &rhs)

    int i,nLen;

    nLen = rhs.len > len ? rhs.len : len;

    for(i = 0 ; i < nLen ; i++)

        data[i] = data[i] + rhs.data[i];

        if(data[i] > MAXN)

            data[i + 1]++;

            data[i] = data[i] - MAXN - 1;

    if(data[nLen] != 0) 

        len = nLen + 1;

    else 

        len = nLen;

BigInteger & BigInteger::sub(const BigInteger &rhs)

    int i,j,nLen;

    if (len > rhs.len)

        for(i = 0 ; i < nLen ; i++)

            if(data[i] < rhs.data[i])

            {

                j = i + 1;

                while(data[j] == 0) j++;

                data[j]--;

                --j;

                while(j > i)

                {

                    data[j] += MAXN;

                    --j;

                }

                data[i] = data[i] + MAXN + 1 - rhs.data[i];

            }

            else 

                data[i] -= rhs.data[i];

        while(data[len - 1] == 0 && len > 1) 

            --len;    

    else if (len == rhs.len)

        for(i = 0 ; i < len ; i++)

            data[i] -= rhs.data[i];

BigInteger BigInteger::operator+(const BigInteger & n) const 

    BigInteger a = *this;

    a.add(n);

    return a;

BigInteger BigInteger::operator-(const BigInteger & T) const

    BigInteger b = *this;

    b.sub(T);

    return b;

BigInteger BigInteger::operator * (const BigInteger &rhs) const

    BigInteger result;

    int i,j,up;

    int temp,temp1;

    for(i = 0; i < len; i++)

        up = 0;

        for(j = 0; j < rhs.len; j++)

            temp = data[i] * rhs.data[j] + result.data[i + j] + up;

            if(temp > MAXN)

                temp1 = temp - temp / (MAXN + 1) * (MAXN + 1);

                up = temp / (MAXN + 1);

                result.data[i + j] = temp1;

                up = 0;

                result.data[i + j] = temp;

        if(up != 0)

            result.data[i + j] = up;

    result.len = i + j;

    while(result.data[result.len - 1] == 0 && result.len > 1) result.len--;

    return result;

BigInteger BigInteger::operator/(const int & b) const

    BigInteger ret;

    int i,down = 0;

    for(i = len - 1 ; i >= 0 ; i--)

        ret.data[i] = (data[i] + down * (MAXN + 1)) / b;

        down = data[i] + down * (MAXN + 1) - ret.data[i] * b;

    ret.len = len;

    while(ret.data[ret.len - 1] == 0) ret.len--;

    return ret;

void BigInteger::print()

    cout << data[len - 1];

    for(i = len - 2 ; i >= 0 ; i--)

        cout.width(GROUP_LEN);

        cout.fill('0');

        cout << data[i];

    cout << endl;

int main()

{  

    clock_t   start,   finish;   

    double     duration;   

    int i,n;

    BigInteger result,num;

    scanf("%d",&n);

    start   =   clock();    

    result = BigInteger(1);

    for(i = 2;i <= n; ++i)

        num = BigInteger(i);

        result = result * num;

    result.print();

    finish   =   clock();   

    duration   =   (double)(finish   -   start)   /   CLOCKS_PER_SEC;  

    printf(   "%f   seconds\n",   duration   );   

    return 0;

下面給出測試結果，

我的機器配置：酷睿雙核2.0G,記憶體3G,

計算10000的階乘，我的機器用時3.312秒，在HDU的伺服器上，10000的階乘用時不到900毫秒。

計算12345的階乘，我的機器用時5.078秒。

計算20000的階乘，我的機器用時13.656秒。

用C/C++确實是會快些的，HDU的這道題目對Java程式的時限是5秒内完成1萬的階乘，但c/c++的時限是1秒，由此可以看出。

大家也可以試試在HDU的伺服器上送出下你的代碼，看看能否在1秒内通過。

此外，還有2個常見的N!題目，就是N!的尾數0的個數和N!的非零末尾數，有興趣的同學可以自己看看。

本文轉自Phinecos(洞庭散人)部落格園部落格，原文連結：http://www.cnblogs.com/phinecos/archive/2009/10/06/1578411.html，如需轉載請自行聯系原作者