Учебное пособие Для студентов технических специальностей всех форм обучения

§6.4. Множества

{A, B, C}, {A, C, B}, {B, C, A}

и т.д., то есть элементы множества не упорядочены.

На вид объектов и их число не накладываются никакие ограничения, но в языке Турбо-Паскаль это понятие существенно уже: в качестве базовых типов допускаются дискретные типы не более чем с 256 различными значениями, то есть типы byte, char, boolean, перечисляемый и диапазон.

Описание типа:

Туре <тип_множество> = SET OF <базовый_тип>

Var <список_переменных>: SET OF <базовый_тип>

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

[Blue, Yellow, Red] или [1,4..8,12,15].

Существует единственное пустое множество, которое принадлежит всем типам множеств и обозначается как [ ].

Пусть есть описание:

Var A, B, C: Set of 0..9;

D, E: Set of '0'..'9';

F, G: Set of Boolean;

Тогда:

A:=[1, 3, 5];

При использовании диапазонов, если значение первой константы меньше значения второй константы диапазона, то задается пустое множество. Запись [5..3] эквивалентна [ ].

S1+S2 содержит элементы, которые принадлежат либо S1, либо S2, либо и тому и другому:

A:=[1, 2, 3];

B:=[1, 5, 9];

C:=A+B;

что эквивалентно

S1*S2 содержит элементы, которые принадлежат как S1, так и S2:

A:=[1, 2, 3];

B:=[1, 5, 9];

C:=A*B;

что эквивалентно

Или выражение

C:=A*[8];

соответствует пустому множеству:

C:=[ ];
3. Относительное дополнение или разность множеств.

S1-S2 содержит элементы из S1, которые не принадлежат S2:

A:=[1, 2, 3];

B:=[1, 5, 9];

C:=A-B;

что эквивалентно

Или выражение

C:=A-[3..9];

соответствует:

C:=[1, 2 ];
4. Проверка на равенство, неравенство и включение множеств.

S1=S2 тогда и только тогда, когда S1 и S2 содержат одни и те же элементы. В противном случае истинно выражение S1<>S2. S1<=S2 принимает истинное значение, когда все элементы S1 являются элементами S2 (множество S2 включает в себя множество S1). Пусть

A:=[1..5];

B:=[1..5];

C:=[1..6];

Тогда логические выражения примут значения:

A=B — истинно;

А=С — ложно;

B<>C — истинно;

A<=C — истинно (С включает А).

5. Проверка принадлежности множеству (включение во множество).

Эта логическая операция обозначается служебным словом in. Выражение X in S1 истинно, если элемент Х принадлежит множеству S1 и ложно в противном случае:

2 in A — истинно;

9 in A — ложно.

Этот тип данных используется довольно редко, за исключением операции проверки принадлежности к множеству. Например, нажата ли клавиша «p» в любом регистре и алфавите:

If CH in ['p', 'P', 'з', 'З'] then ... {нажата клавиша «р»}

Пример использования множеств

В качестве примера используется программа вычисления нескольких первых простых чисел методом «решета Эратосфена», выполняемого по следующему алгоритму.

1. 
   Поместим все числа между 2 и n в «решето».
   
2. 
   Выберем и вынем из «решета» наименьшее из оставшихся в нем чисел.
   
3. 
   Поместим это число среди «простых» чисел.
   
4. 
   Переберем и вынем из решета все числа, кратные данному.
   
5. 
   Если решето не пустое, повторим шаги 2-5.
   

Program Eratosfen;

Const N=255; { Максимально возможное значение }

Var

R, { исходное решето }

Pr { решето с простыми числами - итог }

: Set of 2..N;

i, { счетчик чисел }

j { очередное простое число }

: integer;

Begin

R:=[2..N];

Pr:=[]; { пока в решете с простыми числами ничего нет}

j:=2; { первое простое число }

{ цикл по шагам 2-5}

Repeat

{ поиск очередного простого числа

(первый раз не выполняется ни разу) }

While not (j in R) do

j:=j+1;

Pr:=Pr+[j]; { включение в итог – шаг 3}

i:=j;

Writeln(j:8);

While i<=N do

Begin

R:=R-[i]; { вынимание из решета – шаг 4}

i:=i+j

end;

Until R=[ ]; { повторяем, если решето не пустое }

end.

жүктеу/скачать 2.27 Mb.

Достарыңызбен бөлісу: