«Это первая из серии постов, в которых я расскажу о некоторых алгоритмических головоломках, которые я нашел интересными и которые мне понравилось решать».

Несколько дней назад я наткнулся на сообщение в LinkedIn, в котором были показаны различные временные сложности, с которыми обычно сталкиваются при решении вопросов по программированию. Из всех, O (n!) Был самым ресурсоемким. Он также упомянул, что значения ввода всего 25 в факториальной программе могут привести к целочисленному переполнению даже в таких языках, как python. Все это довольно просто, и вы должны это уже знать, и я тоже, но это действительно заставило меня задуматься, насколько большой будет ценность… допустим, 1000 !? Итак, я решил написать факторную программу, чтобы убедиться в этом сам.

Чтобы вычислить значение n !, я инициализировал answer как единицу и i (переменная счетчика) как два. Затем умножил ответ на i, а затем увеличил i. Это выполняется в цикле до тех пор, пока ответ не достигнет большого значения. На этом этапе следующее умножение может привести к возможному переполнению. Итак, я добавил этот ответ в список и снова продолжил с того же значения i. Это снова делается итеративно.

В конце, когда i достигнет желаемого значения (равного n), у нас будет список, состоящий из очень больших чисел. Теперь все, что нам нужно сделать, это перемножить их вместе.

В своей первой программе я преобразовал большие числа в строку, а затем использовал метод длинного умножения (то, что мы делали в школе), который на самом деле не лучший метод для умножения больших чисел, поскольку он очень медленный, но он служил предназначение (для не очень большого количества конечно!)

Позже я немного изменил его, чтобы сохранить промежуточные значения ответа в виде списка. Затем одно за другим выбирали целое число из нашего ранее созданного списка больших чисел и умножали его непосредственно на каждую цифру в нашем списке ответов, заботясь о сгенерированных переносах. Вот и все, теперь он готов к выполнению для больших значений n. Я пробовал это с 1000, 5000, переходя к 50 000 (на моем ноутбуке это заняло около 10 минут).

Для 50 000 ответ был - 213238 цифр! Вы можете проверить ссылку, чтобы увидеть окончательный результат.

БОНУС - Факториал 100 000 (вычисление заняло больше часа)