Apr 16

Только что 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) - конечная вероятность, которую нужно найти

Это просто пипец… Мне вот интересно, что такое “сложненькая” задача, если эта - “простенькая”.

written by fxposter \\ tags: ,


23 Responses to “Задачка по моделированию”

  1. 1. Ali Says:

    Чего-то я наверное недопонял… При чем тут программирование?
    Если требуется найти вероятность, то она находится точно по формуле из теории вероятности. Из формулы условной вероятности следует формула “умножения вероятностей” (т.к. события у нас независимые). Вероятность получить решку равна 1/2, вероятность получить решку после того, как первый раз выпала решка, тоже 1/2 (события независимы). Вероятность последовательно получить две решки (либо обеих событий одновременно, если у нас 2 монетки) равняется 1/2 * 1/2 = 1/4 = 0,25. Все….

  2. 2. FX Poster Says:

    Программирование здесь действительно абсолютно ни причем. :) А вот насчет подсчета вероятностей – ты аж нифига не прав. :)

    Есть массив из 5 элементов – нули и единицы. Найди мне вероятность того, что в этом массиве встретится два нуля рядом. Если ты думаешь, что это 1/4 – то ты глубоко ошибаешься и можешь сам себя проверить – выписав все возможные значения (а их всего 2^5 == 32) и посмотрев, в скольки из них встретится эти два нуля рядом.

  3. 3. Денис Радченко Says:

    Спасибо за задачку, порешаю на досуге.
    Хотел написать, что 100% ответ 1/4, а сейчас понял что там все чуть сложнее тервера.

  4. 4. mihailt Says:

    Я конечно не особо в теме, но насколько понимаю 1/2 * 1/2 = 1/4 будет верно только при 2 бросках. Надо подумать. ))

  5. 5. Sam Says:

    Определись, задачка по моделированию или всё-таки по комбинаторике. В зависимости от этого подход будет различаться: в комбинаторике монета по-умолчанию принимается за честную с вероятностью 1/2, в моделировании — не обязательно.

  6. 6. tot_ra Says:

    При двух бросках да, 1/4.. А при n-бросках действительно посложней. Не люблю Байеса

  7. 7. Steward Says:

    При n-бросках задача ни чуть не сложнее – 1/2 * 1/2 * 1/2 и так n раз или 2 в степени -n ( или 1/2^n) – если мне не изменяет память

  8. 8. Sam Says:

    Изменяет. Задача стоит не так…

  9. 9. Steward Says:

    и вправду изменяет…. будет формула что-то типа 1 – ( (2n – 1)/2^n ) – точнее лень искать :))

  10. 10. iVan Says:

    хмм.. забавно..
    (ушел кидать монетку))

  11. 11. CTAPbIu_MABP Says:

    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 бросках как минимум одно выпадание будет!

  12. 12. Steward Says:

    Неправда ваша…. при 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

    под мою предыдущую формулу не попадает конечно… но она близка к правильному результату

  13. 13. Steward Says:

    да..
    N=4 = P=8/16 (специально не сокращаю)
    при N=6 = P=25/64

    может кого-то натолкнёт на мысль :)

  14. 14. Steward Says:

    блин… при N=6 = P=43/64 – чё-то я поспешил

  15. 15. CTAPbIu_MABP Says:

    точто я забыл учесть вреоятность того что
    из 4бросков может быть еще такая комбинация 1+1+1+0 я считал только для 1+1+0+0 0+0+1+1 и 0+1+1+0

  16. 16. dodikk Says:

    Паша, а это у тебя получилось доказательно или так, из эмпирических данных, полученных при рассмотрении всех вариантов разных N?

  17. 17. unnamed Says:

    f(n) = [(2^n)/4 + f(n-1) + f(n-2)]/2^n

  18. 18. FX Poster Says:

    dodikk
    Из эмпирических данных, полученных путём несколькочасовых исследований взаимосвязей между возможными вариантами бросков для размерностей N-1 и N.

    unnamed
    Наверное, ты хотел написать так:
    p(n) = (2 ^ n) / 4 + p * (n – 1) + p * (n – 2)
    f(n) = p(n) / (2 ^ n)

    За формулу спасибо, проверю.

    All
    Преподша сказала, что “условие было сформулировано неверно”. :)

  19. 19. Sam Says:

    > Преподша сказала, что “условие было сформулировано неверно”.
    Я про это и говорил :)

  20. 20. buriy Says:

    А теперь запиши f(k) = round(((sqrt(5)+1)^n-(sqrt(5)-1)^n)/2^n), и подставь, чтобы получить точную формулу.

  21. 21. nik Says:

    >>Преподша сказала, что “условие было сформулировано неверно”.
    вот так интересные задачи и получаются

  22. 22. FX Poster Says:

    Ага :)

  23. 23. Ves Says:

    > Если кто хочет поломать немного мозги
    Бррр, чего ломать-то? Вполне стандартная задачка на составление рекуррентных соотношений.

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

Leave a Reply