Найти количество цифр n!(n 10^9)

Пример:

10

Вывод:

7

Поясняю 10! = 3628800, тут 7 цифр

Это сообщение отредактировал(а) altairaimenov - 3.3.2015, 18:28

В целом числе ровно floor(log(x)) + 1 цифр. (log10 разумеется имеется ввиду)

Можно решить апромиксацией стирлинга: http://en.wikipedia.org/wiki/Stirling%27s_approximation

То есть:

Найти a = sqrt(2*PI * n) * (n/e)^n
Потом b = a * (1 + 1/(12*n - 1))
где PI - это число пи, а e - число ейлера

Найти кол-во цифр в a и b. Если одинаковое то ответ есть, если не одинаковое, что будет редко, то наверное можно как-то подругому проверить. Пока других идей в голову не лезет

Пример:

n = 10
a = 3598695.[...]
b = 3628936.[...]

кол-во цифр в а = 7
кол-во цифр в b = 7
ответ 7

Это сообщение отредактировал(а) sQu1rr - 3.3.2015, 19:05

Во-первых, это однозначно в "Центр помощи".
Во-вторых, язык то какой: С или С++?

Общая идея такова.

• Число цифр в числе m можновычислить как ceil(log10(m)).
• Факториал n! = 1 * 2 * ... * n-1 * n.
• Значит число цифр в n! равно ceil(log10(n!)) = ceil(log10(1 * 2 * ... * n-1 * n)) = ceil(log10(1) + log10(2) + ... + log10(n-1) + log10(n)).

На сишечке на коленках как-то так:


Добавлено @ 18:59

Да не, не надо тут никаких аппроксимаций. Танцуем от того, что логарифм произведения равен сумме логарифмов.  

Это сообщение отредактировал(а) kemiisto - 3.3.2015, 19:07

ceil(log10(100)) = ceil(2.0) = 2 

Добавлено через 1 минуту и 1 секунду



Слишком много считать не?

sQu1rr, тоже верно. Таки floor(log10(m)) + 1 всегда будет работать.

Добавлено через 4 минуты и 54 секунды

В смысле, долго? А кому сейчас легко?  Зато, наверняка.

Добавлено через 5 минут и 58 секунд

Меньше минуты на моём старье. Меня устраивает.  

Это сообщение отредактировал(а) kemiisto - 3.3.2015, 19:06

Ну питон не думая это решает. Зачем утруждать комп ненужным

Не совсем понял, о чём ты. Точнее, совсем не понял.

Примерно так: "Даже такой медленный интерпретируемый язык как питон, решает эту задачу моим способом меньше чем за секунду (точнее моментально), а не за минуту на С. Зачем мучать свое железо вычеслениями, когда можно сделать проще - и самому не ждать и железо не утруждать."

Ну, release-версия, собранная с -O3, считает за 15 секунд.  Собственно, твоего кода я в топике не вижу, но если он основан на приближении Стирлинга, то ничего удивительного, что у тебя быстрее получилось "даже" на Python. Вот только какой смысл сравнивать время получения приближённого и точного* решения? Ежу понятно, что приближённый ответ можно получить быстрее.  

Это сообщение отредактировал(а) kemiisto - 4.3.2015, 00:17

а нужен ли точный ответ? для 1е9 число цифр по первому приближению стирлинга совпадает с вашей суммой.
погрешность определения числа цифр гораздо меньше, чем погрешность самого факториала.
кстати, с чего вы взяли, что ваш результат точен: и логарифм, и суммирование это заведомо неточные операции.

Добавлено через 59 секунд
http://ideone.com/KCrQmy

Откуда мне знать. ТС так и не объявлялся. Однако обычно, если не указано иное, нужен именно точный ответ. Зачем считать заведомо приближённо, если можно посчитать точно? Дался вам этот Стирлинг.  


Да ну прямо счаз. Там double всё-таки. Гарантированно 15–17 значащих цифр. Аргументы логарифма до 10^9, сами значения от 0 до 9. Каким образом Вы тут собрались накопить ошибку при 15–17 значащих цифрах? Арифметика с плавающей точкой, конечно, неточная, но она ж не всегда настолько неточная, чтоб за компьютер вообще не садиться.  

на 1e9 сложениях при 15 значащих цифрах может накопиться погрешность порядка 1e-6. пустячок, но приятно))

взаимоисключающие параграфы однако 


Ну так мой аргумент же скорость. Я полностью согласен что можно считать и не приближением, и будет меньше погрешность скорее всего, но зачем?


Точный ответ в кол-ве цифр, а не факториала. Приблежение стирлинга с этим вполне хорошо справляется.

Да и вообще спор бесмыслен. вы предложили один способ, я второй. В отличие от вас, я не говорю про ваш способ "не нужен". Для ОП это будет возможность попробовать оба, и еще и математики подучить.

Почему?  


Бывает, что нужно быть абсолютно уверенным в ответе, и ради этого можно и подождать.


Вы можете гарантировать (доказать), что для всех чисел до 10^9 использование формулы Стирлинга даст верное число цифр?

Это сообщение отредактировал(а) kemiisto - 4.3.2015, 15:13

У меня нет компилятора под рукой - проверьте пожалуйста. А вы можете за разумное время гарантировать то же самое про свой метод? Не считая матиматически доказуемой незначительной погрешности, которая все таки может сыграть свою роль, хоть это и настолько маловероятно, что даже проверять не стоит.



Ну релиз в -O3 не компилируется. -O3 сам по себе подрузамевает тестинг.



Согласен. Если это нужно - ваш способ - верный путь.