(кроме начальной, делающей все очереди пустыми) должна требовать
ограниченного константой числа действий.
Решение. Действуем аналогично ссылочной реализации стеков:
мы помним (для каждой очереди) первого, каждый член очереди пом-
нит следующего за ним (для последнего считается, что за ним сто-
ит фиктивный элемент с номером 0). Кроме того, мы должны для
каждой очереди знать последнего (если он есть) - иначе не
удастся добавлять. Как и для стеков, отдельно есть цепь свобод-
ных ячеек. Заметим, что для пустой очереди информация о послед-
нем элементе теряет смысл - но она и не используется при добав-
лении.
Содержание: array [1..n] of T;
Следующий: array [1..n] of 0..n;
Первый: array [1..n] of 0..n;
Последний: array [1..k] of 0..n;
Свободная : 0..n;
procedure Сделать_пустым;
| var i: integer;
begin
| for i := 1 to n-1 do begin
| | Следующий [i] := i + 1;
| end;
| Свободная := 1;
| for i := 1 to k do begin
| | Первый [i]:=0;
| end;
end;
function Есть_место : boolean;
begin
| Есть_место := Свободная <> 0;
end;
function Пуста (номер_очереди: integer): boolean;
begin
| Пуста := Первый [номер_очереди] = 0;
end;
procedure Взять (var t: T; номер_очереди: integer);
| var перв: integer;
begin
| {not Пуста (номер_очереди)}
| перв := Первый [номер_очереди];
| t := Содержание [перв]
| Первый [номер_очереди] := Следующий [перв];
| Следующий [перв] := Свободная;
| Свободная := Перв;
end;
procedure Добавить (t: T; номер_очереди: integer);
| var нов, посл: 1..n;
begin
| {Есть_свободное_место }
| нов := Свободная; Свободная := Следующий [Свободная];
| {из списка свободного места изъят номер нов}
| if Пуста (номер_очереди) then begin
| | Первый [номер_очереди] := нов;
| | Последний [номер_очереди] := нов;
| | Следующий [нов] := 0;
| | Содержание [нов] := t;
| end else begin
| | посл := Последний [номер_очереди];
| | {Следующий [посл] = 0 }
| | Следующий [посл] := нов;
| | Следующий [нов] := 0;
| | Содержание [нов] := t
| | Последний [номер_очереди] := нов;
| end;
end;
function Очередной (номер_очереди: integer): T;
begin
| Очередной := Содержание [Первый [номер_очереди]];
end;
6.2.9. Та же задача для деков вместо очередей.
Указание. Дек - структура симметричная, поэтому надо хра-
нить ссылки в обе стороны (вперед и назад). При этом удобно к
каждому деку добавить фиктивный элемент, замкнув его в кольцо, и
точно такое же кольцо образовать из свободных позиций.
В следующей задаче дек используется для хранения вершин вы-
пуклого многоугольника.
6.2.10. На плоскости задано n точек, пронумерованных слева
направо (а при равных абсциссах - снизу вверх). Составить прог-
рамму, которая строит многоугольник, являющийся их выпуклой обо-
лочкой, за не более чем C*n действий.
Решение. Будем присоединять точки к выпуклой оболочке одна
за другой. Легко показать, что последняя присоединенная точка
будет одной из вершин выпуклой оболочки. Эту вершину мы будем
называть выделенной. Очередная присоединяемая точка видна из вы-
деленной (почему?). Дополним наш многоугольник, выпустив из вы-
деленной вершины "иглу", ведущую в присоединяемую точку. Полу-
чится вырожденный многоугольник, и остается ликвидировать в нем
"впуклости".
[Рисунок]
Будем хранить вершины многоугольника в деке в порядке обхо-
да его периметра по часовой стрелке. При этом выделенная вершина
является началом и концом (головой и хвостом) дека. Присоедине-
ние "иглы" теперь состоит в добавлении присоединяемой вершины в
голову и в хвост дека. Устранение впуклостей несколько более
сложно. Назовем подхвостом и подподхвостом элементы дека, сто-
ящие за его хвостом. Устранение впуклости у хвоста делается так:
while по дороге из хвоста в подподхвост мы поворачиваем
| у подхвоста влево ("впуклость") do begin
| выкинуть подхвост из дека
end
Таким же способом устраняется впуклость у головы дека.
Замечание. Действия с подхвостом и подподхвостом не входят в
определение дека, однако сводятся к небольшому числу манипуляций
с деком (надо забрать три элемента с хвоста, сделать что надо и
вернуть).
Ещё одно замечание. Есть два вырожденных случая: если мы во-
обще не поворачиваем у похвоста (т.е. три соседние вершины лежат
на одной прямой) и если мы поворачиваем на 180 градусов (так бы-
вает, если наш многоугольник есть двуугольник). В первом случае
подхвост стоит удалить (чтобы в выпуклой оболочке не было лишних
вершин), а во втором случае - обязательно оставить.
6.3. Множества.
Пусть Т - некоторый тип. Существует много способов хранить
(конечные) множества элементов типа Т; выбор между ними опреде-
ляется типом T и набором требуемых операций.
Подмножества множества {1..n}.
6.3.1. Используя память, пропорциональную n, хранить
подмножества множества {1..n}.
Операции Число действий
Сделать пустым C*n
Проверить принадлежность C
Добавить C
Удалить С
Минимальный элемент C*n
Проверка пустоты C*n
Решение. Храним множество как array [1..n] of boolean.
6.3.2. То же, но проверка пустоты должна выполняться за
время C.
Решение. Храним дополнительно количество элементов.
6.3.3. То же при следующих ограничениях на число действий:
Операции Число действий
Сделать пустым C*n
Проверить принадлежность C
Добавить C
Удалить C*n
Минимальный элемент C
Проверка пустоты C
Решение. Дополнительно храним минимальный элемент мно-
жества.
6.3.4 То же при следующих ограничениях на число действий:
Операции Число действий
Сделать пустым С*n
Проверить принадлежность С
Добавить С*n
Удалить С
Минимальный элемент С
Проверка пустоты C
Решение. Храним минимальный, а для каждого - следующий и
предыдущий по величине.
Множества целых чисел.
В следующих задачах величина элементов множества не ограни-
чена, но их количество не превосходит n.
6.3.5. Память C*n.
Операции Число действий
Сделать пустым C
Число элементов C
Проверить принадлежность C*n
Добавить новый
(заведомо отсутствующий) C
Удалить C*n
Минимальный элемент C*n
Взять какой-то элемент C
Решение. Множество представляем с помощью переменных
a:array [1..n] of integer, k: 0..n; множество содержит k элемен-
тов a[1],...,a[k]; все они различны. По существу мы храним эле-
менты множества в стеке (без повторений).
6.3.6. Память C*n.
Операции Число действий
Сделать пустым C
Проверить пустоту C
Проверить принадлежность C*(log n)
Добавить С*n
Удалить C*n
Минимальный элемент С
Решение. См. решение предыдущей задачи с дополнительным ус-
ловием a[1] < ... < a[k]. При проверке принадлежности используем
двоичный поиск.
В следующей задаче полезно комбинировать разные способы.
6.3.7. Используя описанное в предыдущей задаче представле-
ние множеств, найти все вершины ориентированного графа, доступ-
ные из данной по ребрам. (Вершины считаем числами 1..n.) Время
не больше C * (общее число ребер, выходящих из доступных вер-
шин).
Решение. (Другое решение смотри в главе о рекурсии.) Пусть
num[i] - число ребер, выходящих из i, out[i][1], ...,
out[i][num[i]] - вершины, куда ведут ребра.
procedure Доступные (i: integer);
| {напечатать все вершины, доступные из i, включая i}
| var X: подмножество 1..n;
| P: подмножество 1..n;
| q, v, w: 1..n;
| k: integer;
begin
| ...сделать X, P пустыми;
| writeln (i);
| ...добавить i к X, P;
| {(1) P = множество напечатанных вершин; P содержит i;
| (2) напечатаны только доступные из i вершины;
| (3) X - подмножество P;
| (4) все напечатанные вершины, из которых выходит
| ребро в ненапечатанную вершину, принадлежат X}
| while X непусто do begin
| | ...взять какой-нибудь элемент X в v;
| | for k := 1 to num [v] do begin
| | | w := out [v][k];
| | | if w не принадлежит P then begin
| | | | writeln (w);
| | | | добавить w в P;
| | | | добавить w в X
| | | end;
| | end;
| end;
end;
Свойство (1) не нарушается, так как печать происходит од-
новременно с добавлением в P. Свойства (2): раз v было в X, то v
доступно, поэтому w доступно. Свойство (3) очевидно. Свойство
(4): мы удалили из X элемент v, но все вершины, куда из v идут
ребра, перед этим напечатаны.
Оценка времени работы. Заметим, что изъятые из X элементы
больше туда не добавляются, так как они в момент изъятия (и,
следовательно, всегда позже) принадлежат P, а добавляются только
элементы не из P. Поэтому цикл while выполняется не более, чем
по разу, для всех доступных вершин, а цикл for выполняется
столько раз, сколько из вершины выходит ребер.
Для X надо использовать представление со стеком или оче-
редью (см. выше), для P - булевский массив.
6.3.8. Решить предыдущую задачу, если требуется, чтобы дос-
тупные вершины печатались в таком порядке: сначала заданная вер-
шина, потом ее соседи, потом соседи соседей (еще не напечатан-
ные) и т.д.
Указание. Так получится, если использовать очередь в приве-
денном выше решении: докажите индукцией по k, что существует мо-
мент, в который напечатаны все вершины на расстоянии не больше
k, а в очереди находятся все вершины, удаленные ровно на k.
Более сложные способы представления множеств будут разобраны в
главах 11 (Хеширование) и 12 (Деревья).
6.4. Разные задачи.
6.4.1. Реализовать структуру данных, которая имеет все те
же операции, что массив длины n, а именно
начать работу
положить в i-ю ячейку число n
узнать, что лежит в i-ой ячейке
а также операцию "указать номер минимального элемента" (или од-
ного из минимальных элементов). Количество действий для всех
операций должно быть не более C*log n, не считая операции "на-
чать работу" (которая требует не более C*n действий).
Решение. Используется прием, изложенный в разделе о сорти-
ровке деревом. Именно, надстроим над элементами массива как над
листьями двоичное дерево, в каждой вершине которого храним мини-
мум элементов соответствующего поддерева. Корректировка этой ин-
формации, а также прослеживание пути из корня к минимальному
элементу требуют логарифмического числа действий.
6.4.2. Приоритетная очередь - это очередь, в которой важно
не то, кто встал последним (порядок помещения в нее не играет
роли), а кто главнее. Более точно, при помещении в очередь ука-
зывается приоритет помещаемого объекта (будем считать приоритеты
целыми числами), а при взятии из очереди выбирается элемент с
наибольшим приоритетом (или один из таких элементов). Реализо-
вать приоритетную очередь так, чтобы помещение и взятие элемента
требовали логарифмического числа действий (от размера очереди).
