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

Question

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

Answer 1

Во время выполнения это нерекурсивно. Во время компиляции это рекурсивно. Производительность во время выполнения должна быть 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 2

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

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

    return product;
}

Answer 3

Нерекурсивный факториал в 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 4

Рекурсивное использование JavaScript с кэшированием.

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

Answer 5

Повторяющийся:

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)

В этом случае хвостовая рекурсия использует аккумулятор, чтобы избежать накопления стековых вызовов.

Ссылка: Хвостовая рекурсия в Хаскеле

Answer 6

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 7

Я бы использовал памятку. Таким образом, вы можете написать метод как рекурсивный вызов и при этом получить большинство преимуществ линейной реализации.

Answer 8

предполагая, что вы хотите иметь дело с действительно большими числами, я написал бы это следующим образом. Эта реализация была бы полезна, если бы вы хотели приличную скорость для обычных случаев (низкие числа), но хотели бы иметь возможность обрабатывать некоторые очень сложные вычисления. Я бы посчитал это наиболее полным ответом в теории. На практике я сомневаюсь, что вам нужно будет вычислять такие большие факториалы для чего-либо, кроме домашней задачи

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

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

Answer 10

Псевдокод

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