Блог пользователя abzaloid

Автор abzaloid, 11 лет назад, По-русски

Всем привет!

Недавно задумался как решить такую задачу: Есть корень дерева, за каждый ход игрок может у любого листа дерева создать либо левого потомка (с вероятностью p), либо правого (с вероятностью 1 - p). Какого математическое ожидание высоты дерева после n ходов игрока?

UPD: Лист выбирается равновероятно.

Лист -- эта вершина с количеством потомков меньше 2.

  • Проголосовать: нравится
  • -5
  • Проголосовать: не нравится

»
11 лет назад, # |
  Проголосовать: нравится +4 Проголосовать: не нравится

Лист выбирается равновероятно?

»
11 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Можешь сформулировать условие по-точнее. Что есть лист в данной задаче? Вершина, у которой строго меньше 2-ух потомков? я правильно понял? Интересно было бы узнать откуда задача.

  • »
    »
    11 лет назад, # ^ |
      Проголосовать: нравится +1 Проголосовать: не нравится

    Кстати (предположение) при равновероятном выборе (не полной, без 2-ух потомков) вешины и добавлении потомка — ответ на задачу не должен зависеть от того левого или правого мы добавляем.

    • »
      »
      »
      11 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      Вообще-то вроде вы правы. Задача просто придуманная во время неинтересной пары. Насчет выбора листа -- да, равновероятно.

      • »
        »
        »
        »
        11 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        В таком случае, как я понимаю интерес представляет следующая задача: Сначала мы (в зависимости от вероятности p) выбираем "левую" или "правую" вершину мы будем добавлять, а затем среди всех возможных вершин, к которым можно прицепить "левого" или "правого" потомка (в зависимости от сделанного ранее выбора) выбираем равновероятно.

        В такой формулировке по крайней мере есть явная зависомость от p.

        p = 0 или 1 : ans = n;

        p = 0.5 : ;