你将如何编写一个非递归算法来计算n!？
denise
问问题
30282 次
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];
}
于 2008-10-23T20:20:21.493 回答
19
在伪代码中
ans = 1
for i = n down to 2
ans = ans * i
next
于 2008-10-23T20:04:47.420 回答
6
public double factorial(int n) {
double result = 1;
for(double i = 2; i<=n; ++i) {
result *= i;
}
return result;
}
于 2008-10-23T20:02:57.207 回答
6
为了科学的利益，我对计算阶乘的各种算法实现进行了一些分析。我在 C# 和 C++ 中创建了每个迭代、查找表和递归实现。我将最大输入值限制为 12 或更少，因为 13！大于 2^32（能够保存在 32 位 int 中的最大值）。然后，我运行每个函数 1000 万次，循环遍历可能的输入值（即，将 i 从 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
于 2008-10-24T00:15:55.993 回答
5
将递归解决方案重写为循环。
于 2008-10-23T20:02:43.103 回答
5
除非你有像 Python 那样的任意长度的整数，否则我会将 factorial() 的预计算值存储在一个大约 20 个 long 的数组中，并使用参数 n 作为索引。n 的增长率！相当高，计算20！或 21！无论如何，即使在 64 位机器上，你也会得到溢出。
于 2008-10-23T20:11:01.807 回答
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];
}
于 2008-10-23T21:17:00.397 回答
2
我喜欢 pythonic 解决方案：
def fact(n): return (reduce(lambda x, y: x * y, xrange(1, n+1)))
于 2009-01-26T22:57:27.673 回答
2
long fact(int n) {
long x = 1;
for(int i = 1; i <= n; i++) {
x *= i;
}
return x;
}
于 2008-10-23T20:03:55.457 回答
2
int total = 1
loop while n > 1
total = total * n
n--
end while
于 2008-10-23T20:04:46.343 回答
1
fac = 1 ;
for( i = 1 ; i <= n ; i++){
fac = fac * i ;
}
于 2008-10-23T20:04:39.857 回答
1
public int factorialNonRecurse(int n) {
int product = 1;
for (int i = 2; i <= n; i++) {
product *= i;
}
return product;
}
于 2008-10-23T20:05:34.330 回答
1
在运行时，这是非递归的。在编译时它是递归的。运行时性能应该是 O(1)。
//Note: many compilers have an upper limit on the number of recursive templates allowed.
template <int N>
struct Factorial
{
enum { value = N * Factorial<N - 1>::value };
};
template <>
struct Factorial<0>
{
enum { value = 1 };
};
// Factorial<4>::value == 24
// Factorial<0>::value == 1
void foo()
{
int x = Factorial<4>::value; // == 24
int y = Factorial<0>::value; // == 1
}
于 2009-01-26T14:48:07.583 回答
1
对于非递归方法，没有比这更简单的了
int fac(int num) {
int f = 1;
for (int i = num; i > 0; i--)
f *= i;
return f;
}
于 2019-07-09T04:53:42.017 回答
0
我会使用记忆。这样，您可以将方法编写为递归调用，并且仍然可以获得线性实现的大部分好处。
于 2008-10-25T19:48:08.680 回答
0
long fact(int n)
{
long fact=1;
while(n>1)
fact*=n--;
return fact;
}
long fact(int n)
{
for(long fact=1;n>1;n--)
fact*=n;
return fact;
}
于 2008-11-18T05:12:25.010 回答
0
伪代码
total = 1
For i = 1 To n
total *= i
Next
于 2008-10-23T20:04:23.617 回答
0
假设您希望能够处理一些非常大的数字，我将其编码如下。如果您希望在常见情况下（小数字）获得相当大的速度，但又希望能够处理一些超大量的计算，则此实现将适用。我认为这是理论上最完整的答案。在实践中，我怀疑除了家庭作业问题之外，您是否需要计算如此大的阶乘
#define int MAX_PRECALCFACTORIAL = 13;
public double factorial(int n) {
ASSERT(n>0);
int[MAX_PRECALCFACTORIAL] fact = {1, 1, 2, 6, 24, 120, 720, 5040, 40320,
362880, 3628800, 39916800, 479001600};
if(n < MAX_PRECALCFACTORIAL)
return (double)fact[n];
//else we are at least n big
double total = (float)fact[MAX_PRECALCFACTORIAL-1]
for(int i = MAX_PRECALCFACTORIAL; i <= n; i++)
{
total *= (double)i; //cost of incrimenting a double often equal or more than casting
}
return total;
}
于 2008-10-23T20:49:39.513 回答
0
迭代：
int answer = 1;
for (int i = 1; i <= n; i++){
answer *= i;
}
或者...在 Haskell 中使用尾递归：
factorial x =
tailFact x 1
where tailFact 0 a = a
tailFact n a = tailFact (n - 1) (n * a)
在这种情况下，尾递归的作用是使用累加器来避免堆栈调用堆积。
于 2012-08-09T16:18:34.493 回答
0
Java中的非递归阶乘。此解决方案使用自定义迭代器（以演示迭代器的使用:)）。
/**
* Non recursive factorial. Iterator version,
*/
package factiterator;
import java.math.BigInteger;
import java.util.Iterator;
public class FactIterator
{
public static void main(String[] args)
{
Iterable<BigInteger> fact = new Iterable<BigInteger>()
{
@Override
public Iterator<BigInteger> iterator()
{
return new Iterator<BigInteger>()
{
BigInteger i = BigInteger.ONE;
BigInteger total = BigInteger.ONE;
@Override
public boolean hasNext()
{
return true;
}
@Override
public BigInteger next()
{
total = total.multiply(i);
i = i.add(BigInteger.ONE);
return total;
}
@Override
public void remove()
{
throw new UnsupportedOperationException();
}
};
}
};
int i = 1;
for (BigInteger f : fact)
{
System.out.format("%d! is %s%n", i++, f);
}
}
}
于 2016-03-02T10:37:08.520 回答
-1
int fact(int n){
int r = 1;
for(int i = 1; i <= n; i++) r *= i;
return r;
}
于 2008-10-23T20:03:57.783 回答
-2
递归地使用带有缓存的 JavaScript。
var fc = []
function factorial( n ) {
return fc[ n ] || ( ( n - 1 && n != 0 ) &&
( fc[ n ] = n * factorial( n - 1 ) ) ) || 1;
}
于 2012-10-23T16:16:15.767 回答