8.2.3. Действия над множествами
В Паскале, как и в математике, над множествами можно выполнять следующие логические операции:
Рассмотрим эти операции подробно, но предварительно произведем описание:
type COUNTRIES = (ENG, FR, USA, SP, IT);
var MAP1, MAP2: COUNTRIES.
а) ОБЪЕДИНЕНИЕ (+) : [ENG, FR] + [IT] = [ENG, FR, IT];
б) ПЕРЕСЕЧЕНИЕ (*) : [ENG, FR, USA] * [ENG, USA, IT] = [ENG, USA];
в) РАЗНОСТЬ (-) : [ENG..IT] – [ENG..SP] = [IT].
Эти три операции используются для построения выражений над множествами, например:
MAP1 := MAP1 + [USA];
MAP1 := MAP1 * (MAP2 + [IT]).
П р и м е р. Решето Эратосфена. Найти все простые числа, не превосходящие заданного числа.
Алгоритм базируется на вычеркивании чисел, кратных выбранному.
const MAXPRIM = 15;
var PRIMES: set of 2..MAXPRIM;
COUNT, MULTIPLE: integer;
¦ writeln (‘простые числа, меньше ‘, MAXPRIM);
¦ for COUNT := 2 to MAXPRIM do
¦ if COUNT in PRIMES then
¦ ¦ for MULTIPLE := 1 to (MAXPRIM div COUNT) do
¦ ¦ PRIMES := PRIMES — [COUNT*MULTIPLE]
Примечание. Программа работает с множеством, состоящим из всех целых чисел в интервале 2 . 15. В ней при помощи цикла FOR проверяется каждое целое число, входящее в множество. Если оно является элементом множества, то печатается и из множества удаляются все целые числа, кратные данному числу.
8.3. Вывод множеств
При работе с множествами немаловажным является вопрос вывода на экран элементов множества. Отметим, что в большинстве версий языка в операторах WRITE нельзя называть переменные типа ARRAY. Например, нельзя вывести множество таким образом:
VAR A : SET OF 1..9;
Здесь нет ничего удивительного, так как даже если А есть массив, то его тоже нельзя распечатать сразу с помощью одного оператора WRITE (А). Для вывода элементов массива организуются циклы.
Для вывода элементов множества также нужно организовать цикл (однократный), внутрь которого вводится некоторая переменная, пробегающая все возможные значения этого множества, а перед оператором WRITE в рамках конструкции IF проверяется, входит ли этот элемент в конкретное множество:
if K in SET1 then write (K).
Как правило, для целей распечатки элементов множеств организуются свои процедуры. Пусть мы имеем дело с множествами, состоящими из целых чисел в границах NIZ и VERH. Зададим множественный тип TS для этих границ:
type INT = NIZ..VERH; TS = set оf INT.
Тогда можно написать процедуру, содержащую в качестве параметра множество:
procedure PRINTSET (OS : TS);
¦ for M := NIZ to VERH do
¦ if M in OS then writeln (M);
Теперь можно обращаться к этой процедуре для печати множеств, если только они состоят из элементов, не выходящих из интервала NIZ …VERH. Пусть в разделе констант было описано:
const NIZ = 0; VERH = 10.
Тогда можно вывести на экран элементы множества, обратившись к процедуре:
а) PRINTSET ([5, 6, 7]);
Обращение к процедуре можно организовать также в виде:
var SET1, SET2 : TS;
PRINTSET (SET1); PRINTSET (SET1 + SET2); и т.д.
П р и м е р . В заключение рассмотрим пример целиком, где продемонстрируем все те действия, которые определены над множествами.
type KOST = 1..6; BROSOK = set of KOST;
var A, B, C : BROSOK;
procedure SRAWNENIE (D : BROSOK);
¦ for K := 1 to 6 do
¦ if K in D then write (K:4); writeln;
¦ A := [1, 3, 4]; B := [2, 4, 6];
¦ write (‘[1, 3, 4] + [2, 4, 6] =’); SRAWNENIE (C);
¦ write (‘[1, 3, 4] – [2, 4, 6] =’); SRAWNENIE (C);
¦ write (‘[1, 3, 4] * [2, 4, 6] =’); SRAWNENIE (C);
Примечание. В программе определяются множества A, B, C типа BROSOK, элементами которых являются целые числа из диапазона [1..6], и процедура вывода на экран элементов таких множеств.
Затем задаются множества A и B, находятся различные значения множества C и выводятся его элементы.
Замечание 1. Если множество задано перечислимым типом, то его элементы напечатать нельзя. На печать можно вывести элементы только ординального типа: INTEGER, CHAR, BOOLEAN, интервальный.
Замечание 2. Один и тот же набор данных можно организовать в виде линейного массива ARRAY, в виде множества SET и в виде строки типа STRING. Какой из этих видов предпочтительнее? Если над элементами (числами) производятся действия, то лучше ARRAY. Если же стоит задача о взаимосвязи элементов нескольких множеств или вопрос о вхождении каких-то объектов в множество, то лучше SET.
Например, проверить, входит ли некоторая буква в заданный текст, можно двумя способами:
var TX : set of ‘a’..’z’;
1-й с п о с о б 2-й с п о с о б
for k := 1 to 20 do if BW in TX then writeln (‘да’).
if BW = TX [k] then OTWET := ‘да’;
Из приведенных фрагментов программ видно, что 2-й способ в данном случае предпочтительнее, так как здесь для определения вхождения буквы в текст достаточно однократного использования оператора IF, тогда как в первом случае для этого используется многократное применение того же оператора IF в операторе цикла FOR.
Множества
Множество представляет собой набор элементов одного типа. Элементы множества считаются неупорядоченными; каждый элемент может входить во множество не более одного раза. Тип множества описывается следующим образом:
В качестве базового может быть любой тип, в том числе строковый и классовый. Исключение составляют типы указателей.
type
ByteSet = set of byte;
StringSet = set of string;
Digits = set of ‘0’..’9′;
SeasonSet = set of (Winter,Spring,Summer,Autumn);
PersonSet = set of Person;
Элементы базового типа сравниваются на равенство следующим образом: у простых типов, строк и указателей сравниваются значения, у структурированных и у классов — значения всех элементов или полей. Однако, если поля относятся к ссылочному типу, то сравниваются только их адреса (неглубокое сравнение).
Чтобы сконструировать значение типа множество, используется так называемый конструктор множества, имеющий вид:
где в списке могут перечисляться через запятую либо выражения базового типа, либо (для порядковых типов) их диапазоны в виде a..b , где a и b — выражения базового типа. Например:
var
bs: ByteSet := [1,3,5,20..25];
fios: StringSet := [‘Иванов’,’Петров’,’Сидорова’];
Значения в списке могут отсутствовать, тогда множество является пустым:
Пустое множество-константа [] совместимо по присваиванию с множеством любого типа. Однако тип пустого множества-константы не выводится автоматически:
Множество, задаваемое конструктором множества, может иметь элементы различных типов, например:
В этом случае вычисляется наиболее общий тип, и он объявляется базовым типом множества. Например:
[1..4,5.5] // set of real
[‘1′,’abc’] // set of string
[1,’1′] // set of object
Для множеств имеет место структурная эквивалентность типов.
Множества целых и множества на базе типа и его диапазонного подтипа или на базе двух диапазонных типов одного базового типа неявно преобразуются друг к другу. Если при присваивании s := s1 во множестве s1 содержатся элементы, которые не входят в диапазон значений базового типа для множества s, то они отсекаются.
var st: set of 3..9;
.
st := [1..5,8,10,12]; // в st попадут значения [3..5,8]
Операция in проверяет принадлежность элемента множеству:
if Wed in bestdays then .
Для множеств определены операции + (объединение), — (разность), * (пересечение), = (равенство), <> (неравенство), <= (нестрогое вложение), < (строгое вложение), >= (нестрого содержит) и > (строго содержит).
Процедура Write при выводе множества выводит все его элементы. Например,
выведет [‘Иванов’,’Петров’,’Сидорова’] , при этом данные, если это возможно, будут отсортированы по возрастанию.
Для перебора всех элементов множества можно использовать цикл foreach , данные перебираются в некотором внутреннем порядке:
foreach var s in fios do
Write(s,’ ‘);
Для добавления элемента x к множеству s используется конструкция s += [x] или стандартная процедура Include : Include(s,x) . Для удаления элемента x из множества s используется конструкция s -= [x] или стандартная процедура Exclude : Exclude(s,x) .
Как организовать вывод элементов множества
Главная / Раздел 5
Сложные типы данных.
Множества
Тип "множество" является одним из сложных типов данных системы программирования Turbo Pascal 7.0. Тип "множество" является множеством всевозможных сочетаний объектов исходного порядкового типа. Число элементов исходного множества в Turbo Pascal не должно превышать 256. Все значения базового типа, образующие конкретные значения множественного типа, должны быть различны. Порядок "расположения" элементов в множестве никак не фиксируется. Это соответствует принятой в математике трактовке множества как бесповторной неупорядоченной совокупности объектов.
Описание (декларация) типа множество.
Для задания типа "множество" следет использовать служебные слова set и of, а затем указать элементы этого множества, как правило, в виде перечисления или диапазона, например:
Введя тип "множество", можно задать переменные этого типа.
Так же как и для других структурированных типов тип множество можно задать непостредственно при задании переменных.
Присвоение для переменных типа множество.
Множеству можно в программе присвоить то или иное значение. Обычно значение задаётся с помощью так называемого конструктора множества. Конструктор задаёт множество элементов с помощью перечисления в квадратных скобках выражений, значения которого дают элементы этого множества. Допустимо использовать диапазоны элементов.
В каждое множество включается и т.н. пустое множество [], не содержащее никаких элементов. Конструктор множества можно использовать и непосредственно в операциях над множествами.
Операции над множествами.
Так же как и в математике в системе программирования Turbo Pascal 7.0 над множествами применимы следующие операции:
+ — объединение множеств. C := A+B;
Каждый элемент множества C является элементом либо множества A, либо множества В.
— — разность множеств. C := A-B;
Каждый элемент множества C является элементом множества A, но не является элементом множества В.
* — пересечение множеств. C := A*B;
Каждый элемент множества C является элементом множества A и B одновременно.
Множество A равно множеству B, если каждый элемент множества A является элементом множества B, и наоборот, каждый элемент множества B является элементом множества A. Результат операции логическая величина.
<> — проверка неэквивалентности двух множеств. A <> B;
Множество A не равно множеству B, если множество A содержит хотя бы один элемент, не являющийся элементом множества B, или (и) наоборот, множество B содержит хотя бы один элемент, не являющийся элементом множества A. Результат операции логическая величина.
<= — проверка, является ли левое множество подмножетвом правого.
A <= B; Множество A является подмножеством множества B, если все элементы множества A являются элементами множества B. Результат операции логическая величина.
>= — проверка, является ли правое множество подмножеством левого.
A >= B; Действие операции аналогично действию предыдущей операции. Результат операции логическая величина.
in — проверка, входит ли элемент (слева) в множество (справа).
C in B; результат операции логическая величина.
Примеры программ.
Из множества целых чисел 1..20 выделить: множество чисел, делящихся на 6 без остатка; множество чисел делящихся на 2 или на 3 без остатка. Вывести содержимое этих множеств на экран.
Ввести строку символов, состоящую из латинских букв цифр и пробелов. Осуществить проверку правильности введённых символов.
Решу Паскаль
Множества в языке Паскаль: описание, хранение, операции, вывод, использование
Когда мы произносим слово множество, подразумеваем большое количество объектов:
- множество целых чисел,
- множество латинских букв,
- множество слов.
В этой публикации расскажем, как использовать множества в языке Паскаль.
Множество — это набор уникальных неупорядоченных значений одного типа.
Описание (объявление) множества
var m:set of базовый тип;
Примеры
Целые числа
Описание
в блоке var
m : set of integer ;
s : set of string ;
Хранение данных в множестве
m:=[3,4,6,8,9]; элементы множества заключаются в квадратные скобки и перечисляются через запятую
m:=[0..9]; диапазон значений через две точки
Операции над множествами
- пересечение
- объединение
- вычитание
Применение операций над множествами
m2:=m*m1; пересечение [3,4,9]
m2:=m+m1; объединение [3,4,6,8,9,15,20]
m2:=m1-m; разность [15,20]
Пустое множество
Как добавить значение в множество
m:=m+[x]; значение переменной x добавили в множество m
Операция вхождения in
Обратиться к элементу множества непосредственно нельзя. Но можно использовать операцию вхождения in.
Вывод множества на экран
for k:=10 to 24 do
if k in m then write(k); //если значение k принадлежит множеству m, то вывести k
В версии PascalABC.NET 3.8.2 множество можно вывести целиком:
Результат будет таким:
Использование множеств в задачах
Задача 1. Дано натуральное число. Сформировать множество его цифр (найти различные цифры числа)
В цикле while будем разбивать число на цифры и добавлять цифру в множество.
Исходные данные: n – натуральное число (тип integer)
Промежуточные данные: d – цифра числа (тип integer)
Выходные данные: m – множество цифр числа
Программа решения на языке Паскаль
var m:set of integer;
m:=[]; //пустое множество
writeln(‘Введите натуральное число’);
writeln(‘Множество цифр числа’);
Результат выполнения программы
Задача 2. Дан алфавит строчных русских букв, получить множество согласных букв вычитанием множества гласных букв.
Воспользуемся тем, что char является порядковым типом данных, в качестве букв алфавита возьмем множество b:=[‘а’..’я’] .
Множество гласных букв получим перечислением: g:=[‘у’,’е’,’ы’,’а’,’о’,’э’,’я’,’и’,’ю’]
Множество согласных букв получим вычитанием s:=b-g;
b – множество строчных русских букв
g – множество строчных гласных букв
Выходные данные: s – множество строчных согласных букв
Программа решения на языке Паскаль
var b,g,s:set of char;k:char;
if k in s then write(k,’ ‘);
Задача 3. Дана строка символов. Сколько в этой строке символов цифр?
Будем проверять принадлежность символа строки множеству символов цифр [‘0’..’9′] и копить счетчик.
Программа решения на языке Паскаль
for k:=1 to length(s) do
if s[k] in m then t:=t+1;
writeln(‘Символов цифр в строке: ‘,t);
Еще одна задача на применение операции вхождения in. Как проверить, есть ли в строке заданная подстрока.
Результат выполнения программы
Задача 4. Как найти все уникальные (неповторяющиеся) значения в массиве чисел?
Мы знаем, что множество хранит уникальные значения. Возьмем пустое множество.
Если в множестве нет значения, равного элементу массива, то добавим значение этого элемента в множество. Таким образом, в множестве сохранятся значения элементов массива, и они будут уникальными.
Программа решения на языке Паскаль
var a:array[1..100] of integer;
m:set of integer;
writeln(‘Введите количество элементов массива’);
m:=[]; //пустое множество
a[k]:=random(1,10);//случайные числа из промежутка [1;10]
if not(a[k] in m) then //если значения элемента a[k] нет в множестве
m:=m+[a[k]]; //добавить значения элемента a[k] в множество m
writeln(‘Уникальные элементы массива’);
for k:=1 to 10 do //цикл по числам из промежутка от 1 до 10
if k in m then write(k,’ ‘); //если число k принадлежит множеству, вывести число k
// либо вывод сразу всего множества write(m), цикл for k:=1 to 10 do тогда не нужен