Простенькая задачка

← →
MBo (2002-08-02 12:48) [0]

Не по програмированию, но может, кому любопытно будет:
Найти количество десятичных цифр в числе N! (факториал)

← →
VictorT (2002-08-02 13:03) [1]

А такой метод не подходит, просто посчитать факториал, а потом в результате кол-во цифр?

← →
Igorek (2002-08-02 13:04) [2]

int(lg(1) + lg(2) + ... + lg(N)) + 1

не уверен ;-)

← →
Igorek (2002-08-02 13:07) [3]

2VictorT © (02.08.02 13:03)

> А такой метод не подходит, просто посчитать факториал, а
> потом в результате кол-во цифр?

А для того, что-бы узнать расстояние до другой галактики обязательно туда лететь и включать спидометр? ;-)

← →
VictorT (2002-08-02 13:10) [4]

> Igorek © (02.08.02 13:07)

Ну, я бы сказал, что твой способ не проще, чем расчёт факториала.

← →
MBo (2002-08-02 13:14) [5]

>VictorT
факториал очень быстро растет, числа могут быть очень велики

>Igorek
да, правильно.
Есть способ быстрее, требует знания одной формулы.

← →
Igorek (2002-08-02 15:11) [6]

2 MBo © (02.08.02 13:14)

> Есть способ быстрее, требует знания одной формулы.

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

← →
Alx2 (2002-08-02 15:15) [7]

>MBo © (02.08.02 13:14)
Стирлинга? :)

← →
Alx2 (2002-08-02 15:21) [8]

По Стирлингу: 1/2*(2*n*ln(n)-2*n+ln(2*Pi*n))/ln(10)+1
Более точно (асимптотическое разложение с тремя членами):
-1/2*(-2*ln(288*n^2+24*n+1)+3*ln(n)-2*n*ln(n)+2*n+ln(41472*1/Pi))/ln(10)+1

← →
MBo (2002-08-02 15:32) [9]

>Igorek Alx2
да, я имел в виду по Стирлингу
n!~(n/e)^n*Sqrt(2*Pi*n)*(1+1/12n+1/288n^2...)

NC:=n*Lg10(n/e)+1/2*Lg10(2*Pi*N)+1 (приближенно, без ряда)

← →
MBo (2002-08-05 07:06) [10]

Из дидактических целей ;) отмечу, что метод, предложенный Igorek © (02.08.02 13:04), бывает иногда весьма полезен. Молодежь уже не знает, что раньше в школе (калькуляторы были не всегда) для вычислений пользовались 4-х-значными логарифмическими таблицами Брадиса (в технике применялись и более точные варианты). С помощью известных свойств логарифма можно умножение и деление заменять соответственно менее трудоемкими при вычислениях вручную сложением и вычитанием логарифмов соответствующих чисел. На этом же принципе построена и работа ранее широко применявшихся логарифмических линеек. В применении к данному случаю использование логарифмов позволяет избежать работы с очень большими числами и без применения специальных библиотек найти или хотя бы оценить результат.
Еще пример: найти при заранее неизвестных сомножителях (т.е. априорное сокращение невозможно) результат деления/умножения
Q=(a)^b/(c^d)
W:=Lg(Q):=b*Lg(a)-d*Lg(c)
Q:=10^W
для a=20 b=10000 c=10^131 d=100
W=10000*1.302-100*131=10
Q=10^10
при непосредственном вычислении для очень больших или маленьких значений сомножителей может возникнуть арифметическое переполнение или по крайней мере потеря точности.

← →
Igorek (2002-08-05 10:14) [11]

MBo © (05.08.02 07:06)
Ну хорошо, найти десятичный логарифм с помощью логарифмической линейки просто. А как просто возвести 10 к дробной степени?

← →
MBo (2002-08-05 10:20) [12]

точно так же, только наоборот - по логарифму смотрим 10в этой степени
например 10^2.47
0.47 на лог. шкале дает 3 на нормальной, т.е. получается 300

← →
Alx2 (2002-08-05 11:42) [13]

Еще задачка:
Может ли степень двойки начинаться на 7?

← →
MBo (2002-08-05 11:55) [14]

70368744177664=2**46

← →
Виктор Щербаков (2002-08-05 12:02) [15]

MBo © (05.08.02 11:55)
Хорошее решение :)

← →
Alx2 (2002-08-05 12:05) [16]

>MBo © (05.08.02 11:55)
А во сколько раз семерка встречается реже остальных цифр?

← →
MBo (2002-08-05 12:32) [17]

>Alx2
решал в целых числах
n=log2(2^n)
7*10^k<=2^n<8*10^k

n>=2.8+k*3.311
n<3+k*3.311

очевидно, логарифмический промежуток от J до J+1 (j-1..9)
уменьшается с ростом J, так что 8 и 9 еще реже будут. IMHO.

← →
MBo (2002-08-05 12:38) [18]

если эти соображения правильны, то вероятность первой 7 около 0.06 (log2(8)-log2(7))/log2(10)

← →
Alx2 (2002-08-05 12:43) [19]

>MBo © (05.08.02 12:38)

Хм... у меня несколько другое мнение было, но оно начинает трещать :)

Сейчас поищу противоречия....

← →
Alx2 (2002-08-05 12:56) [20]

Борис, ты прав :)
Я сначала было подумал, что частота встреч одинаковая. Потом просек, что кое-что упустил.

Рассуждал так: десятичную логарифмическую шкалу намотал на окружность длиной 1. Получилось, что количество оборотов по этой окружности даст порядок числа. Угол поворота деленный на 2 * Pi - мантиссу. Так как порядок числа нас не интересует, можно остановиться только на мантиссе. Умножение некоторого числа на 2 приведет к перемещению по нашей окружности на lg(2). Так как lg(2) - иррациональное, то двигаясь с таким шагом по окружности мы побываем в любой ее точке, причем каких-то особо выделенных точек нет. Отсюда вывод, что частота попадания в некоторый интервал есть длина этого интервала. Следовательно, частота семерки = длина интервала от 7 до 8 = lg(8)-lg(7), что ты уже и написал :)
А сбило меня то, что lg(x+1)-lg(x)<>const - мозгом пернул, так сказать :)

← →
MBo (2002-08-05 13:05) [21]

Задачка оказалась любопытной, раньше не доводилось с таким типом встречаться. Наводка про логарифмы помогла, конечно

← →
Alx2 (2002-08-05 14:23) [22]

А вот еще из той же оперы:
Показать, что можно подобрать такое целое n, чтобы с любой, наперед заданной точностью выполнялось sin(n+1)=sin(n)

← →
MBo (2002-08-05 14:43) [23]

E=sin(n+1)-sin(n)=2*sin(1/2)*cos(n+1/2)
отбросим константу (порядка 1)
cos(n+1/2)->0
n+1/2->Pi/2+Pi*K
опять уравнение в целых числах
N~~A+Pi*K
поскольку инкременты левой и правой части не связаны между собой рациональной дробью p/q, найдется пара N и K, при которых
N-Pi*K-A< любого E1 (зависящего от E). Затрудняюсь показать это строго

← →
Alx2 (2002-08-05 15:17) [24]

Простенькая задачка Найти похожие ветки