Форум: "Потрепаться";
Текущий архив: 2002.09.02;
Скачать: [xml.tar.bz2];
ВнизПростенькая задачка Найти похожие ветки
← →
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]>MBo © (05.08.02 14:43)
Класс!
>Затрудняюсь показать это строго
Ну, на язык эпсилон-окрестностей скатываться не будем :)
Страницы: 1 вся ветка
Форум: "Потрепаться";
Текущий архив: 2002.09.02;
Скачать: [xml.tar.bz2];
Память: 0.5 MB
Время: 0.007 c