Теоретический материал (Паскаль)

Сайт:	Информатикс
Курс:	Типы данных
Книга:	Теоретический материал (Паскаль)

Напечатано::	Гость
Дата:	Пятница, 27 Июнь 2025, 19:26

Множественный тип данных. Множество. Элемент множества. Способы задания множества. Объединение множеств. Разность множеств. Пересечение множеств

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

Определение. Под множеством в Паскале понимается конечная совокупность элементов, принадлежащих некоторому базовому типу.

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

Такие ограничения связаны с формой представления множества в языке и объясняются тем, что функция Ord для элементов используемого базового типа должна быть в пределах от 0 до 255.

Множество имеет зарезервированное слово set of и вводится следующим описанием

Type
  < имя типа > = set of < имя базового типа >;
Var
  < идентификатор,... >:< имя типа >;

Рассмотрите примеры описаний множеств:

Type
  SetByte = set of byte; {множество 1, определённое над типом byte} 
  SetChisla = set of 10 .. 20; {множество 2, определённое в диапазоне от 10 до 20}
  Symbol = set of char; {множество, определённое на множестве символов}
  Month = (January, February, March, April, May, June, July, August, September, October, November, December);
  Season = set of Month; {тип множества, определённый на базе перечислимого типа Month}
Var
  Letter, Digits, Sign : Symbol; {множествa, определённые над символьным типом}
  Winter, Spring, Summer, Autumn, Vacation, WarmSeason : Season;
  Index : SetChisla=[12, 15, 17];
  Operation : set of (Plus, Minus, Mult, Divid);
  Param : set of 0..9=[0, 2, 4, 6, 8];

Для переменных типа множества в памяти отводится по 1 биту под каждое возможное значение базового типа. Так, под переменные Letter, Digits, Sign будет отведено по 256/8=32 байта. Для переменной Winter, базовый тип которой (Month) имеет 12 элементов, необходимо 2 байта, причем второй используется только наполовину. Если множество содержит какой-то элемент, то связанный с ним бит имеет значение 1, если нет - 0.

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

Sign:=['+', '-'];
Spring:=[March, April, May];
b:=[ 'k', 'l', 'd' ]

либо определение через диапазон. В этом случае в множество включены все элементы диапазона.

Digits:=['0'..'9'];
WarmSeason := [May .. September];

Обратите внимание, что в определении множества Digits использованы символы в таблице ASCII-кодов, а не целые числа.

Обе формы конструирования могут сочетаться:

Vacation:=[January, February, June .. August];

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

{постоянное множество допустимых символов}
Const
  YesOrNo = ['Y', 'y', 'N', 'n'];
  {множества - типизированные константы}
Const
  Digits : set of char=['0'..'9'];
  DigitsAndLetter : set of char=['0'..'9', 'a'..'z', 'A'..'Z'];
  {применение операции "+" для объявления множества-константы}
Const
  Yes = ['Y', 'y'];
  No = ['N', 'n'];
  YesOrNo = Yes+No;

Объединение множеств (+)

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

Объединение множеств записывается как операция сложения.

Type
  Symbol = set of char; 
Var
  SmallLatinLetter, CapitalLatinLetter, LatinLetter : Symbol;
Begin
  . . . . . . 
  SmallLatinLetter :=['a'..'z'];
  CapitalLatinLetter := ['A'..'Z'];
  LatinLetter := SmallLatinLetter+CapitalLatinLetter;
  . . . . . . 
End.

В операции объединения множеств могут участвовать и отдельные элементы множества.

Например, допустима следующая запись, где два элемента и множество объединяются в новое множество:

WarmSeason := May+Summer+September;

или другая запись

B: = B+['c'];

которую можно применить для организации множества в цикле, если заменить множество ['c'] переменной Sym того же типа, что и множество B, и считывать с клавиатуры данные в переменную Sym, объединяя ее затем с множеством В.

B: = B+Sym;

Разность множеств (-)

Определение. Разностью двух множеств является третье множество, которое содержит все элементы 1-го множества, не входящие во 2-е множество.

a: = a-[ 'd' ];

Если в вычитаемом множестве есть элементы, отсутствующие в уменьшаемом, они не влияют на результат.

Summer := WarmSeason-Spring-Autumn;
Summer := WarmSeason-May-September;

Модуль System содержит процедуры для включения элемента в множество

Include(Var S : set of T; Element : T);

и исключения из множества

Exclude(Var S : set of T; Element : T);

где S - множество элементов типа Т, а Element - включаемый (или исключаемый) элемент.

Эти функции отличаются от операций объединения и вычитания множеств только тем, что генерируют более эффективный код.

Пересечение множеств

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

Summer := WarmSeason*Vacation;

Логические операции над множествами: проверка принадлежности элемента множеству, проверка включения элемента в множество, сравнение множеств

Определение. Множества считаются равными, если все элементы, содержащиеся в одном множестве, присутствуют в другом, и наоборот.

В соответствии с этим правилом определяется результат операций сравнения "=" и "<>".

Например,

If WarmSeason*Vacation=Summer 
  Then
    Writeln ('Правильно');

Задание. Сравните множества М1 и М2, пользуясь рисунками.

Проверка включения

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

Операции проверки вхождения одного множества в другое записываются как "<=" или ">="

if S1<=S2
  then
    writeln ('S1 входит в S2');
if S1>=S2
  then
    writeln ('S2 входит в S1');

Задание. Подумайте, что напечатает оператор Write в каждом из случаев:

if Vacation>=Summer 
  then
    writeln ('Правильно')
  else
    writeln ('Неправильно');

if Vacation<=Summer 
  then
    writeln ('Правильно')
  else
    writeln ('Неправильно');

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

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

Например, выражение

May in WarmSeason

имеет значение True.

Использование множеств и операции in позволяет, в частности, сделать эффективнее проверку правильности вводимых символов.

Например, для проверки допустимости введенного символа можно использовать следующее условие:

(Reply='y') or (Reply='Y') or (Reply='n') or (Reply='N')

Но если ввести множество

Const
  AllowSymbol : set of char = ['Y', 'y', 'N', 'n'];

проверяемое условие можно записать в более компактной форме:

Reply in AllowSymbol

Примечание. Множественный тип данных не может быть использован для определения функции.

Рассмотрите пример.

Задача. Описать множество М(1..50). Сделать его пустым. Вводя целые числа с клавиатуры, заполнить множество 10-ю элементами.

В разделе описания переменных опишем множество целых чисел от 1 до 50, переменную Х целого типа будем использовать для считывания числа-кандидата в множество, целую переменную i используем для подсчета количества введенных чисел.

В начале программы применим операцию инициализации множества М:=[ ]. Так множество в правой части оператора присваивания не имеет элементов, множество М будет пустым.

Заполнние множества организуем в цикле Repeat, параметр которого i будет указывать порядковый номер вводимого элемента. Операцию добавления элемента в множество запишем оператором присваивания М:=M+[X]. Перед добавлением элемента выполним его проверку на допустимость (0 < X < 50). При выполнении условия X in M выведем сообщение о том, что число Х уже принадлежит в множеству.

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

Program InputMno;
Var
  M : set of 1..50;
  X, i : integer;
Begin
  M := [ ];
  i :=1;
  repeat
    write('Введите ',i,'-й элемент множества');
    readln(X);
    if (X in M)
      then
        writeln(Х, ' уже содержится в множестве')
      else

        if (X < 1) or (X > 50) 
          then
            writeln('Недопустимое значение ',  Х)
          else

            begin
              writeln(Х, ' помещен в множество');
              M := M+[X];
              i := i+1;
            end;
  until i>10;
End.

Задание. Наберите рассмотренную программу, откомпилируйте ее. Проверьте работу программы, исполняя ее по шагам и наблюдая текущие значения переменных i, X, M в окне просмотра. Попробуйте задать значения числа большие 50, повторно задавать одинаковые значения Х и анализируйте значения множества М. Дополните программу выводом на экран содержимого полученного множества. Откомпилируйте программу.

Примеры решения задач на применение множеств

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

Зададим тип Letters - множество букв русского языка, затем опишем переменные этого типа: Glasn - множество гласных букв, Sogl - множество согласных букв. Вводимое с клавиатуры предложение опишем переменной Text типа String. Для указания номера символа в строке Text применим переменную i типа byte. Для подсчета количества гласных и согласных букв опишем переменные G и S. Проверку принадлежности символов, составляющих предложение, множеству гласных или согласных букв русского языка организуем с использованием оператора цикла For. Параметр цикла i, изменяясь от 1 до значения длины предложения, будет указывать порядковый номер символа в предложении. Принадлежность очередного символа предложения множеству гласных или согласных букв проверим с помощью операции in. Если выполняется условие Text[i] in Sogl, тогда увеличивается на 1 счетчик S. Если выполняется условие Text[i] in Glasn, тогда увеличивается на 1 счетчик G. Если не выполняется ни первое, ни второе условие, значит, очередной символ в предложении не является гласной или согласной буквой русского языка.

Теперь рассмотрите текст программы:

Program GlasnSogl;
Type
  Letters = set of 'A'..'я';
Var
  Glasn, Sogl : Letters;
  Text : String;
  i, G, S : byte;
Begin
  Glasn := ['A', 'а', 'Е', 'е', 'И', 'и', 'О', 'о', 'У', 'у', 'ы','Э', 'э', 'Ю', 'ю', 'Я', 'я', 'Ё', 'ё'];
  Sogl := ['Б'..'Д', 'б'..'д', 'Ж', 'ж', 'З', 'з', 'К'..'Н', 'к'..'н', 'П'..'Т', 'п'..'т', 'Ф'..'Щ', 'ф'..'щ', 'ь', 'ъ'];
  Write('Введите предложение ');
  Readln(Text);
  G := 0;
  S := 0;
  For i := 1 to Length(Text) do
    Begin
      If Text[i] in Glasn
        Then
          G := G+1;
      If Text[i] in Sogl 
        Then
          S := S+1;
    End;
  Write('В предложении " ', Text, ' " ', G, ' гласных и ', S, ' согласных букв');
End.

Задание. Усовершенствуйте программу, дополните комментарием. Если у Вас возникла идея решения этой задачи с помощью другого алгоритма, - дерзайте.

Пример 2. Поиск простых чисел с помощью решета Эратосфена в числовом промежутке [1 .. N].

В теме "Целочисленная арифметика" Вы решали задачи на поиск простых чисел в заданном диапазоне различными способами. Здесь мы рассмотрим ту же задачу, но применим для ее решения знания, полученные при изучении темы "Множества".

Примечание. Вспомним, что простым числом называется число, не имеющее делителей, кроме единицы и самого себя.

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

Рассмотрите вариант решения этой задачи.

Program Resheto;
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.

Ответьте на вопросы:

Как сформировано множество М?
Как организован просмотр элементов этого множества?
Как организован просмотр делителей?
Как удаляется элемент множества?
Как организован вывод "просеянного" множества?

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

Задание. Улучшите алгоритм решения предложенной задачи. Протестируйте программу и дополните ее комментариями.

Примечание. Если Вы затрудняетесь при выполнении задания, то вот Вам подсказки:

Например, вы знаете, что если из множества М удалены все элементы, делящиеся на 2, то нет смысла проверять, делятся ли оставшиеся числа на 4, 6, 8, 10, и т.д.

Когда программа проверяет делимость, например, на 50, то она проверяет и числа до 50, что не имеет смысла.

Пример 3. Разгадывание ребусов.

+ МУХА
МУХА
СЛОН

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

Заметим, что значение буквы М в слове МУХА может иметь значения от 1 до 4, а буква А в этом же слове не может быть равна 0.

Рассмотрите решение задачи.

Program Rebus;
Type
  MN = set of 0..9;
Var
  digit, m, u, h, a : 0..9;
  i,  n1, n2 : Integer;
  S1, S2 : MN;
  f : boolean;
Procedure Print(x, y : Integer);
Begin
  write(x);
  write(' + ');
  write(x);
  write(' = ');
  writeln(y);
  writeln;
End;
Begin
  S1 := [ ];
  for m := 1 to 4 do
    begin
      S1 := S1+[m];
      for u := 0 to 9 do
        if Not(u in S1)
          then
            begin
              S1 := S1+[u];
              for h := 0 to 9 do
                if Not (h in S1)
                  then
                    begin
                      S1 := S1+[h];
                        for a := 1 to 9 do
                          if Not (a in S1) 
                            then
                              begin
                                S1 := S1+[a];
                                n1 := 1000*m+100*u+10*h+a; {число MUHA}
                                n2 := 2*n1; {число SLON}
                                f := true;  {все цифры в числе SLON - разные}
                                S2 := [ ];
                                for i := 1 to 4 do
                                  begin
                                    digit := n2 mod 10; {выделяем цифру числа SLON}
                                    n2 := n2 div 10;
                                    f := f and not (digit in s2); {цифра повторяется?}
                                    S2 := [digit] + S2;
                                  end;
                                if (S1*S2=[ ]) and f {если все цифры в примере разные}
                                  then
                                    Print (n1, 2 * n1);
                                S1 := S1-[a];
                              end;
                     S1 := S1-[h];
                end;
            S1 := S1-[u];
        end;
      S1 := S1-[m];
    end;
  Readln;
End.

Задание. Решите один из ребусов:

П Ч Ё Л К А x 7 = ЖЖЖЖЖЖ
ТОРГ x Г = ГРОТ
ЛАДЬЯ+ЛАДЬЯ = ФЕРЗЬ
М3 = КУБ
СМ3 = КУБИК
МАТЕ * М = АТИКА
ПРОП * О = РЦИЯ
ПРОП : О = РЦИЯ
(М + О + С +К + В + А)4 = МОСКВА
ВЕТКА + ВЕТКА = ДЕРЕВО
САР = АТОВ
ПЛОМБА * 5 = АПЛОМБ
НИКЕЛЬ * 6 = ЕЛЬНИК
КВАНТ * 30 = ЖУРНАЛ
КАПЛЯ + КАПЛЯ + КАПЛЯ + = ОЗЕРКО
СОРОК * 5 = ДВЕСТИ
SIX * TWO = TWELVE
ДВЕСТИ * 5 = ТЫСЯЧА
НАТАША + ТОНЯ = СЁСТРЫ
БРА2 = БОМДОР

Пример 4. Рассмотрите специальную процедуру ввода положительных целых чисел, которая запрещает набор иных символов, кроме цифр, и ограничивает число используемых символов.

Procedure ReadWord(Var Result : Word; x, y, MaxLength : byte);
Const
  ValidSymbol : set of char=['0'..'9',#8,#13];
Var
  Str : string;
  Code : integer;
  Key : char;
Begin
  GoToXY(x, y);{курсор - в заданную позицию}
  Str := ''; {строка пустая}
  repeat {начало бесконечного цикла}
    {проверка вводимых символов на допустимость}
    repeat
      Key := ReadKey
    until Key in ValidSymbol; 
    case Key of {анализ вводимых символов}
      '0'..'9' : {нажата цифра}
        if Length(Str)>=MaxLength {если длина больше заданной}
          then
            begin
              Sound(100); {звуковой сигнал}
              Delay(200);
              NoSound;
            end
          else {если длина меньше заданной}
            begin
              write(Key); 
              Str:=Str+Key; {добавление символа в строку}
            end; 
      #8 : {нажата клавиша BackSpace}
        if Length(Str)>0 {если строка не пустая}
          then
            begin
              Delete(Str, Length(Str),1); {удаление из строки}
              GoToXY(WhereX-1, WhereY); {возврат курсора}
              write(' '); {запись пробела вместо символа}
              GoToXY(WhereX-1, WhereY); {возврат курсора}
            end
          else {если строка пустая}
            begin
              Sound(100); {звуковой сигнал}
              Delay(200);
              NoSound;
            end;
      #13 : {нажата клавиша Enter}
        begin
          Val(Str, Result, Code); {преобразование строки в целое число}
          Exit {выход из подпрограммы}
        end;
      end; {конец оператора Case}
  until False; {бесконечный цикл}
End;

В заголовке процедуры Result - возвращаемое число; MaxLength - максимальное число цифр в записи числа; х, у - координаты начальной позиции вывода. Процедура формирует текстовую строку Str, состоящую из цифр. При нажатии клавиши Enter строка преобразуется в целочисленную переменную.

В начале программы курсор направляется в заданную точку, и текстовой строке присваивается пустое значение. Далее начинается бесконечный цикл, заданный оператором Repeat ... Until False. Выход из цикла происходит вместе с выходом из процедуры по команде Exit. "Бесконечность" цикла обеспечивает произвольное число повторов и исправлений при вводе числа.

Процедура реагирует только на нажатие цифровых клавиш, клавиш Enter и BackSpace. Назначение клавиш - традиционное: Enter используется для завершения процедуры, BackSpace - для стирания последнего введенного символа.

Цикл

  repeat
    Key := ReadKey
  until Key in ValidSymbol;

проверяет вводимые символы на допустимость. Множество допустимых символов ValidSymbol определено в процедуре как константа, оно включает цифровые символы и символы, соответствующие клавишам Enter и BackSpace. Первая имеет символьный код #13, вторая - #8.

Далее оператор Case производит выбор одного из трех направлений - обработка нажатой цифры, обработка клавиши BackSpace или обработка клавиши Enter. При нажатой цифре сначала проверяют, не достигло ли число цифр максимального значения. Число цифр определяется функцией Length, аргумент которой - редактируемая строка. Если длина уже достигла максимального значения, выдается звуковой сигнал. Если длина вводимой строки меньше максимальной, то в строку дописывается символ, и он же выводится на экран процедурой Write.

При нажатии клавиши BackSpace должен быть стерт последний введенный символ. Вначале производится проверка, есть ли в строке символы. Если строка пуста, подается звуковой сигнал, если нет - начинается удаление символа. Для этого строка уменьшается на один элемент процедурой Delete, курсор возвращается назад на одну позицию, на место стираемой цифры записывается символ пробела, затем курсор снова возвращается на позицию назад. Возврат курсора обеспечивается оператором GoToXY(WhereX-1, WhereY), который использует функции WhereX и WhereY для определения текущего положения курсора и уменьшает координату х на 1.

После нажатия Enter строка преобразуется в целочисленную переменную процедурой Val, и происходит выход из процедуры ReadWord по команде Exit.

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

Поскольку все проверки усложняют программу, требование защиты от возможных ошибок программиста не является обязательным. Вопрос в том - надеется ли программист на свою аккуратность при использовании собственных процедур.

Задание*. Составьте программу для проверки входных данных другого типа.