Редактирование: РОС, ответы на задачи
Материал из eSyr's wiki.
Внимание: Вы не представились системе. Ваш IP-адрес будет записан в историю изменений этой страницы.
ПРЕДУПРЕЖДЕНИЕ: Длина этой страницы составляет 95 килобайт. Страницы, размер которых приближается к 32 КБ или превышает это значение, могут неверно отображаться в некоторых браузерах. Пожалуйста, рассмотрите вариант разбиения страницы на меньшие части.
Правка может быть отменена. Пожалуйста, просмотрите сравнение версий, чтобы убедиться, что это именно те изменения, которые вас интересуют, и нажмите «Записать страницу», чтобы изменения вступили в силу.
Текущая версия | Ваш текст | ||
Строка 388: | Строка 388: | ||
Составляем сбалансированное дерево, например, такое. Где бы ни находился маркер, нужно 15 посылок запросов для инициализации (по каждому ребру либо в обну, либо в другую сторону). Далее, надо, начиная с вершины, где есть маркер, обойти в глубину дерево. Кажется, что оптимально это можно сделать за 26 операций. В самом деле, начнём обход из корня (0), и будем обходить сначала правые поддеревья, потом левые. Тогда по каждому ребру придётся пройти 2 раза (вперёд и назад), кроме последних четырёх(рёбра 0-1, 1-2, 2-3, 3-4), так как из вершины 4 маркер возвращаться не будет (очередь пуста). Итого: (15+26)(Ts+1*Tb). | Составляем сбалансированное дерево, например, такое. Где бы ни находился маркер, нужно 15 посылок запросов для инициализации (по каждому ребру либо в обну, либо в другую сторону). Далее, надо, начиная с вершины, где есть маркер, обойти в глубину дерево. Кажется, что оптимально это можно сделать за 26 операций. В самом деле, начнём обход из корня (0), и будем обходить сначала правые поддеревья, потом левые. Тогда по каждому ребру придётся пройти 2 раза (вперёд и назад), кроме последних четырёх(рёбра 0-1, 1-2, 2-3, 3-4), так как из вершины 4 маркер возвращаться не будет (очередь пуста). Итого: (15+26)(Ts+1*Tb). | ||
- | Замечание: в приведенном выше решении, на мой взгляд, имеется ошибка - не учтены повторные посылки запроса после того, как маркер покидает вершину, в направлении ушедшего маркера (они выполняются, если очередь запросов в узле не пуста). Их количество считается вручную (мысленно проводим обход дерева и при каждом переходе в следующую вершину смотрим, остались ли еще запросы на только что покинутой). На приведенном выше рисунке, таким образом, строя обход в глубину | + | Замечание: в приведенном выше решении, на мой взгляд, имеется ошибка - не учтены повторные посылки запроса после того, как маркер покидает вершину, в направлении ушедшего маркера (они выполняются, если очередь запросов в узле не пуста). Их количество считается вручную (мысленно проводим обход дерева и при каждом переходе в следующую вершину смотрим, остались ли еще запросы на только что покинутой). На приведенном выше рисунке, таким образом, строя обход в глубину слева направо, нужно к ответу добавить 12*(Ts+1*Tb). Данное решение принято аспирантом на экзамене, кроме того, им было сделано замечание, что запрос может посылаться вместе с маркером в одном сообщении, тогда удастся избежать лишних накладных расходов на инициацию передачи и к ответу добавится просто 12*Tb. |
Замечание2: А если начать обход не с 0 вершины, а с 15? тогда нам потребуется только 23 операции (т.к не придется дважды проходить 15-13, 13-9, 9-0) | Замечание2: А если начать обход не с 0 вершины, а с 15? тогда нам потребуется только 23 операции (т.к не придется дважды проходить 15-13, 13-9, 9-0) |