Только что 2 часа убил на “простенькую задачку по комбинаторике”, как сказала наша преподаватель по моделированию. Если кто хочет поломать немного мозги, то вот сама задачка (исходного задания у меня нет, так что это моя интерпретация задания):
Бросаем симметричную монетку n раз. Она может упать либо орлом, либо решкой вверх. Найти вероятность выпадения двух решек (ну, или орлов, не суть важно) подряд.
Если перефразировать в более удобный вид, получаем:
Есть массив, состоящий из нулей и единиц, размером в n элементов. Какова вероятность того, что в массиве есть два нуля, стоящие рядом.
Задача просто бешенная, как бы проста она не казалась. У меня ответ получился только через рекурсию, а в конце в нём всплыл еще и дополнительный ряд Фибоначчи:
q(n) = p(n) / (2 ^ n)
p(n) = 2 * p(n - 1) + f(n - 1)
p(1) = 0
f(1) = 1, f(2) = 1, f(3) = 2, ...
f(n) - ряд Фибоначчи
q(n) - конечная вероятность, которую нужно найтиЭто просто пипец… Мне вот интересно, что такое “сложненькая” задача, если эта - “простенькая”.
April 16th, 2008 at 03:07
Чего-то я наверное недопонял… При чем тут программирование?
Если требуется найти вероятность, то она находится точно по формуле из теории вероятности. Из формулы условной вероятности следует формула “умножения вероятностей” (т.к. события у нас независимые). Вероятность получить решку равна 1/2, вероятность получить решку после того, как первый раз выпала решка, тоже 1/2 (события независимы). Вероятность последовательно получить две решки (либо обеих событий одновременно, если у нас 2 монетки) равняется 1/2 * 1/2 = 1/4 = 0,25. Все….
April 16th, 2008 at 03:16
Программирование здесь действительно абсолютно ни причем. :) А вот насчет подсчета вероятностей – ты аж нифига не прав. :)
Есть массив из 5 элементов – нули и единицы. Найди мне вероятность того, что в этом массиве встретится два нуля рядом. Если ты думаешь, что это 1/4 – то ты глубоко ошибаешься и можешь сам себя проверить – выписав все возможные значения (а их всего 2^5 == 32) и посмотрев, в скольки из них встретится эти два нуля рядом.
April 16th, 2008 at 10:12
Спасибо за задачку, порешаю на досуге.
Хотел написать, что 100% ответ 1/4, а сейчас понял что там все чуть сложнее тервера.
April 16th, 2008 at 10:41
Я конечно не особо в теме, но насколько понимаю 1/2 * 1/2 = 1/4 будет верно только при 2 бросках. Надо подумать. ))
April 16th, 2008 at 12:53
Определись, задачка по моделированию или всё-таки по комбинаторике. В зависимости от этого подход будет различаться: в комбинаторике монета по-умолчанию принимается за честную с вероятностью 1/2, в моделировании — не обязательно.
April 16th, 2008 at 12:56
При двух бросках да, 1/4.. А при n-бросках действительно посложней. Не люблю Байеса
April 16th, 2008 at 13:55
При n-бросках задача ни чуть не сложнее – 1/2 * 1/2 * 1/2 и так n раз или 2 в степени -n ( или 1/2^n) – если мне не изменяет память
April 16th, 2008 at 14:07
Изменяет. Задача стоит не так…
April 16th, 2008 at 14:18
и вправду изменяет…. будет формула что-то типа 1 – ( (2n – 1)/2^n ) – точнее лень искать :))
April 17th, 2008 at 13:44
хмм.. забавно..
(ушел кидать монетку))
April 18th, 2008 at 13:37
Steward ближе всех к цели пока
при трех бросках может быть 1+2 и 2+3 вероятность каждой 1/4 значит общая вероятность 1/2
при четырех бросках может быть 1+2, 2+3, 3+4, опять же вероятность каждой 1/4 значит общая 3/4. тут еще один вопрос втает потому что если будет 1+2 и 3+4 то это еще 1/16 итого 9/16+1/16 = 10/16 = 5/8
и уже при 5 бросках вероятность будет 4/4 (+ 1/8) что больше 1 значить при 5 бросках как минимум одно выпадание будет!
April 18th, 2008 at 14:02
Неправда ваша…. при 5 бросках вероятность выпадения 19/32
Как она может вообще быть больше 1-цы…. это при количестве испытаний стремящемся к бесконечности – вероятность в данном случае будет страмится к единицы.. но уж никак не при 5 бросках.. :)))
Вероятность при N броскаъх следующие
N=1 = P=0
N=2 = P=1/4
N=3 = P=3/8
N=4 = P=4/8
N=5 = P=19/32
под мою предыдущую формулу не попадает конечно… но она близка к правильному результату
April 18th, 2008 at 14:06
да..
N=4 = P=8/16 (специально не сокращаю)
при N=6 = P=25/64
может кого-то натолкнёт на мысль :)
April 18th, 2008 at 14:24
блин… при N=6 = P=43/64 – чё-то я поспешил
April 18th, 2008 at 15:46
точто я забыл учесть вреоятность того что
из 4бросков может быть еще такая комбинация 1+1+1+0 я считал только для 1+1+0+0 0+0+1+1 и 0+1+1+0
April 19th, 2008 at 11:38
Паша, а это у тебя получилось доказательно или так, из эмпирических данных, полученных при рассмотрении всех вариантов разных N?
April 19th, 2008 at 14:06
f(n) = [(2^n)/4 + f(n-1) + f(n-2)]/2^n
April 19th, 2008 at 17:47
dodikk
Из эмпирических данных, полученных путём несколькочасовых исследований взаимосвязей между возможными вариантами бросков для размерностей N-1 и N.
unnamed
Наверное, ты хотел написать так:
p(n) = (2 ^ n) / 4 + p * (n – 1) + p * (n – 2)
f(n) = p(n) / (2 ^ n)
За формулу спасибо, проверю.
All
Преподша сказала, что “условие было сформулировано неверно”. :)
April 20th, 2008 at 00:43
> Преподша сказала, что “условие было сформулировано неверно”.
Я про это и говорил :)
April 21st, 2008 at 17:31
А теперь запиши f(k) = round(((sqrt(5)+1)^n-(sqrt(5)-1)^n)/2^n), и подставь, чтобы получить точную формулу.
April 30th, 2008 at 00:01
>>Преподша сказала, что “условие было сформулировано неверно”.
вот так интересные задачи и получаются
April 30th, 2008 at 14:54
Ага :)
August 21st, 2008 at 18:27
> Если кто хочет поломать немного мозги
Бррр, чего ломать-то? Вполне стандартная задачка на составление рекуррентных соотношений.
Ага, а вот если бы был процесс, завершающийся выпадением двух решек, то можно было бы напрямую записать аналитически.