Только что 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) - конечная вероятность, которую нужно найтиЭто просто пипец… Мне вот интересно, что такое “сложненькая” задача, если эта - “простенькая”.
Последние комментарии