大数阶乘

时间限制：

3000 ms  |  内存限制：65535 KB

难度：

3

 

描述

我们都知道如何计算一个数的阶乘，可是，如果这个数很大呢，我们该如何去计算它并输出它？

 

输入

输入一个整数m(0<m<=5000)

输出

输出m的阶乘，并在输出结束之后输入一个换行符

样例输入

50

样例输出

30414093201713378043612608166064768844377641568960512000000000000 看到大数运算首先想到的是运用数组在表示大数，以前是用过int型数组，但是考虑到这将会占用大量内存。所以决定尝试 char型数组，char和int的转化很简单，(int)(n - 48)和(char)(c + 48)。 然后就是解决大数的乘法问题，乘法中的难点在进位。想起来很简单，可实际上程序实现起来非常复杂，差不多用了我一下午时间，真是惭愧。下面就是程序：

#include 
       
        #include 
        
         #include 
         
          #define NUM 20000int main(char argc, char**argv){    char a[NUM];    char t[NUM];    char nstr[4];    int i, n, oldj = 0,len = 0;    scanf("%d", &n);    memset(a,0,NUM*sizeof(char));    a[0] = '1';    memset(t,0,NUM*sizeof(char));    t[0] = '1';    for(i = 1; i <= n; i++)    {        int count = 0, lastAdd = 0, j, c = 0;        int ii = i;        // 拷贝字符串数组        strcpy(a, t);        // 整数n的转化            while(ii)        {            ii/=10;            count++;        }        sprintf(nstr, "%d", i);        for(c = 0; c < count - 1; c++)        {            if(a[oldj + c] == '\0')                a[oldj + c] = '0';        }        for(j = 0; j < NUM; j++)        {            int remain;            int nn = 0, k;            if(a[j] == '\0')                break;                        for(k = 0; k <= j && k < count; k++)            {                nn += (int)(nstr[count-1-k] - 48) * (int)(a[j - k] - 48);            }            nn += lastAdd;            lastAdd = nn / 10;            remain = nn % 10;            if(lastAdd != 0 && a[j + 1] == '\0')                a[j + 1] = '0';                    t[j] = (char)(remain + 48);            }        oldj = j;    }    for(i = oldj-1; i >= 0; i--)    {        printf("%c", t[i]);    }    printf("\n");    system("pause");}
         
        
       

提交代码后发现还有更优的算法，而且在时间和空间上比我的程序好好几倍。瞬间感觉自己弱爆了。

#include
       
        #include
        
         const int maxn=20000;int a[maxn];int main(){    int n,i,j,s,c;    scanf("%d",&n);    memset(a,0,sizeof(a));    a[0]=1;    for(i=2;i<=n;i++)    {c=0;    for(j=0;j<=maxn;j++)    {    s=a[j]*i+c;    a[j]=s%10;    c=s/10;    }    }    for(j=maxn;j>=0;j--) if(a[j]) break;    for(i=j;i>=0;i--) printf("%d",a[i]);    printf("\n");    return 0;}
        
       

基本思路基本一致，只不过它用的是int型数组，但是为什么我的程序运行速度更慢，也许是字符和数字之间的转化太多造成的。弄巧成拙了。。