Факторизация числа с помощью дерева | C++

Приветствую!

Во время изучения циклов часто попадается задание на вычисление факториала числа. Предполагается применение наивного алгоритма: итерация по циклу и мультипликатор.

Проблема в том, что факториал — быстрорастущая функция. Для небольших значений N значение N! имеет много значащих цифр.

Алгоритм вычисления деревом основан на идеи того, что длинные числа примерно одинаковой длины умножать эффективнее, чем длинное число умножать на короткое (как в наивной реализации). Поэтому нужно добиться, чтобы при вычислении факториала множители постоянно были примерно одинаковой длины.

Алгоритм:

1. Найдём произведение последовательных чисел от LEFT до RIGHT, обозначим его как factorialProduct(LEFT, RIGHT);

2. Разделим интервал от LEFT до RIGHT пополам и посчитаем factorialProduct(LEFT, RIGHT) как factorialProduct(LEFT, RIGHT) * factorialProduct(MIDDLE + 1, RIGHT), где MIDDLE — середина между LEFT и RIGHT, MIDDLE = (LEFT + RIGHT) / 2;

3. Аналогично разобьём factorialProduct(LEFT, RIGHT) и factorialProduct(MIDDLE + 1, RIGHT);

4. Повторим эту операцию, пока в каждом интервале останется не более двух множителей. Очевидно, что factorialProduct(LEFT, RIGHT) = LEFT, если LEFT и RIGHT равны, и factorialProduct(LEFT, RIGHT) = LEFT * RIGHT, если RIGHT больше LEFT на единицу. Чтобы найти N! нужно посчитать factorialProduct(2, N).

Пример:

Код алгоритма без реализации длинной арифметики на C++:

Послесловие:

Порешать задачи по программированию можно на CodinGame. -- © Bezukh Vladimir, 2019