杭電HDU1042（有點坑的高精度） - acm1314－IT工程師數位筆記本

文章出處

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

題意：

Given an integer N(0 ≤ N ≤ 10000), your task is to calculate N!

是不是很簡單呢？

一般方法：

#include<iostream>
#include<cstring>
using namespace std;
const int MAXN = 10000;
int a[MAXN];

int main()
{
    int N, k, temp;
    while(scanf("%d", &N)!=EOF)
    {
        memset(a, 0, sizeof(a));
        a[0]=1; 
        for(int i=1; i<=N; i++)
        {
            k=0;
            for(int j=0; j<MAXN; j++)
            {
                a[j]=a[j]*i+k;
                k=a[j]/10;
                a[j]%=10;
            }
        }
        int t;
        for(t=MAXN-1; t>=0; t--)
        if(a[t])
        {
            //cout<<t<<endl;
            break;
        }    
        for(int i=t; i>=0; i--)
        printf("%d", a[i]);
        printf("\n");
    }
    return 0;
}

上面的代碼是不是和你的想法相同呢？，很遺憾，上述代碼一定會超時！那么，能不能把數組開小些呢？ ----> 不能。當N=10000時，你會發現數組要開到9999。很明顯，這道題就是要卡你的時間，就是要卡你的優化。下面是兩個優化思路：

1. 合并計算：從而減少計算次數，例如你在每個a[i]中存10000數量級的數，然后這個數組的長度就成2000啦！但是這種算法在實現時要考慮很多情況，比較繁瑣！

2.過程優化：由于結果值在計算時，數位變化很大，但是上述代碼，在計算時每次都按MAXN-1 位計算，所以做了很多的無用功。如果每次計算時都順帶著算出位數，這樣就可以節省很多時間。代碼只需稍加改動即可！

3.綜合使用前兩種方法！

由于第一和第三中方法較繁瑣，我不再理會！

#include<iostream>
#include<cstdio>
using namespace std;

const int MAXN=100002;
int a[MAXN];

int main()
{
    int N;
    int k,count,temp;
    while(scanf("%d", &N)!=EOF)
    {
        a[0]=1;
        count=1;
        for(int i=1;i<=N;i++)
        {
            k=0;
            for(int j=0;j<count;j++)
            {
                temp=a[j]*i+k;
                a[j]=temp%10;
                k=temp/10;    
            }
            while(k)//¼ÇÂ¼½øÎ»    
             {
                a[count++]=k%10;
                k/=10;
            }
        }
            for(int i=count-1;i>=0;i--)
                printf("%d", a[i]);
                printf("\n");
    }
    return 0;
}

耗時： 1045MS 時限是5s。

然而：

#include<iostream>
#include<cstdio>
using namespace std;

const int MAXN = 100000;
int main()
{
    int n, a[MAXN];
    int i, j, k, count, temp;
    while(cin>>n)
    {
        a[0]=1;
        count=1;
        for(i=1; i<=n; i++)
        {
            k=0;
            for(j=0; j<=count; j++)
            {
                temp=a[j]*i+k;
                a[j]=temp%10;
                k=temp/10;
            }
            while(k)
            {
                a[count++]=k%10;
                k/=10;
            }
        }
        for(j=MAXN-1; j>=0; j--)
        if(a[j])
        break;
        for(i=count-1; i>=0; i--)
        cout<<a[i];
        cout<<endl;
    }
    return 0;
}

耗時： 811MS 很是令人費解！ cin和cout不應該比scanf等慢嗎？，然而事實就是這樣，看來，書上說的也未必正確。雖然這個道理大家都懂，但是不知不覺中還是迷信權威。現實情況是千變萬化的，面對不同的情況會有意料之外的結果。所以永遠不要自以為是，永遠不要把話說的太絕對， -------好像陷入悖論啦。呵呵！

，，，，，，，，，，，，，，，，，，，，，，，，，，，，，，，，，，，，，，，，，，，，，，，，，，，，，，，，，，，，，，，，，，，，，，，，，，，，，

文章列表