Всем привет!
Недавно задумался как решить такую задачу: Есть корень дерева, за каждый ход игрок может у любого листа дерева создать либо левого потомка (с вероятностью p), либо правого (с вероятностью 1 - p). Какого математическое ожидание высоты дерева после n ходов игрока?
UPD: Лист выбирается равновероятно.
Лист -- эта вершина с количеством потомков меньше 2.
Лист выбирается равновероятно?
Да
Можешь сформулировать условие по-точнее. Что есть лист в данной задаче? Вершина, у которой строго меньше 2-ух потомков? я правильно понял? Интересно было бы узнать откуда задача.
Кстати (предположение) при равновероятном выборе (не полной, без 2-ух потомков) вешины и добавлении потомка — ответ на задачу не должен зависеть от того левого или правого мы добавляем.
Вообще-то вроде вы правы. Задача просто придуманная во время неинтересной пары. Насчет выбора листа -- да, равновероятно.
В таком случае, как я понимаю интерес представляет следующая задача: Сначала мы (в зависимости от вероятности p) выбираем "левую" или "правую" вершину мы будем добавлять, а затем среди всех возможных вершин, к которым можно прицепить "левого" или "правого" потомка (в зависимости от сделанного ранее выбора) выбираем равновероятно.
В такой формулировке по крайней мере есть явная зависомость от p.
p = 0 или 1 : ans = n;
p = 0.5 : ;