3. Алексей приехал на каникулах в деревню и пошёл в лес. Он идёт по тропинкам, пока не найдёт гриб мухомор или белый. Схема тропинок изображена на рисунке. На любой развилке он…

Нельзя точно ответить без самой схемы тропинок. Нужно знать структуру дерева: сколько развилок и сколько листьев (концов), какие листья белые, какие мухоморы. Приведём метод расчёта, чтобы вы смогли посчитать по изображению.

Как словить вероятность

• Модель: дерево с корнем в доме. Листья дерева — это места, где есть грибы. Каждый развилок (внутренний узел) имеет k исходящих ответвлений, и Алексей на развилке выбирает одно из них с равной вероятностью 1/k.
• Пусть W(v) — вероятность принести домой белый гриб, если начинать путь с узла v.
  • Для листа l: W(l) = 1, если лист белый; W(l) = 0, если мухомор.
  • Для внутреннего узла v с детьми c1,...,ck: W(v) = (1/k) * (W(c1) + W(c2) + ... + W(ck)).
• Искать нужно W(root) — вероятность принести домой белый гриб.

Пошаговый алгоритм

1. Обозначьте каждый узел и его детей. Определите, какой из листьев белый, какой мухомор.
2. Вычисляйте W снизу вверх (динамическим программированием): сначала для листьев, затем для их родителей и так далее до корня.
3. Ответ — W(root).

Примеры

• Пример 1: корень имеет 2 ветки: левая заканчивается белым грибом, правая — мухомор. W(левая) = 1, W(правая) = 0, значит W(root) = (1/2)(1) + (1/2)(0) = 1/2.
• Пример 2: корень имеет 3 ветки: две белых и одна мухомор. W = (1/3)(1 + 1 + 0) = 2/3.
• Пример 3: более сложное дерево, можно посчитать аналогично суммированием по уровням.

Пожалуйста, пришлите изображение схемы тропинок или опишите её текстом (сколько развилок, какие листья белые, какие мухоморы, сколько ветвей у каждого развилки). Я быстро посчитаю точную вероятность W(root).