Множества целых чисел

В следующих задачах величина элементов множества не ограничена, но их количество не превосходит n .

$\scriptstyle{\blacktriangleright}$ 6.3.5. Память Cn :

$\begin{displaymath} \begin{tabular} {ll} Операции & Число действий \\ [1ex] Сд... ...ный элемент & $Cn$\\ Взять какой-то элемент & $C$\end{tabular}\end{displaymath}$

Решение. Множество представляем с помощью переменных

         a:array [1..n] of integer, k: 0..n;

множество содержит k элементов ${\hbox{\tt a[1]}},\ldots{\hbox{\tt a[k]}}$ ; все они различны. По существу мы храним элементы множества в стеке (без повторений). С тем же успехом можно было бы воспользоваться очередью вместо стека. $\scriptstyle\blacktriangleleft$

$\scriptstyle{\blacktriangleright}$ 6.3.6. Память Cn :

$\begin{displaymath} \begin{tabular} {ll} Операции & Число действий \\ [1ex] Сд... ...Cn$\\ Удалить & $Cn$\\ Минимальный элемент & $C$\end{tabular}\end{displaymath}$

Решение. См. решение предыдущей задачи с дополнительным условием ${\hbox{\tt a[1]}}<\ldots<{\hbox{\tt a[k]}}$ . При проверке принадлежности используем двоичный поиск. $\scriptstyle\blacktriangleleft$

В следующей задаче полезно комбинировать разные способы.

$\scriptstyle{\blacktriangleright}$ 6.3.7. Используя описанные способы представления множеств, найти все вершины ориентированного графа, доступные из данной по ребрам. (Вершины считаем числами ${\hbox{\tt 1}}\ldots{\hbox{\tt n}}$ .) Время не больше $C\cdot{}$ (общее число ребер, выходящих из доступных вершин).

Решение. (Другое решение смотри в главе о рекурсии.) Пусть num[i] -- число ребер, выходящих из i, а out[i][1],..., out[i][num[i]] -- вершины, куда ведут ребра из вершины 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 -- булевский массив. $\scriptstyle\blacktriangleleft$

$\scriptstyle{\blacktriangleright}$ 6.3.8. Решить предыдущую задачу, если требуется, чтобы доступные вершины печатались в таком порядке: сначала заданная вершина, потом ее соседи, потом соседи соседей (еще не напечатанные) и т.д.

[Указание. Так получится, если использовать очередь для хранения X в приведенном выше решении: докажите индукцией по k , что существует момент, в который напечатаны все вершины на расстоянии не больше k , а в очереди находятся все вершины, удаленные ровно на k .] $\blacktriangleleft$

Более сложные способы представления множеств будут разобраны в главах 11 (хеширование) и 12 (деревья).

pvv
1/8/1999