Алгоритмы для вычисления факториала — это алгоритм определения произведения всех натуральных чисел, начиная от единицы и до заданного числа включительно.
Под термином факториал числа понимается функция, которая вычисляет произведение последовательности натуральных чисел от единицы до N включительно: N! = 1 • 2 • 3 • … • N. Факториал является очень быстро увеличивающейся функцией, поскольку даже при относительно малых по величине N, значение его факториала будет уже многоразрядным. Рассмотрим некоторые алгоритмы, позволяющие вычислить факториал числа.
Наивный алгоритм
Этот алгоритм является самой простой реализацией, так как просто выполняет действия, заложенные в определении факториала:
Рисунок 1. Наивный алгоритм. Автор24 — интернет-биржа студенческих работ
Эта программа выполняется за интервал времени менее двух секунд для N до пятидесяти тысяч. Но есть и более продвинутые алгоритмы и один из них рассмотрим далее.
Алгоритм вычисления деревом
Этот алгоритм базируется на таком положении, что операция умножения с числами большой и примерно одинаковой разрядности будет эффективнее умножения большого числа на маленькое. Исходя из этого, необходимо обеспечить при определении факториала примерно равный размер сомножителей на постоянной основе. Пускай требуется вычислить произведение последовательности чисел от L до R. Введём обозначение этого произведения как Р (L, R). Поделим промежуток между L и R на два и вычислим Р (L, R) как P(L, M) • P(M + 1, R), здесь M является серединой чисел L и R, то есть M = (L + R) / 2. Следует отметить, что сомножители получаются примерно одинаковыми. Затем по аналогии разбиваем далее P(L, M) и P(M + 1, R). Эту процедуру необходимо выполнять до тех пор, пока каждый интервал не будет иметь больше двух сомножителей. Понятно, что Р (L, R) = L, когда L и R равны, и P(L, R) = L • R, если L и R имеют единичное отличи. Для того, чтобы вычислить N!, требуется определить Р(2, N). Рассмотрим действие этого алгоритма для N=10, определим Р (2, 10):
P(2, 10)
P(2, 6) • P(7, 10)
( P(2, 4) • P(5, 6) ) • ( P(7, 8) • P(9, 10) )
( (P(2, 3) • P(4) ) • P(5, 6) ) • ( P(7, 8) • P(9, 10) )
( ( (2 • 3) • (4) ) • (5 • 6) ) • ( (7 • 8) • (9 • 10) )
( ( 6 • 4 ) • 30 ) • ( 56 • 90 )
( 24 • 30 ) • ( 5 040 )
720 • 5 040
3 628 800
В итоге мы получили подобие дерева, у которого сомножители расположены в узлах, а результирующее значение находится в корневой системе.
Рисунок 2. Дерево. Автор24 — интернет-биржа студенческих работ
Программная реализация этого алгоритма приведена ниже:
Рисунок 3. Программа. Автор24 — интернет-биржа студенческих работ
По этой программе для числа пятьдесят тысяч вычисление факториала длится менее секунды, что в два раза быстрее предыдущего алгоритма.
Алгоритм вычисления факторизацией
Данный алгоритм способен разложить факториал на простые сомножители, что и есть по сути факторизация. То есть в преобразовании N! принимают участие только простые сомножители от двух до N. Вычислим количество вложений сомножителя К в факториал N!. Или иначе, определим в какой степени стоит сомножитель К в этом разложении. Каждый К-ый сомножитель произведения 1 • 2 • 3 • … • N приводит к возрастанию степени на единицу, то есть степень равняется N / K. Далее учитываем, что K в квадрате компонент также даёт возрастание степени на единицу, то есть показатель степени будет $N / K+ N / K^2$
Далее с возрастанием степени будет такая же картина. В финале имеем следующую формулу для показателя степени простого сомножителя К:
$N / K+ N / K^2 + N / K^3 + N / K^4 +…$
Для примера определим, сколько раз двойка в различных степенях входит в факториал десяти. Число два содержится в каждом втором сомножителе (2, 4, 6, 8 и 10). А общее число этих сомножителей 10 / 2 = 5. При этом, каждый четвёртый множитель выдаёт число четыре (то есть два в степени два). Этих сомножителей 10 / 4 = 2 (4 и 8). Далее восьмой сомножитель даёт число восемь (то есть два в степени три). Такой сомножитель только один 10 / 8 = 1 (8). Два в четвёртой степени — это число шестнадцать. Но его нет ни в одном сомножителе, следовательно, алгоритм можно останавливать. В итоге видим, что степень числа два при разложении факториала десяти на простые сомножители равняется 10 / 2 + 10 / 4 + 10 / 8 = 5 + 2 + 1 = 8.
Аналогично возможно определить показатели степени других простых сомножителей в факториале десяти (это числа три, пять и семь). Затем уже можно определить их произведение: $10! = 2^8 • 3^4 • 5^2 • 7^1 = 3 628 800$.
