- •Раздел 1. Множества.
- •1.1. Множества и подмножества.
- •1.2. Способы задания множеств.
- •1.3. Операции над множествами.
- •1.4. Свойства операций над множествами
- •1.5. Разбиение и покрытия
- •1.6. Булеан
- •1.7. Генерация всех подмножеств заданного универсума
- •1.9. Алгоритмы пересечения, объединения двух множеств и проверки включения слиянием
- •1.8. Алгоритм построения бинарного кода Грея
1.8. Алгоритм построения бинарного кода Грея
Данный алгоритм генерирует последовательность всех подмножеств n-элементного множества, причем каждое следующее подмножество получается из предыдущего удалением или добавлением одного элемента.
Для самостоятельного изучения. (описан в учебнике).
1.9. Алгоритмы пересечения, объединения двух множеств и проверки включения слиянием
В общем случае множество состоит из элементов. При этом трудоемкость выполнения основных операций будет:
- О(n) – ограничено сверху числом элементов в множестве. Т.е. для проверки принадлежности элемента множеству в худшем случае необходимо сравнить данный элемент с каждым элементом множества 1 раз;
,, - О(m*n) – ограничено сверху произведением мощностей множеств. Т.е. для выполнения данных операций, сначала необходимо каждый элемент первого множества сравнить с каждым элементом второго.
Если же элементы множества будут упорядочены, то трудоемкость выполнения основных операций можно свести к О(n), где n – наибольшая мощность множеств, участвующих в операции. Операции над множествами, чьи элементы упорядочены, в общем случае называется алгоритмом типа слияния.
Алгоритм типа слияния параллельно просматривает два множества, представленных упорядоченными списками, причем на каждом шаге продвижение происходит в том множестве, в котором текущий элемент меньше.
Рассмотрим алгоритм вычисления пересечения слиянием двух множеств A и B. В данном примере подразумевается, что множества представлены в виде массивов, чьи элементы упорядочены.
ia<-0;
ib<-0;
С<-; //C – пустое множество
while (ia<|A| and ib<|B|) do
if (A[ia] < B[ib]) then //A[ia] не принадлежит пресечению,
ia <- ia + 1; //переходим на следующий
else if (A[ia] > B[ib]) then //B[ib] не принадлежит пресечению,
ib <- ib + 1; //переходим на следующий
else //элементы A[ia] и B[ib] совпадают
Добавить элемент A[ia] в множество С;
ia <- ia + 1;
ib <- ib + 1;
endif
end while
Самостоятельно изучить алгоритмы проверки включения слиянием и вычисления объединения слиянием (смысл в том же).