Функции, включающие вычисление факториала, предоставляют широкие возможности для разработки умных алгоритмов экономии времени. Возьмем, к примеру, эту задачу из CTCI Гейл Лаакманн Макдауэлл:
Напишите функцию, которая возвращает количество конечных нулей для заданного факториала.
Попытка грубой силы будет состоять в том, чтобы вычислить факториал, а затем подсчитать нули в конце, используя модуль 10:
Хотя это выполняет свою работу, мы можем оптимизировать, если остановимся на рассмотрении того, какие целые числа способствуют добавлению конечных нулей в уравнение факториала или умножения. При умножении на 10 в конце добавляется ноль, как и при умножении на два числа, произведение которых равно 10.
Таким образом, мы можем сделать вывод, что факториал и подсчет нулей можно пропустить, если мы просто суммируем пары чисел, кратных 2 и 5. Будет гораздо больше кратных 2, поэтому мы можем сосредоточиться на подсчете пятерок.
Первый пограничный случай появляется на 25, так как это дает нам две пятерки (5 x 5). Таким образом, вместо того, чтобы считать числа, кратные пятерам, мы можем добавить к счетчику количество раз, когда пять входят в каждое число.
Есть еще одна оптимизация. Можете ли вы сказать, что это такое?
