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

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

23.10.2008 20:01:25
Почему? Потому что вычислительная! рекурсивно поразительно медленно по сравнению с циклом.
BradC 23.10.2008 20:07:24
@BradC: На самом деле это не так, если вы используете динамическое программирование.
Can Berk Güder 23.10.2008 20:10:46
Я всегда предполагал, что это зависит от языка.
EBGreen 23.10.2008 20:18:50
большинство компиляторов оптимизируют хвостовую рекурсию, поэтому ваш пробег может меняться
Steven A. Lowe 23.10.2008 20:34:53
Hafthor 23.10.2008 20:36:30
22 ОТВЕТА

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

4
23.10.2008 20:02:43
public double factorial(int n) {
    double result = 1;
    for(double i = 2; i<=n; ++i) {
        result *= i;
    }
    return result;
}
6
23.10.2008 20:10:10
Я думаю, что вам нужно <=. factorial (3) возвращает 2.
MrDatabase 23.10.2008 20:06:00
должно быть для (int i = 2; i <= n; ++ i)
matt b 23.10.2008 20:07:18
Домашние задания разрешены. Ранее сегодня был пост об этом. Тем не менее, код, который публикуется в ответ, должен иметь псевдокод.
Elie 23.10.2008 20:07:31
long fact(int n) {
    long x = 1;
    for(int i = 1; i <= n; i++) {
        x *= i;
    }
    return x;
}
2
23.10.2008 20:03:55
int fact(int n){
    int r = 1;
    for(int i = 1; i <= n; i++) r *= i;
    return r;
}
-1
25.10.2008 19:45:17

Псевдокод

total = 1
For i = 1 To n
    total *= i
Next
0
23.10.2008 20:04:23
fac = 1 ; 
for( i = 1 ; i <= n ; i++){
   fac = fac * i ;
}
0
23.10.2008 20:05:24
int total = 1
loop while n > 1
    total = total * n
    n--
end while
2
23.10.2008 20:04:46

в псевдокоде

ans = 1
for i = n down to 2
  ans = ans * i
next
18
23.10.2008 20:04:47
public int factorialNonRecurse(int n) {
    int product = 1;

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

    return product;
}
1
23.10.2008 20:12:50

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

5
23.10.2008 20:22:04

Поскольку 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];
}
28
26.01.2009 14:40:25
фиксированный. Чертов нулевой индекс !!
BradC 23.10.2008 21:14:39
Как написано, это будет на самом деле медленнее, поскольку при инициализации массива каждый вызов будет стоить дороже, чем ~ 12 операций умножения (примерно в 2 раза). Таблица хорошего просмотра должна использовать статические данные. Кроме того, что происходит, когда я передаю 13 или -20 для этой функции?
Wedge 23.10.2008 21:26:09
Кроме того, число от второго до последнего должно быть 39916800, а не 3991800 (это может иллюстрировать проблему с поиском таблиц).
Wedge 23.10.2008 23:10:43
Например, в Ruby, где он автоматически переключается в большое целочисленное представление.
martinus 16.01.2009 22:16:03
@Wedge - мой компилятор говорит, что поиск быстрее в два раза (если я не передам константу в функцию, и в этом случае компилятор просто возвращает предварительно вычисленную константу)
Eclipse 26.01.2009 23:19:56

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

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

}
0
24.10.2008 21:06:17
У вас есть две ошибки в вашей поисковой секции. Ваш чек должен быть <= 12 и 1! не равно 2. Кроме того, вы скопировали ошибку выше для 11 !, это должно быть 39916800, а не 3991800 (обратите внимание на пропущенные 6). Кроме того, это требует проверки ошибок. Что такое факториал (-10)? или факториал (500)?
Wedge 24.10.2008 00:31:43
(это был урок, потому что вы никогда не должны слепо копировать домашнее задание по CS без тестирования :)) Исправлено. Assert добавлен, исправлено значение MAX для включения нового номера (поэтому <= не требуется). Теперь это будет работать как двойная версия, если это необходимо по какой-либо причине.
David Frenkel 24.10.2008 21:05:02
Отлично. Вы, вероятно, хотите использовать слишком большие входные значения. С помощью факториала вы можете легко переполнить даже двойное число.
Wedge 24.10.2008 21:34:27

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

3
23.10.2008 21:17:00

В интересах науки я провел профилирование различных реализаций алгоритмов для вычисления факториалов. Я создал итеративную, справочную таблицу и рекурсивные реализации каждой из них на 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
6
24.10.2008 00:15:55
Возможно, это скорее указание на C # и .Net;)
Richard A 24.10.2008 01:10:45
Так вы запускали эти тесты на 64-битном процессоре? Если нет, то мне очень интересно, почему половина тестов будет быстрее во втором тесте, чем в первом.
Dave Sherohman 18.11.2008 06:06:43
Цифры в каждой таблице нормализованы к итерационным временам C ++ для этой таблицы, таблицы не должны масштабироваться друг с другом. Обратите внимание, что эти прогоны выполнялись на 32-битной ОС, и 64-битные тесты занимали больше времени, чем 32-битные.
Wedge 18.11.2008 17:02:26

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

0
25.10.2008 19:48:08
Возможно, вы думаете о последовательности Фибоначчи - факториал не выигрывает от запоминания.
Kyle Cronin 25.10.2008 20:07:32
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;
}
0
1.11.2011 17:44:49

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

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

def fact(n): return (reduce(lambda x, y: x * y, xrange(1, n+1)))
2
26.01.2009 22:57:27

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

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)

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

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

0
9.08.2012 16:18:34

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

var fc = []
function factorial( n ) {
   return fc[ n ] || ( ( n - 1 && n != 0 ) && 
          ( fc[ n ] = n * factorial( n - 1 ) ) ) || 1;
}
-2
23.10.2012 16:16:15
Да, но вопрос был без рекурсии .
Konrad Rudolph 23.10.2012 16:18:17
Смотрите текст вопроса. "не рекурсивный"
hsanders 23.10.2012 16:37:42

Не рекурсивный факториал в 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);
        }
    }
}
0
2.03.2016 10:37:08

Для нерекурсивного подхода это не может быть проще, чем это

int fac(int num) {
    int f = 1;
    for (int i = num; i > 0; i--)
        f *= i;
    return f;
}
0
9.07.2019 04:53:42