¿Cómo escribirías un algoritmo no recursivo para calcular los factoriales?

Question

¿Cómo escribirías un algoritmo no recursivo para calcular n!?

Answer 1

Vuelva a escribir la solución recursiva como un bucle.

Answer 2

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

Answer 3

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

Answer 4

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

Answer 5

Pseudo código

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

Answer 6

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

Answer 7

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

Answer 8

en pseudocódigo

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

Answer 9

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

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

    return product; 
} 

Answer 10

A menos que tenga enteros de longitud arbitraria como en Python, almacenaría los valores precalculados de factorial() en una matriz de aproximadamente 20 longs, y usaría el argumento n como índice. La tasa de crecimiento de n! es bastante alto, y computa 20! o 21! Obtendrá un desbordamiento de todos modos, incluso en máquinas de 64 bits.

Answer 11

¡Ya que un Int32 se va a desbordar en algo más grande que 12! de todos modos, sólo hago:

public int factorial(int n) { 
    int[] fact = {1, 1, 2, 6, 24, 120, 720, 5040, 40320, 
       362880, 3628800, 39916800, 479001600}; 
    return fact[n]; 
} 

Answer 12

asumiendo que quería ser capaz de tratar con algunos números muy grandes, me codificarlo como sigue. Esta implementación sería para si deseabas una cantidad decente de velocidad para casos comunes (números bajos), pero quería poder manejar algunos cálculos súper fuertes. Consideraría que esta es la respuesta más completa en teoría. En la práctica, dudo que se necesita para calcular factoriales tan grandes para que no sea un problema de tarea

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

Ésta es la función precomputed nada, excepto realmente correcto. Como se dijo, 13! se desborda, por lo que no tiene sentido calcular un rango tan pequeño de valores. 64 bit es más grande, pero esperaría que el rango aún sea bastante razonable.

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

Fuente: http://ctips.pbwiki.com/Factorial

Answer 14

En aras de la ciencia me encontré con algunos perfiles en varias implementaciones de algoritmos para calcular los factoriales. Creé implementaciones iterativas, de búsqueda y recursivas de cada una en C# y C++. ¡Limité el valor de entrada máximo a 12 o menos, desde 13! es mayor que 2^32 (el valor máximo capaz de mantenerse en una int de 32 bits). Luego, ejecuté cada función 10 millones de veces, recorriendo los posibles valores de entrada (es decir, incrementando i de 0 a 10 millones, usando i módulo 13 como parámetro de entrada).

Aquí son los relativos tiempos de ejecución para diferentes implementaciones normalizaron a la iterativo C++ figuras:

  C++ C# 
--------------------- 
Iterative 1.0 1.6 
Lookup  .28 1.1 
Recursive 2.4 2.6 

Y, por completitud, aquí están los relativos tiempos de ejecución para las implementaciones utilizando enteros de 64 bits y que permite la entrada valores hasta 20:

  C++ C# 
--------------------- 
Iterative 1.0 2.9 
Lookup  .16 .53 
Recursive 1.9 3.9 

Answer 15

Me gustaría utilizar la memoria. De esta forma, puede escribir el método como una llamada recursiva y obtener la mayoría de los beneficios de una implementación lineal.

Answer 16

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 17

En tiempo de ejecución esto no es recursivo. En tiempo de compilación es recursivo. El rendimiento en tiempo de ejecución debe ser 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 18

Me encanta la solución a este Pythonic:

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

Answer 19

iterativo:

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

O ... usando la recursión de cola en Haskell:

factorial x = 
    tailFact x 1 
    where tailFact 0 a = a 
     tailFact n a = tailFact (n - 1) (n * a) 

Qué cola recursividad hace en este caso se utiliza una acumulación ulator para evitar acumular en llamadas de pila.

Referencia: Tail Recursion in Haskell

Answer 20

usando JavaScript de forma recursiva con el almacenamiento en caché.

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

Answer 21

Non recursive factorial en Java. Esta solución es con un iterador personalizado (para demostrar el uso del iterador :)).

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