Как бы вы написали нерекурсивный алгоритм для вычисления n!?
Как бы вы написали нерекурсивный алгоритм для вычисления факториалов?
Ответ 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];
}
Ответ 2
в псевдокоде
ans = 1
for i = n down to 2
ans = ans * i
next
Ответ 3
В интересах науки я провел некоторое профилирование по различным реализациям алгоритмов для вычисления факториалов. Я создал итеративную таблицу поиска и рекурсивную реализацию каждого в С# и С++. Я ограничил максимальное входное значение до 12 или меньше, так как 13! больше 2 ^ 32 (максимальное значение, которое может удерживаться в 32-битном int). Затем я выполнял каждую функцию 10 миллионов раз, циклически используя возможные входные значения (то есть увеличивая я от 0 до 10 миллионов, используя я modulo 13 в качестве входного параметра).
Вот относительные времена выполнения для разных реализаций, нормированных на итеративные цифры С++:
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
Ответ 4
public double factorial(int n) {
double result = 1;
for(double i = 2; i<=n; ++i) {
result *= i;
}
return result;
}
Ответ 5
Если у вас нет целых чисел произвольной длины, как в Python, я бы сохранил предварительно вычисленные значения factorial() в массиве длиной около 20 longs и использовал аргумент n в качестве индекса. Скорость роста n! довольно высока и вычисляет 20! или 21! вы все равно получите переполнение, даже на 64-битных машинах.
Ответ 6
Перепишите рекурсивное решение как цикл.
Ответ 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
Ответ 8
long fact(int n) {
long x = 1;
for(int i = 1; i <= n; i++) {
x *= i;
}
return x;
}
Ответ 9
int total = 1
loop while n > 1
total = total * n
n--
end while
Ответ 10
Мне нравится решение pythonic для этого:
def fact(n): return (reduce(lambda x, y: x * y, xrange(1, n+1)))
Ответ 11
public int factorialNonRecurse(int n) {
int product = 1;
for (int i = 2; i <= n; i++) {
product *= i;
}
return product;
}
Ответ 12
Во время выполнения это нерекурсивный. Во время компиляции оно рекурсивно. Производительность исполнения должна быть 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
}
Ответ 13
Псевдокод
total = 1
For i = 1 To n
total *= i
Next
Ответ 14
fac = 1 ;
for( i = 1 ; i <= n ; i++){
fac = fac * i ;
}
Ответ 15
Предполагая, что вы хотите иметь дело с некоторыми действительно огромными числами, я бы закодировал его следующим образом. Эта реализация будет заключаться в том, если вы хотите приличную скорость для обычных случаев (низкие числа), но хотели бы иметь возможность обрабатывать некоторые сверхнадежные вычисления. Я бы счел это самым полным ответом в теории. На практике я сомневаюсь, что вам нужно будет вычислить такие большие факториалы для чего-либо иного, кроме проблемы домашней работы
#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;
}
Ответ 16
Я бы использовал memoization. Таким образом, вы можете написать метод как рекурсивный вызов и по-прежнему получать большую часть преимуществ линейной реализации.
Ответ 17
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;
}
Ответ 18
Итерационный:
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
Ответ 19
Нерекурсивный факториал в 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);
}
}
}
Ответ 20
Для нерекурсивного подхода это не может быть проще, чем это
int fac(int num) {
int f = 1;
for (int i = num; i > 0; i--)
f *= i;
return f;
}
Ответ 21
int fact(int n){
int r = 1;
for(int i = 1; i <= n; i++) r *= i;
return r;
}
Ответ 22
Рекурсивно использовать JavaScript с кешированием.
var fc = []
function factorial( n ) {
return fc[ n ] || ( ( n - 1 && n != 0 ) &&
( fc[ n ] = n * factorial( n - 1 ) ) ) || 1;
}