-1

我正在解决一个计算阶乘的问题，挑战如下！

You are asked to calculate factorials of some small positive integers.

Input

An integer t, 1<=t<=100, denoting the number of testcases, followed by t lines,
each containing a single integer n, 1<=n<=100.

Output 

For each integer n given at input, display a line with the value of n!

我的代码给了我正确的解决方案，但超过了 2 秒的时间限制：

代码如下：

#include<stdio.h>
#include<stdlib.h>
#include<math.h>
void factorial(int N)
{
    printf("\n\n");
    int q,i,j,t,d,z;
    float p=0.0;
    for(i=2;i<=N;i++)
    p=p+log10(i);
    d=(int)p+1;//No of terms in the factorial
    int *b;
    //initialization of an array
    b=(int *)malloc(d*sizeof(int));
    b[0]=1;
    for(i=1;i<N;i++)
    b[i]=0;
    //calculation of factorial
    p=0.0;
    for(j=2;j<=N;j++)
    {
        q=0;
        p=p+log10(j);
        z=(int)p+1;
        for(i=0;i<N;i++)
        {
           t=(b[i]*j)+q;
           q=t/10;
           b[i]=t%10;   
        }
    }
    for(i=d-1;i>=0;i--)
    printf("%d",b[i]);

}
int main()
{
    int n,i,j;
    scanf("%d",&n);
    int *b;
    b=(int *)malloc(n*sizeof(int));
    for(i=0;i<n;i++)
    {
        scanf("%d",&b[i]);
    }
    for(i=0;i<n;i++)
    factorial(b[i]);
    return 0;
}

我怎样才能让我的程序更有效率并在给定的时间限制内产生输出？这个挑战来自HackerEarth

4

1 回答 1

2

由于 N 很小，一种有效的算法是预先计算所有阶乘：

BigNumberType fact[101];  // The numbers will become big, so you need (to create) a type to store it

fact[0] = 1.0;
for (i=0; i < 100; i++) {
  fact[i+1] = multiply(fact[i], i);
}

之后，查找值是微不足道的。

笔记：

扫描输入向量中的最大数并仅计算达到该数的阶乘可能会更有效。

于 2013-05-16T12:24:56.473 回答