C 中的 SPOJ 小阶乘程序

Question

我的代码在 SPOJ 中显示 'wrong output'，尽管它在我的编译器中运行没有问题。

程序的代码是：

#include<stdio.h>

int factorial(int);

int main(){
    int a[100],t,n,i;
    scanf("%d",&t);
    for(i=0;i<t;i++){
        scanf("%d",&a[i]);
    }
    for(i=0;i<t;i++){
        printf("%d",factorial(a[i]));
        printf("\n");   
    }
    return 0;
}

int factorial(int n){
    if(n==0){
        return 1;
    }
    else if(n==1){
        return 1;
    }
    else{
        return n*factorial(n-1);
    }
}

Answer 1

您的程序出现整数溢出。您至少需要 66 bytes to store 100! exactly. An unsigned long long int is usually 8 bytes, and can store up to 1.8 × 10¹⁹. 100! is about 9.3 × 10¹⁵⁷.

您需要另一种方法来计算这个值，或者使用不同的语言。您可以尝试将值存储在 double 或 long double 中，但它不会准确，所以我怀疑它是否会满足 SPOJ。

Answer 2

100！是一个巨大的数字（我认为大约有 160 位数字）。 "long long" 最多可存储 19 位数字。您可以执行以下任一操作来解决此问题：

使用支持非常大整数的语言，例如 java 或 python。
为 c/c++ 等语言创建您自己的大整数类型代码。用数组表示整个大数，数组的每个索引只存储该数的一位数。例如，如果数字是 123，index[0] 存储数字 1，index[1] 存储数字 2，index[2] 存储数字 3。（您可以根据您的选择以相反的顺序存储它们）。

您提供的代码存在整数溢出问题。使用 double/long double 将不起作用，因为它会遭受精度损失。

C 中的 SPOJ 小阶乘程序

SPOJ Small Factorial program in C

c

factorial