您将如何编写非递归算法来计算阶乘？

Question

您将如何编写非递归算法来计算 n!？

Answer 1

因为 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];
}

Answer 2

在伪代码中

ans = 1
for i = n down to 2
  ans = ans * i
next

Answer 3

为了科学的利益，我对计算阶乘的算法的各种实现进行了一些分析。 我用 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

Answer 4

public double factorial(int n) {
    double result = 1;
    for(double i = 2; i<=n; ++i) {
        result *= i;
    }
    return result;
}

Answer 5

将递归解决方案重写为循环。

Answer 6

除非像 Python 中那样有任意长度的整数，否则我会将 Factorial() 的预先计算值存储在大约 20 个长整型的数组中，并使用参数 n 作为索引。 n! 的增长率 比较高，计算20！ 或21！ 无论如何，即使在 64 位机器上，你也会遇到溢出。

Answer 7

这是预先计算的函数，但实际上是正确的。 正如前面所说，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];
} 

资料来源：http://ctips.pbwiki.com/Factorial

Answer 8

long fact(int n) {
    long x = 1;
    for(int i = 1; i <= n; i++) {
        x *= i;
    }
    return x;
}

Answer 9

int total = 1
loop while n > 1
    total = total * n
    n--
end while

Answer 10

我喜欢 pythonic 解决方案：

def fact(n): return (reduce(lambda x, y: x * y, xrange(1, n+1)))

Answer 11

fac = 1 ; 
for( i = 1 ; i <= n ; i++){
   fac = fac * i ;
}

Answer 12

public int factorialNonRecurse(int n) {
    int product = 1;

    for (int i = 2; i <= n; i++) {
        product *= i;
    }

    return product;
}

Answer 13

在运行时这是非递归的。 在编译时它是递归的。 运行时性能应为 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
}

Answer 14

对于非递归方法，没有比这更简单的了

int fac(int num) {
    int f = 1;
    for (int i = num; i > 0; i--)
        f *= i;
    return f;
}

Answer 15

伪代码

total = 1
For i = 1 To n
    total *= i
Next

Answer 16

假设您希望能够处理一些非常大的数字，我将按如下方式编码。 如果您希望在常见情况下（低数字）有足够的速度，但希望能够处理一些超繁重的计算，则可以使用此实现。 我认为这是理论上最完整的答案。 在实践中，我怀疑除了家庭作业问题之外，您是否需要计算如此大的阶乘

#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;

}

Answer 17

我会使用记忆法。 这样，您可以将该方法编写为递归调用，并且仍然可以获得线性实现的大部分好处。

Answer 18

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;
}

Answer 19

迭代：

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)

在这种情况下尾递归的作用是使用累加器来避免堆栈调用上的堆积。

参考：Haskell 中的尾递归

Answer 20

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);
        }
    }
}

Answer 21

int fact(int n){
    int r = 1;
    for(int i = 1; i <= n; i++) r *= i;
    return r;
}

Answer 22

递归地使用带有缓存的 JavaScript。

var fc = []
function factorial( n ) {
   return fc[ n ] || ( ( n - 1 && n != 0 ) && 
          ( fc[ n ] = n * factorial( n - 1 ) ) ) || 1;
}