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

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 modulo 13作为输入参数将i从0增加到1000万).

以下是针对迭代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

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

Answer 5

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

Answer 6

除非像Python中那样有任意长度的整数,否则我会将factorial()的预先计算值存储在大约20个long的数组中,并使用参数n作为索引.n的增长率!相当高,计算20!或21!无论如何,即使在64位计算机上也会出现溢出.