| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | tourist | 3993 |
| 2 | jiangly | 3743 |
| 3 | orzdevinwang | 3707 |
| 4 | Radewoosh | 3627 |
| 5 | jqdai0815 | 3620 |
| 6 | Benq | 3564 |
| 7 | Kevin114514 | 3443 |
| 8 | ksun48 | 3434 |
| 9 | Rewinding | 3397 |
| 10 | Um_nik | 3396 |
| Страны | Города | Организации | Всё → |
| № | Пользователь | Вклад |
|---|---|---|
| 1 | cry | 167 |
| 2 | Um_nik | 163 |
| 3 | maomao90 | 162 |
| 3 | atcoder_official | 162 |
| 5 | adamant | 159 |
| 6 | -is-this-fft- | 158 |
| 7 | awoo | 155 |
| 8 | TheScrasse | 154 |
| 9 | Dominater069 | 153 |
| 10 | nor | 152 |
Всем привет!
Недавно задумался как решить такую задачу: Есть корень дерева, за каждый ход игрок может у любого листа дерева создать либо левого потомка (с вероятностью p), либо правого (с вероятностью 1 - p). Какого математическое ожидание высоты дерева после n ходов игрока?
UPD: Лист выбирается равновероятно.
Лист -- эта вершина с количеством потомков меньше 2.
Лист выбирается равновероятно?
Да
Можешь сформулировать условие по-точнее. Что есть лист в данной задаче? Вершина, у которой строго меньше 2-ух потомков? я правильно понял? Интересно было бы узнать откуда задача.
Кстати (предположение) при равновероятном выборе (не полной, без 2-ух потомков) вешины и добавлении потомка — ответ на задачу не должен зависеть от того левого или правого мы добавляем.
Вообще-то вроде вы правы. Задача просто придуманная во время неинтересной пары. Насчет выбора листа -- да, равновероятно.
В таком случае, как я понимаю интерес представляет следующая задача: Сначала мы (в зависимости от вероятности p) выбираем "левую" или "правую" вершину мы будем добавлять, а затем среди всех возможных вершин, к которым можно прицепить "левого" или "правого" потомка (в зависимости от сделанного ранее выбора) выбираем равновероятно.
В такой формулировке по крайней мере есть явная зависомость от p.
p = 0 или 1 : ans = n;
p = 0.5 :
;