Задачка по терверу

Vlad128

Привет.
  Кто хочет подумать. Понравилась задачка, потому что это хороший пример «к алгоритмам».
  Сразу дам общую постановку, чтобы форумчане не халтурили и чтобы не нарушать копирайт :)
  Есть симметричные «кубики» с числом граней p1, p2, ..., pn. p может быть от двух и выше, потому и «кубики», а не кубики.
  Вопрос: можно ли бросанием этих кубиков смоделировать бросание одного симметричного кубика с числом граней P?
  Требование — строгая конечность времени работы алгоритма. Т.е. нельзя чтобы он почти наверное работал за конечное время или там было мат. ожидание времени работы, но не было точного ограничения.
  Как-то так :)

Vlad128

Если баян, киньте ссылку, пожалуйста :)

Vlad128

Под временем подразумевается число бросаний кубиков.

sverum

Есть связь между p1 .. pn и P?

Vlad128

Если решение не всегда существует, то надо найти условия. Если n=1, p1=2, P=2, то решение есть, например.

sverum

Ну вроде если и только если некоторая степень числа p1p2...pn делится на P.
Без ограничения общности можно считать, что все кубики кинули K раз. Пространство элементарных исходов состоит из (p1p2...pn)^K элементарных исходов. Все они равновероятны. Поэтому оно должно делиться на P частей с одинаковым числом исходов.

Vlad128

Ну да :)
Хороший пример на то, что от алгоритма, который работает почти наверное, до строго детерминированного может быть очень далеко по вполне безобидным на первый взгляд причинам.

Vlad128

Правда у тебя чуточку не хватает формализма как раз в том месте, где «поэтому должно делиться».

sverum

Правда у тебя чуточку не хватает формализма как раз в том месте, где «поэтому должно делиться».
Да вроде все понятно. Должно являться объединением P непересекающихся равновероятных событий, соответствующих выпадению граней моделируемого кубика.

Vlad128

Ну там как бы даже для случая n=1 как раз и зарыто все решение, вообще-то :)

Vlad128

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

griz_a

Какое-то левое обоснование. Я вообще могу кинуть шестигранник и если на нем выпадет i, то кинуть i+3 гранник. Потом как-нибудь исходы пообъединять и получить равновероятные.

Vlad128

Да, вот в моем решении было слово «статистика»

sverum

Какое-то левое обоснование. Я вообще могу кинуть шестигранник и если на нем выпадет i, то кинуть i+3 гранник. Потом как-нибудь исходы пообъединять и получить равновероятные.
Какое-то левое возражение. Построил бы пример, тогда бы и выступал.

sverum

Я вообще могу кинуть шестигранник и если на нем выпадет i, то кинуть i+3 гранник. Потом как-нибудь исходы пообъединять и получить равновероятные.
Но если уж на то пошло, то, как мне кажется, можно считать, что на втором шаге ты подбрасываешь все эти свои "i+3 гранники" одновременно.

griz_a

Нельзя, конечно, получится куча исходов, которых у нас не бывает.
А примера я не знаю и не уверен, что его можно построить. Но сама конструкция под условия подходит вполне.

sverum

Нельзя, конечно, получится куча исходов, которых у нас не бывает.
Ну и что? Эта куча исходов получается "делением" исходов твоего вероятностного пространства. Мера продолжается. Если ты можешь свое вероятностное пространство разбить на P равновероятных событий, то и с "расширенным" можно сделать то же самое. Хотя может и путаю чего.

griz_a

Эта куча исходов получается "делением" исходов твоего вероятностного пространства и продолжением меры. Если ты можешь свое вероятностное пространство разбить на P равновероятных событий, то и с "расширенным" можно сделать то же самое. Хотя может и путаю чего.

Я ж могу бросить 12гранник, выбрать 10 исходов и объединить их по 2.
Конечно, под условие это не подходит, но в чем это не подходит под твои рассуждения - непонятно.
Другое дело, что когда мы объединяем какие-то исходы, то знаменатель полученного объединения будет делителем произведения знаменателей для каждого, ннкуда не денешься. Вроде разумно.

sverum

Я ж могу бросить 12гранник, выбрать 10 исходов и объединить их по 2.
Конечно, под условие это не подходит, но в чем это не подходит под твои рассуждения - непонятно.
Другое дело, что когда мы объединяем какие-то исходы, то знаменатель полученного объединения будет делителем произведения знаменателей для каждого, ннкуда не денешься. Вроде разумно.
Какой-то бессвязный поток сознания, если честно.

Vlad128

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

Lokomotiv59

Какое-то левое обоснование. Я вообще могу кинуть шестигранник и если на нем выпадет i, то кинуть i+3 гранник. Потом как-нибудь исходы пообъединять и получить равновероятные.
Нельзя получить равновероятные. Алгоритм бросаний можно представить в виде дерева. Так вот, для любого конечного детерминированного алгоритма, можно привести эквивалентный алгоритм, в котором каждый кубик будет брошен ровно K раз независимо от исходов бросаний (просто добавить лишние бросания, куда это нужно). Так вот, количество вариантов работы нового алгоритма равно (p_1*p_2*...*p_n)^K, причем они равновероятны. А значит, это число должно делиться на P.

griz_a

Да, я адский тупарь :crazy:
Надо-то просто доразбить каждый исход на (p_1....p_n)^M, где M - ограничивающая константа и считать, что наши опыты - объединение тех
to nku Да что ответ верный я и не сомневался..

sverum

Надо-то просто доразбить каждый исход на (p_1....p_n)^M, где M - ограничивающая константа и считать, что наши опыты - объединение тех
Какое удивительное открытие. Чукча совсем не читатель?
Оставить комментарий
Имя или ник:
Комментарий: