Интересен алгоритмический подход, без необходимости вычислять 100! Он же существует?

задан 26 Мар '19 12:28

3

С трудом верится в возможность какого-то "обходного" способа нахождения суммы цифр.

Возможен такой подход получения приблизительной оценки. Мы знаем, что 100! оканчивается 24 нулями. При помощи формулы Стирлинга можно найти число десятичных цифр в записи факториала. Если все цифры кроме последних нулей считать "случайными" и в среднем равными 9/2, то такой способ даёт значение 603 (берём ближайшее кратное 9). Однако это далековато от верного ответа, равного 648.

(26 Мар '19 13:30) falcao

@falcao, а последовательно генерировать не держа в памяти весь ответ можно? Как например генерируют последовательно цифры числа ПИ.

(26 Мар '19 15:58) Isaev

@falcao, Иначе я не понимаю смысла задания, оно для компьютера, но не на столько же примитивно, чтобы просто посчитать результат и разбить его на составляющие... да и не каждый язык программирования может по-умолчанию работать с большими числами, а в задании ограничение до 10000! Потому я думаю должно существовать решение в пределах целых (0..2^32 допустим) не вычисляя факториал целиком

(26 Мар '19 17:09) Isaev

Нашёл тут ссылочку на последовательность http://oeis.org/A004152

(26 Мар '19 17:10) Isaev
2

@Isaev, тогда обходной способ - программно открыть страничку http://oeis.org/A004152/b004152.txt и прочитать строчку с соответствующим номером.

(26 Мар '19 17:49) knop
1

@falcao, среднее значение старшей цифры - не 4.5, а 5. Для последней ненулевой - тоже 5.

(26 Мар '19 17:54) knop

@knop, это не спортивно. Вот как пример https://www.wolframalpha.com/input/?i=sum+of+digits+of+100000! учитывая, что это web-интерфейс, считает буквально за 1-2 сек. Это явно не прямое умножение 100 тыс больших чисел с последующим разложением на символы и анализом

(26 Мар '19 18:51) Isaev
1

@knop: почему среднее значение 5? Для последней ненулевой -- понятно, а остальные считаются как бы "случайными". Они могут оказаться и нулями в том числе, если глубоко не анализировать.

@Isaev: я думаю, ограничение до 10000 рассчитано на обычный метод подсчёта, аккуратно оформленный. Скорее всего, это возможно. Больших чисел там не надо -- работа идёт с массивами цифр. Замечу также, что вычисление факториалов по заданному модулю делается "бесхитростно", в отличие от степеней. А то через теорему Вильсона мы умели бы быстро проверять простоту "огромных" чисел.

(26 Мар '19 18:55) falcao
показано 5 из 8 показать еще 3
10|600 символов нужно символов осталось
Знаете, кто может ответить? Поделитесь вопросом в Twitter или ВКонтакте.

Ваш ответ

Если вы не нашли ответ, задайте вопрос.

Здравствуйте

Математика - это совместно редактируемый форум вопросов и ответов для начинающих и опытных математиков, с особенным акцентом на компьютерные науки.

Присоединяйтесь!

отмечен:

×237
×108
×67

задан
26 Мар '19 12:28

показан
344 раза

обновлен
26 Мар '19 18:55

Отслеживать вопрос

по почте:

Зарегистрировавшись, вы сможете подписаться на любые обновления

по RSS:

Ответы

Ответы и Комментарии

Дизайн сайта/логотип © «Сеть Знаний». Контент распространяется под лицензией cc by-sa 3.0 с обязательным указанием авторства.
Рейтинг@Mail.ru