Множества в Pascal
В Pascal множества обладают рядом особенностей. Все элементы одного множества должны принадлежать одному и тому же базовому типу. В качестве базового типа должен выступать порядковый тип, но не каждый.
Размер множества в Паскале ограничен предельно допустимым количеством элементов. Во множествах допускаются только такие элементы, порядковые значения которых в их базовых типах не выходят за границы 0..255. Для целочисленных множеств это означает, что в них могут присутствовать только числа от 0 до 255. Отрицательные элементы во множествах не допускаются.
Поэтому базовым типом не может выступать, например, integer . Если необходимо множество целочисленных объектов, то базовый тип должен объявлен как диапазон типа byte . Для символьных множеств базовым типом является char (в нем 256 значений с порядковыми номерами от 0 до 255).
Объявление множеств
В математике для обозначения множества используют фигурные скобки, например , в Паскале — квадратные, например [1, 3, 5]. Порядок элементов во множестве не имеет значения. Так множества [3, 6, 9] и [9, 3, 6] одинаковы.
По форме записи объявление переменной типа множество сходно с объявлением одномерного массива:
var имя: set of тип;Например, объявление переменной ch как множества с базовым типом char , имеет вид:
var ch: set of char;Можно сначала объявить тип множества, а потом использовать его для объявления переменных:
type t_ch = set of char; var ch1, ch2: t_ch;Часто в качестве базового типа используются перечисления и диапазоны:
type week_days = (Mon, Tue, Wed, Thu, Fri); var work_days: set of week_days; lett: set of 'A'..'Z';type nums = 5..25; var a: set of nums;Объявление переменной-множества не присваивает ей набора значений.
Построение множества
Чтобы во множестве появились элементы, необходимо выполнить оператор присваивания, в левой части которого стоит имя переменной-множества, а в правой — конструктор множества или некоторое выражение над множествами.
Конструктор множества — это заключенный в квадратные скобки перечень элементов, разделенных запятыми. В качестве элементов могут использоваться диапазоны значений:
type week_days = (Mon, Tue, Wed, Thu, Fri); var work_days: set of week_days; lett: set of 'A'..'Z'; begin work_days := [Mon, Wed, Thu]; lett := ['C', 'E'..'M', 'Z'] end.Следует помнить, что при задании множества порядок его элементов безразличен, но при задании диапазона такой порядок важен.
Множество, в котором нет элементов, называется пустым (или нуль-множеством). В языке программирования Паскаль обозначается квадратными скобками, между которыми нет элементов:
work_days := [ ];Множество может быть объявлено типизированной константой, для чего в описании после знака равенства следует указать конструктор множества. Например:
const lett: set of ['а'..'я'] = ['а', 'е', 'и', 'о', 'у', 'ы', 'э', 'ю', 'я'];Конструируя множества, можно использовать и переменные при условии, что их текущие значения попадают в диапазон базового типа множества. Так, если ch1 и ch2 имеют тип char , то допустима следующая последовательность операторов:
ch1 := 'A'; ch2 := 'K'; chs := [ch1, ch2, 'M'];В результате получится множество [‘A’, ‘K’, ‘M’].
Вывод элементов множества
В Pascal элементы множества нельзя вводить и выводить. Для организации их ввода-вывода следует использовать вспомогательные переменные. В то же время можно использовать множества как элементы типизированных файлов.
type nums = 0..10; var a: set of nums; i: byte; begin a := [3, 0, 2]; for i := 0 to 10 do if i in a then writeln(i); end.0 2 3Операции над множествами
- присвоение
- объединение
- пересечение
- дополнение
- тождественность
- нетождественность
- содержится во множестве
- содержит множество
- принадлежность элемента множеству
Объединение, пересечение и разность множеств
Над множествами выполнимы объединение (+), пересечение (*) и разность (-).
Объединение двух множеств A и B (A + B) – это новое множество, состоящее из элементов, принадлежащих множеству A или B, либо тому и другому одновременно.
var chs1, chs2, chs3: set of char; begin chs1 := ['a', 'b', 'd']; chs2 := ['m', 'd', 'e']; chs3 := chs1 + chs2 + ['k', 'n']; end.Результат: chs3 = [‘a’, ‘b’, ‘d’, ‘m’, ‘e’, ‘k’, ‘n’].
Пересечение двух множеств A и B (A * B) – это множество, состоящее из элементов, одновременно принадлежащих множествам A и B.
chs3 := chs1 * chs2;Результат: chs3 = [‘d’] .
Разность (дополнение) множеств A и B (A — B) – это новое множество, состоящее из элементов множества A, не вошедших в множество B.
chs1 := ['a', 'e', 't']; chs2 := chs1 – ['e'] < ['a', 't'] >chs3 := ['m', 'n', 't'] – chs2
Используя операции объединения, пересечения и разности, можно добавлять элементы к множествам или удалять их.
Для вставки и удаления элементов при работе с множествами в Pascal введены две процедуры:
include(имя_множества, элемент) exclude(имя_множества, элемент)
Первая из них позволяет выполнить добавление одного элемента в указанное множество, а вторая удалить. Например:
include (chs1, 'g'); < аналогично chs1 + ['g'] >exclude (chs2, 'a');
Операции сравнения множеств
Над множествами можно выполнять четыре операции сравнения: =, <>, >=,
Два множества A и B равны (A = B), если каждый элемент множества A является элементом множества B и наоборот.
Два множества A и B не равны (A <> B), если они отличаются хотя бы одним элементом.
Другими словами, операции = и <> используются для проверки эквивалентности: два значения переменной типа set считаются равными, если они состоят из одних и тех же элементов.
[1, 3] = [3, 1] возвращает true,
[1..3] = [1, 2, 3] возвращает true,
[1] <> [2] возвращает true,
[1, 2, 3] = [1, 4, 3] возвращает false,
[red, blue] = [red, yellow] возвращает false.
Множество A является подмножеством множества B (A = A), если каждый элемент из A присутствует в B.
Пустое множество [ ] содержится во всех множествах, т.е. всегда [ ]
in — операция проверки принадлежности элемента множеству
Имеется возможность выяснить, принадлежит ли данный элемент некоторому множеству. Для этого служит операция in . Пусть A – множество элементов некоторого базового типа, а x – переменная этого типа. Тогда выражение x in A истинно, если значение x является элементом множества A .
red in [red, yellow] возвращает true ;
red in [blue, green] возвращает false .
Замечание 1. Чтобы проверить, является ли значение n цифрой, удобно использовать операцию in следующим образом:
if n in [0..9] then …Замечание 2. Результат операции in может быть неопределенным в некоторых случаях. Пусть:
a: set of 1..50; x: integer.Если присвоить x число, большее максимального значения 50 (например, x := 55 ), то в этом случае результат операции x in a не всегда false .
Все операции сравнения множеств, а также операция in возвращают логическое значение true или false .
Приоритеты операций над множествами
В сложных выражениях над множествами операции имеют следующие приоритеты:
Множества в языке Pascal
Множество это структурированный тип данных, представляющий собой набор взаимосвязанных по какому-либо признаку или группе признаков объектов, которые можно рассматривать как единое целое. Каждый объект в множестве называется элементом множества.
Все элементы множества должны принадлежать одному из порядковых типов, содержащему не более 256 значений. Этот тип называется базовым типом множества. Базовый тип задается диапазоном или перечислением.
Область значений типа множество — набор всевозможных подмножеств, составленных из элементов базового типа. В выражениях на языке Паскаль значения элементов множества указываются в квадратных скобках: [1,2,3,4], [‘а’,‘b’,’с’], [‘a’..’z’].
Если множество не имеет элементов, оно называется пустым и обозначается как []. Количество элементов множества называется его мощностью.
Множество может принимать все значения базового типа. Базовый тип не должен превышать 256 возможных значений. Поэтому базовым типом множества могут быть byte, char, boolean и производные от них типы.
Множество в памяти хранится как массив битов, в котором каждый бит указывает является ли элемент принадлежащим объявленному множеству или нет. Максимальное число элементов множества 256, а данные типа множество могут занимать не более 32 байт.
Число байтов, выделяемых для данных типа множество, вычисляется по формуле: ByteSize = (max div 8) — (min div 8) + 1, где max и min верхняя и нижняя границы базового типа данного множества.
Номер байта для конкретного элемента Е вычисляется по формуле: ByteNumber = (E div 8) — (min div 8), номер бита внутри этого байта по формуле: BitNumber = E mod 8
Не имеет значения порядок записи элементов множества внутри конструктора. Например, [1, 2, 3] и [3, 2, 1] это эквивалентные множества.
Каждый элемент в множестве учитывается только один раз. Поэтому множество [1, 2, 3, 4, 2, 3, 4, 5] эквивалентно [1..5].
Переменные множественного типа описываются так:
Var : set of ;
Var A, D : Set Of Byte; B : Set Of 'a'..'z'; C : Set Of Boolean;
Нельзя вводить значения во множественную переменную процедурой ввода и выводить процедурой вывода.
Множественная переменная может получить конкретное значение только в результате выполнения оператора присваивания:
:= ;
A : = [50, 100, 150, 200]; B : = ['m', 'n', 'k']; C : = [True, False]; D : = A;
Кроме того, выражения могут включать в себя операции над множествами.
Операции над множествами
Объединением двух множеств A и B называется множество, состоящее из элементов, входящих хотя бы в одно из множеств A или B. Знак операции объединения в Паскале «+».
1) [1, 2, 3, 4] + [3, 4, 5, 6] => [1, 2, 3, 4, 5, 6] 2) []+[‘a’..’z’]+[‘A’..’E’, ‘k’] => [‘A’..’E’, ‘a’..’z’] 3) [5 [false, true]
Пересечением двух множеств A и B называется множество, состоящее из элементов, одновременно входящих во множество A и во множество B.
Знак операции пересечения в Паскале «*»
1) [1, 2, 3, 4] * [3, 4, 5, 6] => [3, 4] 2) [‘a’..’z’]*[‘A’..’E’, ‘k’] => [‘k’] 3) [5 []
Разностью двух множеств A и B называется множество, состоящее из элементов множества A, не входящих во множество B.
1a) [1, 2, 3, 4] - [3, 4, 5, 6] => [1, 2] 1b) [3, 4, 5, 6] - [1, 2, 3, 4] => [5, 6] 2a) [‘a’..’z’]-[‘A’..’E’, ‘k’] => [‘a’..’j’, ‘i’..’z’] 2b) [‘A’..’E’, ‘k’] - [‘a’..’z’] => [‘A’..’E’] 3a) [5 [false] 3b) [true] - [5 [true]
Операция вхождения. Это операция, устанавливающая связь между множеством и скалярной величиной, тип которой совпадает с базовым типом множества. Если x такая скалярная величина, а M множество, то операция вхождения записывается так: x in M.
Результат логическая величина true, если значение x входит в множество M, и false в противном случае.
Например, 4 in [3, 4, 7, 9] –– true, 5 in [3, 4, 7, 9] –– false.
Используя данную операцию, можно не только работать с элементами множества, но и, даже если в решении задачи явно не используются множества, некоторые логические выражения можно записать более лаконично.
1) Натуральное число n является двухзначным. Вместо выражения (n >= 10) and (n можно записать n in [10..99] .
2) Символ c является русской буквой. Вместо выражения (c >= ‘А’) and (c =‘а’) and (c =‘р’) and (c пишем c in [‘А’.. ‘Я’, ‘а’.. ‘п’, ‘р’.. ‘я’] и т.д.
Добавить новый элемент в множество можно с использованием операции объединения. Например, a:= a+[5] Для этих же целей в Turbo Pascal 7.0 предназначена процедура Include: include (M, A) M – множество, A – переменная того же типа, что и элементы множества M. Тот же пример можно записать так: Include (a, 5)
Исключить элемент из множества можно с помощью операции «разность множеств». Например, a:= a-[5] Для этих же целей в Turbo Pascal 7.0 предназначена процедура Exclude: exclude (M, A) M – множество, A – переменная того же типа, что и элементы множества M. Тот же пример можно записать так: Exclude (a, 5)
Рассмотрим несколько примеров использования множеств при решении задач.
Задача 1. В городе имеется n высших учебных заведений, которые производят закупку компьютерной техники. Есть шесть компьютерных фирм: «Диалог», «Avicom», «Нэта», «Сервер», «Декада», «Dega.ru». Ответить на следующие вопросы:
1) в каких фирмах закупка производилась каждым из вузов?
2) в каких фирмах закупка производилась хотя бы одним из вузов?
3) в каких фирмах ни один из вузов не закупал компьютеры?
Решим задачу с использованием множеств. Для удобства дальнейших манипуляций в порядке следования занумеруем компьютерные фирмы, начиная с единицы. Занесём информации о месте закупок компьютеров каждым из вузов в отдельное множество.
Ответ на первый вопрос можно получить, выполнив пересечение всех таких множеств.
Ответ на второй вопрос – результат объединения множеств.
И, наконец, на последний – разность множества всех фирм и множества фирм, где хотя бы один вуз делал покупки.
program ex_set_1; type firma = set of 1..6; v = array[0..20] of firma; const f: array [1..6] of string[10] = ('Диалог', 'Avicom', 'Нэта', 'Сервер', 'Декада', 'Dega.ru'); procedure vvod(var a: firma); var i: byte; ans: 0..1; begin a:= []; for i := 1 to 6 do begin Write('Вуз покупал компьютеры в фирме ', f[i], ' (1 - да, 0 - нет)? '); ReadLn(ans); if ans = 1 then a:=a+[i] end; end; procedure Print(a : firma); var i: byte; begin for i := 1 to 6 do if i in a then write(f[i]:10); writeln end; procedure Rez1(a: v; n : byte; var b : firma); var i : byte; begin b := [1..6]; for i := 0 to n-1 do b := b * a[i]; end; procedure Rez2(a: v; n : byte; var b : firma); var i : byte; begin b := []; for i := 0 to n-1 do b := b + a[i]; end; var a: v; n, i : byte; c : firma; begin write('Сколько вузов делали закупку? '); readln(n); for i := 0 to n-1 do vvod(a[i]); Rez1(a, n, c); writeln('Каждый из вузов закупил компьютеры в фирмах: '); Print(c); Rez2(a, n, c); writeln('Хотя бы один из вузов закупил компьютеры в фирмах: '); Print(c); writeln('Ни один из вузов не закупил компьютеры в фирмах: '); Print([1..6]-c); end.
Задача 2. Сгенерировать n множеств (нумерацию начать с 1). Вывести элементы, которые входят во все множества с номерами, кратными трём, но не входят в первое множество.
program ex_set_2; type mn = set of byte; v = array[1..30] of mn; procedure vvod(var a: mn); var i, n, vsp: byte; begin a:= []; n := 1 +random(200); for i := 1 to n do begin vsp:= random(256); a:=a+[vsp] end; end; procedure Print(a : mn); var i: byte; begin for i := 0 to 255 do if i in a then write(i:4); writeln end; procedure Rez(a: v; n : byte; var b : mn); var i : byte; begin b := [0..255]; i:= 3; while iЗадача 3. Дана строка. Сохранить в ней только первые вхождения символов, удалив все остальные.
program ex_set_3; var m : set of char; s : string; i : byte; begin write('Введите строку: '); readln(s); m :=[]; i := 1; while i
- Что такое множество?
- Почему множество является структурированным типом данных?
- Как хранится множество в памяти ЭВМ? Какой максимальный объем оперативной памяти может быть отведен под хранение одного множества?
- Какие операции можно выполнять над множествами?
- Как добавить элемент в множество?
- Как исключить элемент из множества?
- Как вывести элементы множества? Как подсчистать количество элементов в множестве?
- Как может быть использована операция вхождения?
Множества
Множество представляет собой набор элементов одного типа. Элементы множества считаются неупорядоченными; каждый элемент может входить во множество не более одного раза. Тип множества описывается следующим образом:
В качестве базового может быть любой тип, в том числе строковый и классовый. Исключение составляют типы указателей.
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) .
Как организовать вывод элементов множества
Загрузка. Пожалуйста, подождите.Правила раздела!
1. Заголовок или название темы должно быть информативным !
Вывод множеств, Как вывести на экран множества 21.01.2006 16:35
2. Все тексты фрагментов программ должны помещаться в теги [code] . [/code] или [code=pas] . [/code].
3. Прежде чем задавать вопрос, см. "FAQ" и используйте 4. НЕ используйте форум для личного общения!
5. Самое главное - это раздел теоретический, т.е. никаких задач и программ (за исключением небольших фрагментов) - для этого есть отдельный раздел!
Группа: Пользователи
Сообщений: 17
Пол: ЖенскийРепутация: 0
for i:=1 to N do
if (i in m1) then write(i)или есть другой способ?
21.01.2006 16:41Нет. Только этот. Вывод множества - только полным перебором элементов и проверкой на наличие.
Кстати, и математически понятие "извлечение элемента из множества" не определено .
21.01.2006 16:49
Группа: Пользователи
Сообщений: 17
Пол: ЖенскийРепутация: 0
В продолжение темы.
Я так понимаю, что операция сравнения m1[1]>m1[2] со множеством m1 тоже не проходит? Как тогда можно подмнжество, состоящее только из гласных букв отсортировать по алфавиту? Я извиняюсь за настойчивость, но я раньше со множествами работала очень мало, а в faq тоже материла не много.