| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | tourist | 3803 |
| 2 | jiangly | 3707 |
| 3 | Benq | 3627 |
| 4 | ecnerwala | 3584 |
| 5 | orzdevinwang | 3573 |
| 6 | Geothermal | 3569 |
| 6 | cnnfls_csy | 3569 |
| 8 | Radewoosh | 3542 |
| 9 | jqdai0815 | 3532 |
| 10 | gyh20 | 3447 |
| Страны | Города | Организации | Всё → |
| № | Пользователь | Вклад |
|---|---|---|
| 1 | maomao90 | 164 |
| 2 | awoo | 163 |
| 3 | adamant | 162 |
| 4 | maroonrk | 152 |
| 5 | -is-this-fft- | 151 |
| 6 | nor | 150 |
| 7 | atcoder_official | 147 |
| 8 | TheScrasse | 146 |
| 9 | Petr | 145 |
| 10 | SecondThread | 142 |
Всем привет!
Недавно задумался как решить такую задачу: Есть корень дерева, за каждый ход игрок может у любого листа дерева создать либо левого потомка (с вероятностью p), либо правого (с вероятностью 1 - p). Какого математическое ожидание высоты дерева после n ходов игрока?
UPD: Лист выбирается равновероятно.
Лист -- эта вершина с количеством потомков меньше 2.
Лист выбирается равновероятно?
Да
Можешь сформулировать условие по-точнее. Что есть лист в данной задаче? Вершина, у которой строго меньше 2-ух потомков? я правильно понял? Интересно было бы узнать откуда задача.
Кстати (предположение) при равновероятном выборе (не полной, без 2-ух потомков) вешины и добавлении потомка — ответ на задачу не должен зависеть от того левого или правого мы добавляем.
Вообще-то вроде вы правы. Задача просто придуманная во время неинтересной пары. Насчет выбора листа -- да, равновероятно.
В таком случае, как я понимаю интерес представляет следующая задача: Сначала мы (в зависимости от вероятности p) выбираем "левую" или "правую" вершину мы будем добавлять, а затем среди всех возможных вершин, к которым можно прицепить "левого" или "правого" потомка (в зависимости от сделанного ранее выбора) выбираем равновероятно.
В такой формулировке по крайней мере есть явная зависомость от p.
p = 0 или 1 : ans = n;
p = 0.5 :
;