我写了一个简单的 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;
}
最佳答案
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
。
关于c++ - 置换程序中的 int 限制 (C++),我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/40853699/