这个递归因子实现有什么问题？

I compiled and run in my computer, and it executes correctly. I tried IDEONE, and I got a successful answer.

我编译并在我的计算机上运行，它正确执行。我尝试了IDEONE，我得到了一个成功的答案。

But when I submit it in SPOJ, I'm getting a wrong answer. Is something wrong in this implementation?

但是当我在SPOJ中提交它时，我得到了错误的答案。这个实现有问题吗？

#include <iostream>
#include <cstdio>

using namespace std;

int factorial(int n) {
    if (n <= 1)
        return 1;

    return n * factorial(n - 1);
}

int main() {
    int t;
    int n;

    cout << "";
    cin >> t;

    for (int i = 0; i < t; i++) {
        cout << "";
        cin >> n;

        printf("%d\n", factorial(n));
    }

    return 0;
}

1 个解决方案

#1

The problem with the above code is due to the finite space we can use to store the value of an int. On a 32-bit machine, int's have 32 bits (value 0 or 1), which means that the maximum value an unsigned int can have is (2^31 - 1) and the maximum value an int can have is (2^30 - 1) (since it needs one bit to denote whether it is positive or negative, while the unsigned int is always positive and can devote that bit to just regular value).

上面代码的问题是由于我们可以用来存储int值的有限空间。在32位机器上，int有32位（值0或1），这意味着unsigned int可以有的最大值是（2 ^ 31 - 1），int可以有的最大值是（2 ^ 30） - 1）（因为它需要一位来表示它是正还是负，而unsigned int总是正数并且可以将该位专用于常规值）。

Now, that aside, you should look into ways of storing the value of a very large number in a different data structure! Maybe an array would be a good choice...

现在，除此之外，您应该研究如何将非常大的数值存储在不同的数据结构中！也许阵列会是个不错的选择......

Just to brainstorm, imagine creating an int bigInteger[100] (that should be large enough to hold 100!). To multiply two of your numbers, you could then implement a bitMultiplication(int bitNum[], int num) function that would take in your array by reference and perform bitwise multiplication (see the following post for details: Multiplying using Bitwise Operators).

只是为了头脑风暴，想象一下创建一个int bigInteger [100]（应该足够大以容纳100！）。要乘以两个数字，您可以实现一个bitMultiplication（int bitNum []，int num）函数，该函数将通过引用接收数组并执行按位乘法（有关详细信息，请参阅以下文章：使用按位运算符进行乘法）。

Use that bitMulitiplication(int bitNum[], int num) instead of the regular multiplication in your recursive factorial function, and you should have a function that works on large n!

使用bitMulitiplication（int bitNum []，int num）而不是递归factorial函数中的常规乘法，你应该有一个适用于大n的函数！

#1