IPB

> Лекция №5.4: Символы и строки. Множества
Чат
Форум
Загрузка...
 

страницы: 1 2 3 4 5

Содержание

Операции с множествами

Все теоретико–множественные операции реализованы и в языке Pascal:

1) Пересечение двух множеств s1 и s2:s := s1 * s2;
2) Объединение двух множеств s1 и s2:s := s1 + s2;
3) Разность двух множеств s1 и s2 (все элементы, которые принадлежат множеству s1 и одновременно не принадлежат множеству s2)1:s := s1 - s2;
4) Проверка принадлежности элемента el множеству s (результат этой операции имеет тип Boolean):el in s
5) Обозначение для пустого множества:[]
6) Создание множества из списка элементов:

s := [e1, _, eN];

7) Проверка двух множеств на равенство или строгое включение (результат этих операций имеет тип Boolean):
s1 = s2
s1 > s2
s1 < s2

Не существует никакой процедуры, позволяющей распечатать содержимое множества. Это приходится делать следующим образом:

{ s : set of type1; k : type1 }
for k := min_type1 to max_type1 do
 if k in s then
   Write(k, ' ');

Представление множеств массивами

Одно из основных неудобств при работе с множествами — это ограничение размера всего лишь 256–ю элементами. Мы приведём здесь два очень похожих способа представления больших множеств массивами. Единственным условием является наличие некоторого внутреннего порядка среди представляемых элементов: без этого невозможно будет их перенумеровать.

Представление множеств линейными массивами

Задав линейный массив достаточной длины, можно «вручную» сымитировать множество для более широкого, чем 256 элементов, диапазона значений. Например, чтобы работать с множеством, содержащим 10 000 элементов, достаточно такого массива:

set_arr : array[1 .. 10000] of Boolean;

При таком способе представления возможно задать множество до 65 000 элементов.

Для простоты изложения мы ограничимся только числовыми множествами, однако всё сказанное ниже можно применять и к множествам, элементы которых имеют другую природу. Итак, признаком того, что элемент k является элементом нашего множества, будет значение True в k–й ячейке этого массива.

Посмотрим теперь, какими способами мы вынуждены будем имитировать операции над «массивными» множествами.

  1. Проверка множества на пустоту может быть осуществлена довольно просто:

    pusto := True;
    for i := 1 to N do
     if set_arr[i] then
     begin
        pusto := False;
       Break
     end;
  2. Проверка элемента на принадлежность множеству также не вызовет никаких затруднений, поскольку соответствующая компонента массива содержит ответ на этот вопрос:

    is_in := set_arr[element];
  3. Добавление элемента в множество нужно записывать так:

    set_arr[element] := True;
  4. Удаление элемента из множества записывается аналогичным образом:

    set_arr[element] := False;
  5. Построение пересечения множеств реализуется как проверка вхождения каждого элемента в оба множества и последующее добавление удовлетворивших этому условию элементов в результирующее множество.
  6. Построение объединения множеств аналогичным образом базируется на проверке вхождения элемента хотя бы в одно из объединяемых множеств и дальнейшем добавлении элементов в результирующее множество.
  7. Построение разности двух множеств также опирается на проверку вхождения элемента в оба множества, причём добавление элемента в создаваемое множество происходит только в том случае, если элемент присутствует в множестве–уменьшаемом и одновременно отсутствует в множестве–вычитаемом.
  8. Проверка двух множеств на равенство не требует особых пояснений:

    equal := True;
    for i :=1 to N do
     if set1[i] <> set2[i] then
     begin
        equal := False;
       Break
     end;
  9. Проверка двух множеств на включение (set1 < set2) тоже не потребует больших усилий:

    subset := True;
    for i := 1 to N do
     if set1[i] and not set2[i] then
     begin
        subset := False;
       Break
     end;

страницы: 1 2 3 4 5

Примечания

  1. ^ Если множества s1 и s2 не пересекаются, то результат s будет совпадать с s1.
 
 К началу страницы 
 

Код для вставки: :: :: :: ГОСТ ::
Поделиться: //
 



-
Хостинг предоставлен компанией "Веб Сервис Центр" при поддержке компании "ДокЛаб"