c++ - 置换程序中的 int 限制 (C++)

Question

我写了一个简单的 C++ 程序，用 2 种不同的方法计算排列/阶乘。当我尝试对 20 和 2 使用更长的方法 (p1) 时，问题就出现了。当然，“20!”是一个巨大的数字。使用递归方法计算阶乘时整数有限制吗？

#include <iostream>
using namespace std;

int p1(int n, int r);
int p2(int n, int r);
int factorial(int x);

int main()
{
    cout << p1(10, 8) << endl;
    cout << p2(10, 8) << endl;
    cout << p1(4, 3) << endl;
    cout << p2(4, 3) << endl;
    cout << p1(20, 2) << endl;    // THE NUMBER PRINTS INCORRECTLY HERE
    cout << p2(20, 2) << endl;

    system("PAUSE");
    return EXIT_SUCCESS;
}

int p1(int n, int r)   // long version, recursively calls factorial
{
    return (factorial(n) / factorial(n - r));
}

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

int p2(int n, int r)    // shortcut, does arithmetic in for loop
{
    int answer = n;
    for (int i = 1; i < r; i++)
    {
        answer *= n - 1;
        n--;
    }
    return answer;
}

Answer 1

20! 是 2.4*10^18

您可以查看 limits.h 的引用资料查看限制是什么。

考虑 2^32 是 4.2*10^9。 long int 通常是 32 位值。

考虑到 2^64 是 1.8*10^19，所以一个 64 位整数可以让你通过 20! 但不是更多的。 unsigned long long int 应该会为您完成。

unsigned long long int p1(int n, int r)
{
    return (factorial(n) / factorial(n - r));
}

unsigned long long int factorial(unsigned long long int x)
{
    if (x == 0)
        return 1;
    else if (x > 0)
        return (x * factorial(x - 1));
}

unsigned long long int p2(int n, int r)
{
    unsigned long long int answer = n;
    for (int i = 1; i < r; i++)
     {
        answer *= n - 1;
        n--;
    }
    return answer;
}

如果您被允许参与此作业，请考虑使用 float 或 double，除非您需要绝对精度，或者只需要达到 20 即可完成。如果您确实需要绝对精度并执行大于 20 的阶乘，则必须设计一种方法将更大的整数存储在字节数组中，例如 @z32a7ul states。

您还可以通过执行 answer *= --n; 来保存操作，以便在使用它之前预先递减 n。