Задача
Вася хорошо выпил и теперь, когда он добрался до своей улицы, он полностью потерял чувство направления. Поскольку он не помнит, с какой стороны его дом, он выбирает направление наобум. Более того, на каждом перекрёстке он с вероятностью $50\%$ продолжает идти вперёд, а иначе разворачивается и идёт назад. Он настолько потерял связь с реальностью, что может даже пройти мимо своего дома и не заметить этого!
Пройдя $n$ кварталов, Вася засыпает прямо на улице. Проснувшись, он задаётся вопросом: какой у него был шанс заснуть рядом с домом? Ведь от перекрёстка, от которого он начал свой путь, до перекрёстка рядом с домом Васи всего $m$ кварталов. Помогите ему.
Входные данные
В одной строке содержатся два целых числа $n$ и $m$ [latex](0 \le n , m \le 1000)[/latex].
Выходные данные
Выведите одно число — вероятность Васи заснуть на перекрёстке рядом со своим домом. Выведите ответ с абсолютной погрешностью не более $10^{-7}$.
Тесты
| Входные данные | Выходные данные |
| 1 1 | 0.500000000 |
| 10 20 | 0.000000000 |
| 1000 100 | 0.000169397 |
| 16 2 | 0.174560547 |
| 90 44 | 0.000001273 |
Код программы
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 |
#include <iostream> #include <iomanip> using namespace std; int main() { int n, m; cin >> n >> m; double** x = new double* [n+1]; for (int i = 0; i < n+1; i++) { x[i] = new double [2*n+1]; } x[0][n] = 1; double a, b; for(int i = 1; i <= n; i++) { for(int j = n - i; j <= n + i; j++) { a = (j - 1 < 0)? 0 : x[i-1][j-1]; b = (j + 1 > 2*n)? 0 : x[i-1][j+1]; x[i][j] = (a + b) / 2; } } double h = (n + m > 2*n)? 0 : x[n][n+m]; cout << fixed << setprecision(9) << h; for (int i = 0; i < n+1; i++) { delete []x[n-i]; } delete []x; return 0; } |
Решение
Закодируем путь Васи последовательностью из 0 и 1. Пусть 1 соответствует движению вправо, а 0 влево. Пусть из $n$ шагов, которые совершил Вася, $k$ шагов он сделал вправо. Тогда $n-k$ шагов он сделал влево.Нас интересует вероятность того, что Вася переместился в одну из сторон (например вправо) на $m$ кварталов. Тогда должно выполняться: $m+n-k=k$, откуда $k=\frac{m+n}{2}$.Количество последовательностей длины $n$ с $k$ единицами равно $C_n^k$. Поскольку Вася совершил $n$ перемещений, то у него имеется $2^n$ вариантов выбора различных путей. Следовательно вероятность того что Вася пройдет вправо m кварталов, равна $\frac{C_n^k}{2^n}$, где $k=\frac{m+n}{2}$. Отметим, что искомая вероятность равна 0, если $m+n$ нечетно. В этом случае Вася просто не сможет попасть домой, то есть $m+n=2k$ четно.
Ссылки