Задачка по моделированию

Originally published at Блог FX'а. Please leave any comments there.

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

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