Множественный тип данных

Множество в языке Паскаль представляет собой на­бор различных элементов одного (базового) типа.

Базовый тип − это совокупность всех возможных элементов множества. Всего в базовом типе должно быть не более 256 различных элементов. Значение перемен­ной множественного типа может содержать любое ко­личество различных элементов базового типа − от нуля элементов (пустое множество) до всех возможных зна­чений базового типа (напомним, что их должно быть не более 256). Иными словами, возможными значениями переменных множественного типа являются все под­множества базового типа.

Множества, используемые в программе, могут быть описаны либо в разделеType:

Type <имя типа>=Set Of <тип элементов>;

Var <имя множества>: <имя типа>;

либо непосредственно в разделе описания переменных Var:

Var <имя множества>:

Set Of <тип элементов>;

Пример

Type mnog_Char=Set Of Char;

Var mn1: Set Of Char;

mn2: mnog_Char;

mn3: Set Of 'A'..'Z';

s1: Set Of Byte;

s2: Set Of 1000..1200;

Здесь mn1 и mn2 − это множества символов; так как различных символов всего 256, то тип Char можно использовать в качестве базового;

mn3 − множество больших латинских букв;

s1 − множество целых чисел (от 0 до 255); так как тип Byte содержит только целые числа от 0 до 255 (всего 256 различных чисел), его тоже можно использо­вать в качестве базового типа элементов;

s2 − множество целых чисел от 1000 до 1200.

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

Пример

Type digit=Set Of 1..5;

Var s: digit;

Переменная s может принимать значения, состоя­щие из любой совокупности целых чисел от 1 до 5:

[ ] − пустое множество;

[I], [2], [3], [4], [5] − одноэлементные мно­жества;

[1, 2], [1, 3], ..., [2, 4], [4, 5] − двухэле­ментные (пара любых элементов);

[1, 2, 3], [1, 2, 4],..., [3, 4, 5] − трехэле­ментные (тройка элементов);

[1, 2, 3, 4], [1, 2, 3, 5], [1, 2 , 4, 5], [1, 3, 4, 5], [2, 3, 4, 5] − четырехэлементные;

[1, 2, 3, 4, 5] − полное множество (взяты все элементы базового типа).

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

Объединением двух данных множеств называется множество элементов, принадлежащих хотя бы одно­му из этих множеств. Знак операции объединения множеств в Паскале − "+".

Примеры

1) ['А','F']+['В','D']=['A','F','B','D'];

2) [1..3, 5, 7, 11]+[3..8, 10, 12, 15..20]=[1..8, 10..12, 15..20]

Пусть S1:=[1..5, 9], a S2:=[3 .. 7, 12]. Тог­да если S:=S1+S2, то S=[1..7, 9, 12].

Пусть A1:=['a'..'z']; A1:=A1+['A'].

Тогда А1=['А', 'a'..'z'].

Пересечением двух множеств называется множество элементов, принадлежащих одновременно и первому, и второму множеству. Знак операции пересечения мно­жеств в Паскале − "*".

Примеры

1) ['А', 'F']*['В', 'D']=[ ], так как общих элементов нет;

2) [1..3, 5, 7, 11]*[3..8, 10, 12, 15..20]=[3, 5, 7];

3) если S1:=[1..5, 9] и S2:=[3..7, 12], a S:=SI*S2, то S=[3. .5].

Разностью двух множеств называется множество, со­стоящее из тех элементов первого множества, которые не являются элементами второго. Знак операции вычи­тания множеств − "−".

Примеры

1) ['А', 'F']-['В', 'D']=['А', 'F'], так как общих элементов нет;

2) [1..3, 5, 7, 11]-[3..8, 10, 12, 15..20] =[1, 2, 11];

3) S1:=[1..5, 9]; S2:=[3..7, 12]; S:=S1-S2; Тогда S=[1, 2, 9];

4) А1:=['А'..'Z']; А1:=А1-['А']. Тогда А1=['В'..'Z'].

Операция определения принадлежности

Элемента множеству

Эта логическая операция обозначается служебным словом in. Результат операции имеет значение true, если элемент входит в множество, и false в против­ном случае.

Примеры

1) Выражение 5 in [3..7] имеет значение true, так как 5Î[3; 7];

2) выражение 'a' in ['A'..'Z'] имеет значе­ние false, так как маленькой латинской буквы 'а' нет среди больших латинских букв.

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

If (ch='a') or (ch='b') or (ch='x') or (ch='y') Then... − может быть переписан в компактной и наглядной форме:

If ch in ['a', 'b', 'х', 'у'] Then...

Сравнение множеств

Для сравнения множеств используются операции от­ношения:

= − проверка на равенство (совпадение) двухмножеств;

<> − проверка на неравенство двух множеств;

<=, < − проверка на вхождение первого множества во второе множество;

>=, > − проверка на вхождение второго множества в первое множество.

Пример 1

Составить программу выделения следующих множеств из множества целых чисел от 1 до 30:

− множества чисел, кратных 2;

− множества чисел, кратных 3;

− множества чисел, кратных 6;

− множества чисел, кратных 2 или 3.

Вопросы для обсуждения

1. Сколько множеств надо описать? Каков тип их элементов? (Четыре множества с элементами типа Byte.)

2. Каково начальное значение множеств? (Начальное значение множеств − пустое множество.)

3. Как формируются множества? (Первые два фор­мируются перебором всех чисел данного промежутка и отбором подходящих, а третье и четвертое получаются из первых двух путем применения операций пересече­ния или объединения.)

4. Как осуществить вывод сформированных множеств? (Вывод множеств производится ТОЛЬКО поэлементно, поэтому удобно составить процедуру и передавать в нее множество, элементы которого и будут выводиться на экран. Для этого в разделе типов надо создать соответст­вующий тип и использовать его в дальнейшем.)

Программа для решения данной задачи выглядит так:

Program Example_139;

Const n = 30;

Type mn=Set Of 1..n;

Var n2, n3, n6, n23: mn;

{n2 - множество чисел, кратных 2,

n3 - кратных 3, n6 - кратных 6,

n23 - кратных 2 или 3}

k: Integer;

Procedure Print(m: mn);

Var i: Integer;

Begin

For i:=1 To n Do

If i In m Then Write(i:3);

Writeln;

End;

Begin

n2:=[ ]; n3:=[ ];

{начальные значения множеств}

For k:=1 To n Do {формирование n2 и n3}

Begin

{если число делится на 2, то

заносим его в n2}

If k Mod 2=0 Then n2:=n2+[k];

{если число делится на 3, то

добавляем его в n3}

If k Mod 3=0 Then n3:=n3+[k];

End;

{числа, кратные 6, - это те, которые

кратны и 2, и 3, поэтому это пересечение

двух первых множеств, а числа, кратные 2

или 3, - это объединение этих

же множеств}

n6:=n2*n3; n23:=n2+n3; {вывод множеств}

Writeln('числа, кратные 2');

Print(n2);

Writeln('числа, кратные 3');

Print(n3);

Writeln('числа, кратные 6');

Print(n6);

Writeln('числа, кратные 2 или 3');

Print(n23);

Readln;

End.

Задание

Изменить программу так, чтобы результатом ее рабо­ты являлось множество чисел, делящихся на 3, но не делящихся на 2.

Пример 2

"Мешанина". Если взять то общее, что есть у боба с ложкой, добавить кота и поместить в тепло, то получит­ся муравей. Так ли это? Состоит ли муравей из кота?

Вопросы для обсуждения

1. Сколько множеств надо задать и каков тип их эле­ментов? (Четыре множества с элементами символьного типа.)

2. Как сформировать множества? (С помощью опера­тора присваивания: например,

s1:=['б', 'о', 'б'])

3. Как сформировать искомые множества? (С помощью операций пересечения, объединения, вычитания множеств.) Программа для решения этой задачи приведена ниже:

Program Example_140;

Var y1, y2, у3, у4, х: Set of Char;

s: Char;

Begin

у1:=['б', 'о', 'б'];

y2:=[ 'л', 'о', 'ж', 'к', 'а'];

у3:=['к', 'о', 'т'];

у4:=['т', 'е', 'п', 'л', 'о'];

х:=(у1*у2)+у3-у4;

Writeln ('множество х');

{вывод множества х}

For s:='a' То 'я' Do

If s in x Then Write (s); Writeln;

{проверка: состоит ли муравей из кота}

If у3<=х Then Write ('муравей состоит

из кота')

Else Write('муравей не состоит

из кота');

End.

Пример 3

Дано натуральное число n. Составить программу, пе­чатающую в порядке возрастания все цифры, не входя­щие в десятичную запись данного натурального числа.

Вопросы для обсуждения

1. Какое множество нужно сформировать? (Множест­во цифр, входящих в десятичную запись данного числа.)

2. Как сформировать это множество? (С помощью операций div и mod последовательно выделить цифры данного числа и занести их во множество.)

3. Как получить искомый результат и как его вывести?

Программа для решения этой задачи такова:

Program Example_141;

Type mn=Set Of 0..9;

Vars: mn;

n: Longint;

k: Integer;

Begin

Writeln('введите число n');

Readln(n);

s:=[ ]; {формирование множества цифр

десятичной записи натурального числа}

While n<>0 Do

Begin

k:=n Mod 10;

n:=n Div 10;

If Not (k in s) Then s:=s+[k];

End;

{вывод цифр в порядке возрастания}

For k:=0 To 9 Do

If Not (k in s) Then Write(k:2);

Writeln;

Readln;

End.

Пример 4

"Решето Эратосфена". Составить программу поиска простых чисел в промежутке [1; n]. Число n вводится с клавиатуры.

Решение

Простым называется число, которое не имеет других делителей, кроме единицы и самого этого числа. Для решения этой задачи воспользуемся методом "решета Эратосфена", идея которого заключается в следующем: сформируем множество М, в которое поместим все чис­ла заданного промежутка. Затем последовательно будем удалять из него элементы, кратные 2, 3, 4 и так далее, до [n/2] (целая часть числа). После такого "просеива­ния" в множестве М останутся только простые числа.

Примечание. Легко доказать, что можно удалять числа, кратные 2, 3, 4 и так далее, до [sqrt(n)], то есть до целой части квадратного корня числа n.

Ниже приведен вариант решения этой задачи.

Program Example_142;

Var m: Set Of Byte;

i, k, n: Integer;

Begin

Writeln('введите размер промежутка

(до 255)');

Readln(n);

m:=[2..n]; {начальное значение}

For k:=2 To n Div 2 Do

{перебираем все делители }

For i:=2 To n Do {если число кратно

делителю и отлично от него, то удаляем

его}

If (i Mod k=0) And (i<>k) Then m:=m-[i];

{распечатаем оставшиеся элементы}

For i:=1 To n Do

If i in m Then Write(i:3);

Readln;

End.

Пример 5

Дан ребус:

МУХА

МУХА

СЛОН

Решение

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

Для решения этой задачи применим метод перебора с возвратом. Используем множество S1 для хранения цифр слова муха, причем будем заносить в него цифры последовательно, учитывая уже внесенные цифры. Началь­ное значение S1 − пустое множество. После выбора всех цифр первого слова формируем соответствующее число и находим число, соответствующее слову СЛОН. Выделяем цифры СЛОНа (множество S2), и если слова состоят из разных цифр (то есть пересечение S1 и S2 пустое) и все цифры СЛОНа разные, то выводим реше­ние на экран. Далее удаляем из множества S1 послед­нюю внесенную цифру и пытаемся выбрать еще одно ее значение. Таким образом, мы перебираем все возможные варианты и выводим на экран только те, которые удовлетворяют равенству.

Заметим, что букве “М” в слове МУХА может соот­ветствовать цифра от 1 до 4, а букве “А” в этом же слове не может соответствовать 0.

Ниже приводится одно из решений.

Program Example_143;

Type mn=Set Of 0..9;

Var m, y, x, a: 0..9; {цифры числа МУХА}

n1, n2: Integer; {числа МУХА и СЛОН}

a1, a2, a3, a4: 0..9;

{цифры числа СЛОН}

s1, s2: mn;

{для хранения цифр каждого из чисел}

Procedure Print (x,у: Integer);

{вывод решения в виде ребуса}

Begin

Writeln(x:5);

Writeln('+');

Writeln(x:5);

Writeln(' _____');

Writeln(y:5);

End;

Begin

s1:=[ ]; s2:=[ ];

For m:=1 To 4 Do

Begin

s1:=s1+[m];

{заносим первую использованную цифру}

For у:=0 To 9 Do {если эта цифра не

была еще взята, то добавляем ее во

множество цифр числа МУХА и выбираем

цифру для следующей буквы}

If Not (у in s1) Then

Begin

s1:=s1+[y];

For x:=0 To 9 Do

If Not (x in s1) Then

Begin

s1:=s1+[x];

For a:=1 To 9 Do

If Not (a in s1) Then

Begin

s1: =s1+[a];

n1 :=1000*m+100*y-10*x+a;

{число для слова МУХА}

n2:=2*n1;

{число для слова СЛОН}

a1:=n2 Div 1000;

{выделяем цифры СЛОНа}

а2:=n2 Div 100 Mod 10;

a3:=n2 Div 10 Mod 10;

a4:=n2 Mod 10;

s2:=[a1, a2, a3, a4];

{множество цифр СЛОНа}

{если слова состоят из разных

цифр и в слове СЛОН нет

одинаковых букв, то выводим

решение ребуса на экран}

If (s1*s2=[ ]) And

([al]*[a2]*[a3]*[a4]=[ ])

Then Print(n1, n2);

s1:=s1-[a];

{удаляем занесенную цифру}

End;

s1:=s1-[x];

End;

s1:=s1-[y];

End;

s1:=s1-[m];

End;

Readln;

End.