Как бы вы написали нерекурсивный алгоритм для вычисления факториалов?

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). Затем я запускал каждую функцию 10 миллионов раз, циклически просматривая возможные входные значения (т.е. увеличивая i с 0 до 10 миллионов, используя 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

Если у вас нет целых чисел произвольной длины, как в Python, я буду хранить предварительно вычисленные значения factorial () в массиве длиной около 20 и использовать аргумент n в качестве индекса. Скорость роста n! довольно высока, а вычислительная 20! или 21! в любом случае вы получите переполнение даже на 64-битных машинах.

Answer 5

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

Answer 6

Переписать рекурсивное решение как цикл.

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

Я люблю питоническое решение этого:

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

Answer 9

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

Answer 10

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