c++ - 这个递归阶乘实现有什么问题？

Question

我在自己的电脑上编译运行，运行正常。我试过IDEONE，得到了成功的答案。

但是当我在 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;
}

Answer 1

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

现在，除此之外，您应该研究将非常大的数字的值存储在不同的数据结构中的方法!也许数组会是一个不错的选择...

只是为了集思广益，想象一下创建一个 int bigInteger[100](它应该足够大以容纳 100!)。要将两个数字相乘，您可以实现一个 bitMultiplication(int bitNum[], int num) 函数，该函数将通过引用获取您的数组并执行按位乘法(有关详细信息，请参阅以下帖子: Multiplying using Bitwise Operators ).

在你的递归阶乘函数中使用 bitMultiplication(int bitNum[], int num) 而不是常规乘法，你应该有一个适用于大 n 的函数!