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

Question

我写了一个简单的 C++ 程序，用两种不同的方法计算 permutations/factorials。当我尝试对 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个！超出整数范围。你的shortcut function并没有超过仅仅因为你没有计算整个faculty，而是20*19

Answer 2

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 状态。

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

Answer 3

如果你真的需要它，你可以创建一个 class 来保存可变长度的字节数组，并在其上定义运算符。在那种情况下，只有可用内存和您的耐心会限制数字的大小。我认为 Scheme（一种 LISP 方言）会做类似的事情。

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

int limit in permutation program (C++)

c++

permutation

factorial