В следующих задачах величина элементов множества не ограничена, но их количество не превосходит n .
6.3.5. Память Cn :
a:array [1..n] of integer, k: 0..n;множество содержит k элементов ; все они различны. По существу мы храним элементы множества в стеке (без повторений). С тем же успехом можно было бы воспользоваться очередью вместо стека.
6.3.6. Память Cn :
В следующей задаче полезно комбинировать разные способы.
6.3.7. Используя описанные способы представления
множеств, найти все вершины ориентированного графа, доступные из
данной по ребрам. (Вершины считаем числами .)
Время не больше (общее число ребер, выходящих из
доступных вершин).
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. Решить предыдущую задачу, если требуется, чтобы доступные
вершины печатались в таком порядке: сначала заданная вершина,
потом ее соседи, потом соседи соседей (еще не напечатанные) и
т.д.
Более сложные способы представления множеств будут разобраны в главах 11 (хеширование) и 12 (деревья).