Сколько вариантов чисел?

← →
Anatoly Podgoretsky © (2009-07-23 10:45) [40]

> @!!ex (23.07.2009 01:34:33) [33]

Не уговаривай, будем вместе мучаться.

← →
Sha © (2009-07-23 10:57) [41]

> Bless © (23.07.09 09:50) [37]
> Если я ничего не путаю, то это не может быть правильным ответом

Тут ты прав.
Я, видно, совсем расслабился на отдыхе, включение-исключение не заметил.
Там надо чередование знаков.
F(10,18) = 10^18 – C(10,1)*9^18 + C(10,2)* 8^18 - C(10,3)* 7^18 + C(10,4)* 6^18 … - C(10,9)*1^18.
Т.к. в первом слагаемом, например, числа в которых отсутствуют цифры 1 и 2, будет учтена дважды, и т.д.

> Bless © (23.07.09 10:30) [39]
> Вместе пишется только в предложениях типа "ввиду сложившихся обстоятельств..."

А тут ты не прав, "иметь ввиду" тоже вместе.

← →
Sha © (2009-07-23 10:59) [42]

Т.к. в первом вычитаемом, блин

← →
Bless © (2009-07-23 11:02) [43]

> Sha © (23.07.09 10:57) [41]
> А тут ты не прав, "иметь ввиду" тоже вместе.
>

http://gramota.ru/slovari/dic/?word=%E2+%E2%E8%E4%F3&all=x

ввиду, предлог (ввиду того что...; ввиду предстоящих расходов), но сущ. в виду (иметь в виду; бросить якорь в виду берега)

← →
palva © (2009-07-23 11:07) [44]

> F(10,18) = 10^18 – C(10,1)*9^18 – C(10,2)* 8^18 - … - C(10,9)*1^18

Здесь от общего количества последовательностей должны быть отняты те последовательности, которые не удовлетворяют условию (все цифры присутствуют). Вычитание происходит порциями, однако эти порции имеют непустое пересечение. В результате одна и та же последовательность отбрасывается несколько раз.

Возьмем первую порцию с мощностью C(10,1)*9^18 Она по замыслу (если я его понял) должна содержать все последовательности в записи которых не участвует одна цифра, но в ней также содержатся все последовательности в которых не участвуют две цифры, три цифры и т. д. Поэтому вычитать C(10,2)* 8^18 и т. д. уже не нужно. Все уже учтено.

Теперь о самом количестве C(10,1)*9^18 По-моему, оно подсчитано неправильно. Здесь мы пытались сосчитать отдельно те последовательности в которых не участвует цифра 0, цифра 1 и т. д. Но если в последовательности не участвует две цифры 0 и 1, то эта последовательность будет сосчитана два раза.

Есть такая комбинаторная формула включения и исключения. Скорее всего, она должна сработать. К сожалению у меня нет времени подумать на эту тему.

← →
palva © (2009-07-23 11:10) [45]

> Sha © (23.07.09 10:57) [41]

Вот это похоже на правду.
(Пока писал, тут изменения произошли)

← →
Sha © (2009-07-23 11:27) [46]

> Bless © (23.07.09 11:02) [43]
согласен

← →
palva © (2009-07-23 11:36) [47]

Чтобы увидеть работу формулы включения исключения, можно рассуждать так:
Обозначим через p(n1,n2, ...) число последовательностей, в которые не входят цифры n1,n2,... (может быть, еще какие-то цифры не входят, но это уже не важно). Это число равно (10-n)^18, где n - количество параметров в скобках. Тогда ответом будет:
p() - p(0) - p(1) - ... - p(9) +
p(0,1) + p(0,2) + ... + p(8,9) -
p(0,1,2) - ... - p(7,8,9) +
...
p(0,1,2,3,4,5,6,7,8,9).
Что и даст ответ, приведенный Sha

← →
Sha © (2009-07-24 10:32) [48]

Кстати, из того, что F(m,m)=m! следует интересное соотношение:

m^m - m! = S(i:=1..m-1) (-1)^(i-1) * C(m,i) * (m-i)^m,

где через S(i:=1..m-1) обозначена сумма по i=1..m-1

← →
Alx2 © (2009-07-25 14:11) [49]

Еще вариант:
Пусть f(m,n) - вероятность того, что в мощность множества (или количество уникальных) цифр в последовательности из n цифр равна m.
Каждая цифра равновероятна и вероятность ее появления равна p.
Тогда справедливо:

f(m,n) = f(m,n-1)*m*p+f(m-1,n-1)*(1-(m-1)*p)

Это получается из такиз соображений:
Пусть мы получаем на каждом шаге по одной цифре.
Тогда f(m,n) - вероятность того, что на шаге n мы имеем m уникальных цифр.
Она (вероятность) складывается из двух взаимоисключающих случаев:
1. Случай, когда m уникальных набрали уже на предыдущем шаге (номер n-1). Тогда нам на текущем шаге не нужна очередная уникальная цифра, а нужна уже встретившаяся. Вероятность этого m*p и соответствующее слагаемое есть f(m,n-1)*m*p
2. Случай, когда имеется на одну уникальную цифру меньше, чем требуется. Тогда вероятность получить новую уникальную цифру есть 1-(m-1)*p. И соответствующее слагаемое есть f(m-1,n-1)*(1-(m-1)*p)

Вот отсюда получается формула f(m,n) = f(m,n-1)*m*p+f(m-1,n-1)*(1-(m-1)*p)

Осталось подставить p = 1/10 (потому-что десятичная система счисления, и каждая цифра встречается с вероятностью 1/10),
m = 10 (потому-что уникальных цифр должно бытб 10)
n = 18 (потому-что длина цепочки = 18)

И искомое число найдем как 10^18*f(10,18) = 134672620008326400
На 10^18 домножил чтобы получить количество вариантов. Так как вероятность f(m,n) можно тут интерпретировать как долю искомых чисел от общего их количества

← →
Sha © (2009-07-25 15:57) [50]

> Alx2 © (25.07.09 14:11) [49]
> 134672620008326400

совпало )

Вот еще один забавный факт: во всех проверенных мной случаях F(m,p) делилось на m!

← →
Readers (2009-09-04 09:20) [51]

Ты как обычно радуешь нас своими лучшими фразами спасибо, беру!

← →
Maxamans (2009-09-17 00:39) [52]

Что, что, а такой подробной статьи не видел давно. Респект и уважуха автору

← →
McSimm © (2009-09-17 01:11) [53]

> Readers (04.09.09 09:20) [51]
>
> Ты как обычно радуешь нас своими лучшими фразами спасибо,
> беру!
>
> Maxamans (17.09.09 00:39) [52]
>
> Что, что, а такой подробной статьи не видел давно. Респект
> и уважуха автору

Это новое слово в спам-технологиях?
Я что-то опять не понимаю .... какой смысл ?

← →
Sha © (2009-09-17 07:52) [54]

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

← →
Sha © (2009-09-17 07:59) [55]

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

← →
Autodot (2009-09-17 14:06) [56]

Нелохо получилось. Есть ещё что-нибудь из этой серии?

← →
Inovet © (2009-09-17 14:12) [57]

> [53] McSimm © (17.09.09 01:11)

А как он ветку выбирает?

← →
McSimm © (2009-09-17 15:00) [58]

> Autodot (17.09.09 14:06) [56]
>
> Нелохо получилось. Есть ещё что-нибудь из этой серии?

Еще один

Фразы явно подобраны для минимального риска быть удаленными.
По форумам их уж поиск выдает много.

> Sha © (17.09.09 07:59) [55]
>
> Еще вариант.
> Эти фразы - метки форумов, где боту удалось пройти автоматическую
> регистрацию и она в настоящий момент действующая.
> Потом остается погуглить и все

Похоже, повышают качество баз.

> Но тут нет лишнего вроде. Или есть?

e-mail только...
Скорее всего и правда метят территорию

> TIF © (17.09.09 17:01) [59]
> e-mail только.

Еще есть, например, сообщения других авторов.
В этом случае имеет смысл поднимать тему, чтоб не пропала.
Ну это так, чисто теоретически.

← →
AntiZOG (2009-09-17 21:17) [61]

> @!!ex © (22.07.09 15:20)
>
> 18 значное число.
> Каждая цифра используеться минимум один раз.

Посчитай для 10-значного в цикле(это при нормальном алгоритме на 20-30 сек), а далее полученное число * 10^8

> [61] AntiZOG (17.09.09 21:17)
> Посчитай для 10-значного в цикле(это при нормальном алгоритме
> на 20-30 сек), а далее полученное число * 10^8

В цикле при нормальном, говоришь.

← →
AntiZOG (2009-09-17 21:37) [63]

> Inovet © (17.09.09 21:22) [62]
>
> > [61] AntiZOG (17.09.09 21:17)
> > Посчитай для 10-значного в цикле(это при нормальном алгоритме
> > на 20-30 сек), а далее полученное число * 10^8
>
> В цикле при нормальном, говоришь.

Хотя в общем так не получится.

это было бы 1*10^8.

Ну 10 млрд итераций вполне реально(10^10). допустим на итерацию уходит 100 тактов. При производительности процессоров в 10-15 Гфлопс это займёт (100*10)/15 = 66 Секунд. Код компилировать 64-битный.

>> @!!ex © (22.07.09 15:20)
>> 18 значное число.
>> Каждая цифра используеться минимум один раз.

> AntiZOG (17.09.09 21:17) [61]
> Посчитай для 10-значного в цикле, а далее полученное число * 10^8

Это неверно.
Минимум один раз относится к любой позиции.
В твоем случае минимум один раз означает гарантированное однократное присутствие каждой цифры в первых 10 позициях,
в то время как требуется гарантированное однократное присутствие каждой цифры во всем числе.

← →
AntiZOG (2009-09-17 23:24) [65]

> AntiZOG (17.09.09 23:24) [65]
> Можно сказать только что чисел больше чем 10^8

Можно и точнее сказать (см. [41] и [49])

Сколько вариантов чисел? Найти похожие ветки