Множества

В своё время, расказывая о типах я совсем упустил из виду множества. Теперь настало время наверстать упущенное. Множества - это наборы логически связанных объектов одного типа. Логическая связь между элементами контролируется только программистом. Количество элементов множества может меняться от 0 до 256. Множество, не содержащее элементов называется пустым. Вообщем эта терминология пришла из математики. Но на всякий случай я продолжу:
Два множества считаются эквивалентными ттогда и только тогда, когда все их элементы равны, при этом порядок их следования не имеет значения.
Если все элементы одного множества входят в другой, то говорят, что первое множество включается во второе. (соответственно пустое множество включается в любое). Описание множества имеет вид:

set of БАЗОВЫЙ_ТИП

Например:

Days : set of 1..31;
Digit : set of '0'..'9';
Leters : set of Char;

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

Days := [8, 9, 13, 20 .. 25];
Digit := ['1', '3', '2', '9', '0'];
Leters := [ ]; - пустое множество

Рассмотрим ещё один пример, что бы понять что такое эквивалентность и включение:

type
   num = set of 0 ..9;
   digit = set of '0' .. '9';
var
   s1, s2, s3 : digit;
   s4, s5, s6 : num;
begin
   s1 := ['1', '2', '3'];
   s2 := ['2', '1', '3'];
   s3 := ['1', '3'];
   s4 := [0..3];
   s5 := [4 .. 6];
   s6 := [3, 5 .. 9];

Множества s1 и s2 эквивалентны. Множество s3 включается в s2 и в s1 соответственно. Над множествами определны следующие операции:

*

пересечение множеств - результат содержит общие для обеих множеств элементы. s4 * s6 cодержит [3], а s4 *s5 пустое множество

+

объединение множест - результат содержит элементы первого множества, дополненные недостоющими элементами второго множества. s4 + s5 содержит [0,1,2,3,4,5, 6]

-

разность множеств - результат содержит элементы из первого множества, которые не принадлежат второму. например s6 - s5 содержит [3,7,8,9]

=

эквивалентность - результат true, если множества эквивалентны и false в другом случае

<>

не эквивалентность - true если множества не эквивалентны

>=, <=

вхождение (проверка на подмножество)
• <= - true если первое множество включено во второе
• >= - true, если второе множество включено в первое

in

проверка на принадлежность. Синтаксис: ЗНАЧЕНИЕ in МНОЖЕСТВО
возвращает true, если ЗНАЧЕНИЕ принадлежит множеству, например 3 in s6 - true; 2*2 in s1 - flase

Так же для множеств определены 2 процедуры:

• procedure Include(var S: set of T;I:T);
  Включает новый элемент I в множество S
• procedure Exclude(var S: set of T;I:T);
  Исключает элемент I из множества S

Несмотря на возможность использовать для этих операций +/- использование процедур более предпочтительней, т.к. они отличаются более высокой скоростью выполнения. Ну вот и всё, а вы боялись!
© дантист, после вырывания зуба Теперь пришло время рассмотреть несколько примерчиков.

program test;

var
 S : set of char;
 c : char;

begin

 s := [];

 repeat
   read (c);
   include (s, c);
 until c = '.';

 for c := '0' to '9' do
   if c in s then
      writeLn (c)
end.

Итак что же делает эта программа? Для начала пользователь вводит в цикле символы, пока не нажал точку. При этом мы заполняем множество S этими символами. После этого выводим на экран те символы, которые оказались цифрами. Для этого нам надо проверить вхождение цифр в это множество. Что мы благополучно и делаем. Ещё один пример использования множеств - стандартный запрос Y / N - раньше надо было писать 2 условия if (key = 'Y') or (key = 'y') теперь же всё гораздо проще - if key in ['Y', 'y'], так же можно добавть проверку, не нажал ли пользователь букву У вместо Y :) key in ['Y', 'y', 'У', 'у'] или же добавить ещё проверку на букву Д ....

Программа

Сегодня мы напишем програмку, позволяющую нам находить простые числа среди натуральных. В основу её будет заложен метод, названный решето Эратосфена. Суть этого метода очень проста - из множества чисел ( в начале оно является множеством [2 .. N]) берётся первое число (назовём его next) - оно является простым, потом из множества чисел удаляются само next и все кратные ему числа, т.е. next*2, next*3 и т.д. И так повторяем до тех пор, пока не исключим из исходного множества все элементы. Сам текст программы приведён ниже:

program pnum;

const
 N = 255;

type
 SetOfNumber = set of 1 .. N;

var
 n1, next, i : word;
 BeginSet, PrimerSet : SetOfNumber;

begin
 BeginSet := [2 .. N];  { начальное множество }
 PrimerSet := [1];  { это множество простых чисел,  в нём первое простое число 1}
 next := 2; {следующее простое }

 while BeginSet <> [] do
 begin
   n1 := next;

   { исключаем все числа кратные next }
   while n1 <= N do
   begin
      Exclude (BeginSet, n1);
      n1 := n1 + next
   end;

  { включаем next в множество }
   Include (PrimerSet, next);
   
   {получаем в next следующее простое, которое есть первое в BeginSet}
   repeat
     next := next + 1
   until (next in BeginSet) or (next > N)
 end;

 for i := 1 to N do
   if i in PrimerSet then
      write (i:8)
end.

Эту программу нельзя использовать для произвольного набора чисел, т.к. в множестве не может быть больше 256 элементов. Кстати в нашем множестве SetOfNumber 255 элементов, двайте ка добавим ещё один SetOfNumber = set of 1 .. 256 - компилируем и получаем жизнерадостное сообщение об ошибке, под номером 23 - Set base type out of range - тип множества выходит за границы. Эта ошибка происходит из-за того. что можно использовать целочисленный тип с минимальной границей 0 и максимальной 255 или любой перечисляемый тип, но не более чем с 256 элементами.