首页 > 代码库 > 大数阶乘

大数阶乘

首先定义一个足够长的数组。
拿10000的阶乘为例,最后的结果长度是35660位,所以我们定义一个40000个成员的数组就可以了。
int result[40000];
其核心思想就是把计算结果每一位上的数字保存到一个数组成员中,例如:
把124保存至数组中,保存结果应该是
result[0] 4
result[1] 2
result[2] 1
这样肯定是没有问题的,一个int型数据存放一个小于10的数是绝对不会溢出。但是处理起来就稍微有点麻烦。
把整个数组看成一个数字,这个数字和一个数相乘的时候,需要每一位都和这个乘数进行相乘运算还需要把前一为的进位加上。运算方法和小学数学是一样的,乘积的个位是当前位上应该表示的数字,10位以上的需要进位。因为乘数不可能大于10000,所以乘数和一个小于10的书相乘的时候不会大于100000,再加上前一位的进位用一个int型数据来保持这个结果就没有问题。写法如下:
int 结果 = result[x] * 乘数 + 进位;
每一位的计算结果有了,把这个结果的个位数拿出来放到这个数组元素上:
result[x] = 结果%10;
接下来的工作就是计算出进位:
进位 = 结果 / 10;
这样一位一位的把整个数组计算一遍,最后可能还有进位,用同样的方法,把进位的数值拆成单个数字,放到相应的数组元素中。
最后输出一下结果,从最高位吧数字打印一遍就OK了。完整程序如下,在VC6.0下调试通过。

#include <iostream>

using namespace std;

int a[40000];

int main()
{
    int n;
    while(cin>>n)
    {
        int jz=0;
        int ws=1;
        int temp;
        a[0]=1;
        for(int i=2;i<=n;i++)
        {
            temp=0;
            for(int j=1;j<=ws;j++)
            {
               temp=i*a[j-1]+jz;
               a[j-1]=temp%10;
               jz=temp/10;
            }
            while(jz)
            {
                a[++ws-1]=jz%10;
                jz/=10;
            }
        }
        for(int i=ws-1;i>=0;i--)
        cout<<a[i];
        cout<<endl;
    }
    return 0;
}