9. Множества

Множества – это наборы однотипных логически связанных друг с другом объектов. Характер связей между объектами лишь подразумевается программистом и никак не контролируется Турбо Паскаль. Количество элементов, входящих в множество, может меняться в пределах от 0 до 255 (множество не содержащее элементов называется пустым).

Именно непостоянством количества своих элементов множества отличаются от массивов и записей.

Два множества считаются эквивалентными тогда, и только тогда, когда все их элементы одинаковы, причем порядок следования элементов множества безразличен. Если все элементы одного множества входят также и в другое, говорят о включении первого множества во второе. Пустое множество включается в любое другое.

Пример:

Определение и задание множеств:

type

digitChar=set of '0'…'9';

digit=set of 0…9;

var

s1, s2, s3: digit Char;

s4, s5, s6: digit;

begin

. . . .

S1: =['1', '2', '3'];

S2: =['3', '2', '1'];

S3: =['2', '3'];

S4: =[0…3, 6];

S5: =[4, 5];

S6: =[3…9];

. . . .

end.

В этом примере множества S1 и S2 эквивалентны, а множество S3 включено в S2 , но не эквивалентно ему.

Описание типа множества имеет вид:

<имя типа> = SET OF <баз.тип>

Здесь <имя типа> – правильный идентификатор;

SET OF –зарезервированные слова (множество, из);

<баз.тип> – базовый тип элементов множества, в качестве которого может использоваться любой тип, кроме Word, integer, longint.

Для задания множества используется так называемый конструктор множества: список спецификаций элементов множества, отделяемых друг от друга запятыми; список обрамляется квадратными скобками. Спецификациями элементов могут быть константы или выражения базового типа.

Над множествами определены следующие операции:

* – пересечение множеств; результат содержит элементы, общие для обоих множеств, например:

S4*S6 содержит [3], S4*S5 –пустое множество;

+ – объединение множеств; результат содержит элементы первого множества; дополненные недостающими элементами из второго множества

S4+S5 содержит [0, 1, 2, 3, 4, 5, 6];

S4*S5 содержит [3, 4, 5, 6, 7, 8, 9];

- – разность множеств; результат содержит элементы из первого множества, которые не принадлежат второму:

S6-S5 содержит [3, 6, 7, 8, 9];

S4-S5 содержит [0, 1, 2, 3, 6];

= – проверка эквивалентности; возвращает TRUE, если оба множества эквивалентны;

< > – проверка неэквивалентности; возвращает TRUE, если оба множества неэквивалентны;

<= - проверка вхождения; возвращает TRUE, если первое множество включено во второе;

>= - проверка вхождения; возвращает TRUE, если второе множество включено в первое;

IN – проверка принадлежности. В этой операции первый элемент –выражение, а второй – множество одного и того же типа; возвращает TRUE, если выражение имеет значение, принадлежащее множеству:

3 in S6 возвращает TRUE;

2*2 in S1 возвращает FALSE.

Дополнительно к этим операциям можно использовать две процедуры

INCLUDE – включает новый элемент во множество

(Include(S,I) , где S – множество, I – элемент);

EXCLUDE – исключает элемент из множества

(Exclude(S,I), где S – множество, I – элемент).

В отличие от операций «+» и «-», реализующих аналогичные действия над двумя множествами, процедуры оптимизированы для работы с одиночными элементами множества и поэтому отличаются высокой скоростью быстродействия.

Пример:

Разработать программу выделения из первой сотни натуральных чисел всех простых чисел.

В основе программы лежит прием, известный под названием «решето Эратосфена». Суть программы состоит в следующем. Сначала формируется множество BEGINSET, состоящее из всех целых чисел в диапазоне от 2 до N. в множество PRIMERSET (оно будет содержать искомые простые числа) помещается 1. Затем циклически повторяются следующие действия.

• взять из BEGINSET первое входящее в него число NEXT и поместить его в PRIMERSET;

• удалить из BEGINSET число NEXT и все другие числа, кратные ему, т.е. 2*NEXT, 3*NEXT и т.д.

Цикл повторяется до тех пор, пока множество BEGINSET не станет пустым.

Эту программу нельзя использовать для произвольного N, т.к. в любом множестве не может быть больше 256 элементов.

Program PrimerNumberDetect;

{Выделение всех простых чисел из первых N целых}

Const

N=255; {Количество элементов исходного множества}

Type

SetOfNumber =set of 1…N;

Var

N1, next, i: word;{Вспомогательные переменные}

BeginSet;{Исходное множество}

Primer Set: SetOfNumber;{Множество простых чисел}

Begin

BeginSet:= [2…N];{Создаем исходное множество}

Primer Set:= [1];{Первое простое число}

Next:= 2;{Следующее простое число}

While Begin Set < >[]do

begin

n1:=next; {n1-число, кратное очередному простому (next)}

{Цикл удаления из исходного множества непростых чисел}

while n1<=N do

begin

Exlude(beginSet, n1);

n1:=n1+next{Следующее кратное}

end;

Include(PrimerSet, next);

{Получаем следующее простое, которое есть первое не вычеркнутое из исходного множества}

repeat

inc(next)

until (next in BeginSet) or (next >N)

end; {Конец основного цикла}

{Выводим результат:}

for i:=1 to N do

if i in PrimerSet then Write (i:8);

writeln

End.