考虑计算一个数的阶乘问题。当结果大于 2^32 时，我们会得到溢出错误。我们如何设计一个程序来计算大数的阶乘？
编辑：假设我们使用的是 C++ 语言。
EDIT2：这是一个重复的问题
问问题
1171 次
8 回答
2
作为仅标记算法的问题。您的 2^32 不是问题，因为算法永远不会出现溢出错误。算法的实现可以并且确实存在溢出错误。那你用什么语言？
大多数语言都有可以使用的 BigNumber 或 BigInteger。
这是一个 C++ BigInteger 库：https ://mattmccutchen.net/bigint/
我建议你谷歌搜索：c++ biginteger
于 2013-01-26T23:33:06.910 回答
1
测试这个脚本：
import gmpy as gm
print gm.fac(3000)
对于非常大的数字很难存储或打印结果。
于 2013-01-26T23:50:48.043 回答
1
对于某些目的，例如计算组合的数量，计算阶乘的对数就足够了，因为您将阶乘除以阶乘并且最终结果的大小更合理 - 您只需在取之前减去对数结果的指数。
您可以通过添加对数或使用http://en.wikipedia.org/wiki/Gamma_function来计算阶乘的对数，这通常在数学库中可用（有很好的方法来近似）。
于 2013-01-27T04:52:22.973 回答
1
这样做需要您采取几种方法之一，但基本上可以归结为：
- 将您的号码拆分为多个变量（存储在数组中）和
- 跨阵列管理您的操作。
这样，数组中的每个 int/元素都有一个位置大小，最后可以串在一起形成整数。
C中的一个很好的例子：http ://www.go4expert.com/forums/c-program-calculate-factorial-t25352/
于 2013-01-26T23:31:43.930 回答
0
首先发明一种存储和使用大数的方法。常见的方法是将整数数组解释为大数的数字。然后将基本运算添加到您的系统中，例如乘法。然后相乘。
或者使用已经制定的解决方案。Google for：c++ 大整数库
于 2013-01-26T23:28:48.570 回答
0
You can use BigInteger for finding factorial of a Big numbers probably greater than 65 as the range of data type long ends at 65! and it starts returning 0 after that. Please refer to below Java code. Hope it would help:
import java.math.BigInteger;
public class factorial {
public factorial() {
// TODO Auto-generated constructor stub
}
public static void main(String args[])
{
factorial f = new factorial();
System.out.println(f.fact(100));
}
public BigInteger fact(int num)
{
BigInteger sum = BigInteger.valueOf(1);
for(int i = num ; i>= 2; i --)
{
sum = sum.multiply(BigInteger.valueOf(i));
}
return sum;
}
}
于 2018-12-18T20:28:35.603 回答
0
如果要提高测量范围，可以使用对数。对数会将您的乘法转换为加法，使其存储起来要小得多。
factorial(n) => n * factorial(n-1)
log(factorial(n)) => log(n) * log(factorial(n-1))
5! = 5*4*3*2*1 = 120
log(5!) = log(5) + log(4) + log(3) + log(2) + log(1) = 2.0791812460476247
In this example, I used base 10 logarithms, but any base works.
10^2.0791812460476247
Or 10^0.0791812460476247*10^2 or 1.2*10^2
于 2020-05-28T11:09:23.573 回答