|
Интересен алгоритмический подход, без необходимости вычислять 100! Он же существует? задан 26 Мар '19 12:28 
Isaev
показано 5 из 8
показать еще 3
|
Здравствуйте
Математика - это совместно редактируемый форум вопросов и ответов для начинающих и опытных математиков, с особенным акцентом на компьютерные науки.
Присоединяйтесь!
отмечен:
задан
26 Мар '19 12:28
показан
1490 раз
обновлен
26 Мар '19 18:55
Связанные вопросы
Дизайн сайта/логотип © «Сеть Знаний». Контент распространяется под лицензией cc by-sa 3.0 с обязательным указанием авторства.
С трудом верится в возможность какого-то "обходного" способа нахождения суммы цифр.
Возможен такой подход получения приблизительной оценки. Мы знаем, что 100! оканчивается 24 нулями. При помощи формулы Стирлинга можно найти число десятичных цифр в записи факториала. Если все цифры кроме последних нулей считать "случайными" и в среднем равными 9/2, то такой способ даёт значение 603 (берём ближайшее кратное 9). Однако это далековато от верного ответа, равного 648.
@falcao, а последовательно генерировать не держа в памяти весь ответ можно? Как например генерируют последовательно цифры числа ПИ.
@falcao, Иначе я не понимаю смысла задания, оно для компьютера, но не на столько же примитивно, чтобы просто посчитать результат и разбить его на составляющие... да и не каждый язык программирования может по-умолчанию работать с большими числами, а в задании ограничение до 10000! Потому я думаю должно существовать решение в пределах целых (0..2^32 допустим) не вычисляя факториал целиком
Нашёл тут ссылочку на последовательность http://oeis.org/A004152
@Isaev, тогда обходной способ - программно открыть страничку http://oeis.org/A004152/b004152.txt и прочитать строчку с соответствующим номером.
@falcao, среднее значение старшей цифры - не 4.5, а 5. Для последней ненулевой - тоже 5.
@knop, это не спортивно. Вот как пример https://www.wolframalpha.com/input/?i=sum+of+digits+of+100000! учитывая, что это web-интерфейс, считает буквально за 1-2 сек. Это явно не прямое умножение 100 тыс больших чисел с последующим разложением на символы и анализом
@knop: почему среднее значение 5? Для последней ненулевой -- понятно, а остальные считаются как бы "случайными". Они могут оказаться и нулями в том числе, если глубоко не анализировать.
@Isaev: я думаю, ограничение до 10000 рассчитано на обычный метод подсчёта, аккуратно оформленный. Скорее всего, это возможно. Больших чисел там не надо -- работа идёт с массивами цифр. Замечу также, что вычисление факториалов по заданному модулю делается "бесхитростно", в отличие от степеней. А то через теорему Вильсона мы умели бы быстро проверять простоту "огромных" чисел.