你如何编写一个非递归算法来计算 n!？
如何编写一个非递归算法来计算阶乘？
18
- denise
6
为什么？因为使用递归计算n!与循环相比速度非常慢。 - BradC
1@BradC：实际上不是这样的，如果你使用动态规划。 - Can Berk Güder
我一直认为这是与语言有关的。 - EBGreen
1大多数编译器都会优化尾递归，所以您的结果可能会有所不同。 - Steven A. Lowe
请参考以下链接，其中包含了关于不同编程语言中的阶乘算法的问题。 - Hafthor
你说得对。我在考虑递归版本的斐波那契数列（f[n] = f[n-1] + f[n-2]）的低效性。
递归版本的阶乘并不像这么糟糕（f[n] = n * f[n-1]）。 - BradC
22个回答
31
由于Int32在大于12!时会溢出，因此只需执行以下操作：
public int factorial(int n) {
int[] fact = {1, 1, 2, 6, 24, 120, 720, 5040, 40320,
362880, 3628800, 39916800, 479001600};
return fact[n];
}
- BradC
5
8这样写实际上会更慢，因为每次调用都要初始化数组，这比大约12次乘法运算（约2倍的计算量）更昂贵。好的查找表应该使用静态数据。此外，如果我向该函数传递13或-20会发生什么？ - Wedge
3另外，倒数第二个数字应该是39916800，而不是3991800（这可能说明查找表存在问题）。 - Wedge
不像 Ruby 那样，它会自动切换到大整数表示。 - martinus
1@Wedge - 我的编译器说查找速度提高了两倍（除非我将一个常量传递到函数中，在这种情况下，编译器只返回预先计算的常量）。 - Eclipse
@Wedge 从 2021 年的程序员到 2008 年的程序员，它会被内联为静态数据在可执行文件中，因此数组不需要被初始化。 - cdecompilador
19
伪代码中：
ans = 1
for i = n down to 2
ans = ans * i
next
- Vincent Ramdhanie
8
为了科学研究的目的，我对计算阶乘的各种算法实现进行了一些分析。我使用C#和C++分别创建了迭代、查找表和递归实现，并将最大输入值限制在12或更小，因为13!大于2^32（32位整数能够容纳的最大值）。然后，我运行了每个函数1000万次，循环使用可能的输入值（即从0递增到1000万，使用i模13作为输入参数）。
这里是不同实现相对于迭代C++数据的相对运行时间：
C++ C#
---------------------
Iterative 1.0 1.6
Lookup .28 1.1
Recursive 2.4 2.6
为了完整起见，以下是使用64位整数并允许输入值高达20的实现的相对运行时间：
C++ C#
---------------------
Iterative 1.0 2.9
Lookup .16 .53
Recursive 1.9 3.9
- Wedge
3
1也许更多是对C#和.Net的谴责 ;) - Richard A
那么，你在64位CPU上运行这些测试了吗？如果没有，那么我非常好奇为什么第二个测试中有一半的测试比第一个测试快。 - Dave Sherohman
每个表格中的数字都经过归一化处理，以适应该表格对应的 C++ 迭代次数，这些表格之间的比例并不相同。请注意，这些测试是在一个 32 位操作系统上执行的，64 位测试所需的时间比 32 位测试更长。 - Wedge
7
public double factorial(int n) {
double result = 1;
for(double i = 2; i<=n; ++i) {
result *= i;
}
return result;
}
- Chris Marasti-Georg
3
我认为你需要使用<=。阶乘函数factorial(3)返回2。 - MrDatabase
应该是 for(int i = 2; i<= n; ++i) - matt b
作业问题是允许的。今天早些时候有一个帖子提到了这一点。然而，对于回复中发布的代码，应该给出伪代码。 - Elie
5
将递归解决方案改写为循环。
- JohnMcG
5
除非你有像Python一样的任意长度整数，否则我会将factorial()预计算值存储在大约20个长整型的数组中，并使用参数n作为索引。n!的增长速度相当高，即使在64位机器上计算20！或21！也会发生溢出。
- Federico Ramponi
3
这是预计算函数，但实际上是正确的。正如所说，13！会溢出，因此计算这么小的值范围没有意义。64位更大，但我认为范围仍然相当合理。
int factorial(int i) {
static int factorials[] = {1, 1, 2, 6, 24, 120, 720,
5040, 40320, 362880, 3628800, 39916800, 479001600};
if (i<0 || i>12) {
fprintf(stderr, "Factorial input out of range\n");
exit(EXIT_FAILURE); // You could also return an error code here
}
return factorials[i];
}
- PhirePhly
2
我喜欢这个Pythonic的解决方案：
def fact(n): return (reduce(lambda x, y: x * y, xrange(1, n+1)))
- dangerouslyfacetious
2
long fact(int n) {
long x = 1;
for(int i = 1; i <= n; i++) {
x *= i;
}
return x;
}
- Bill the Lizard
2
int total = 1
loop while n > 1
total = total * n
n--
end while
- Elie
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接