Как организовать вывод элементов множества

Множества в 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 .

Приоритеты операций над множествами

В сложных выражениях над множествами операции имеют следующие приоритеты:

Множества

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

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

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) .

Как организовать вывод элементов множества

Нет. Только этот. Вывод множества — только полным перебором элементов и проверкой на наличие.

Кстати, и математически понятие «извлечение элемента из множества» не определено .

21.01.2006 16:49

Группа: Пользователи
Сообщений: 17
Пол: Женский

Репутация: 0

В продолжение темы.
Я так понимаю, что операция сравнения m1[1]>m1[2] со множеством m1 тоже не проходит? Как тогда можно подмнжество, состоящее только из гласных букв отсортировать по алфавиту? Я извиняюсь за настойчивость, но я раньше со множествами работала очень мало, а в faq тоже материла не много.

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

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

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

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

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

Type SetByte = set of byte; SetChisla = set of 10 .. 20; Symbol = set of char; Month = (January, February, March, April, May, June, July, August, September, October, November, December); Season = set of Month; Var Letter, Digits, Sign : Symbol; 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 then writeln (‘S1 входит в S2’); if S1>=S2 then writeln (‘S2 входит в S1’);

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

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

2.

if Vacation then writeln (‘Правильно’) else writeln (‘Неправильно’);

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

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

1. Как сформировано множество М?
2. Как организован просмотр элементов этого множества?
3. Как организован просмотр делителей?
4. Как удаляется элемент множества?
5. Как организован вывод «просеянного» множества?

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

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

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

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

Пример 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; n2 := 2*n1; f := true; S2 := [ ]; for i := 1 to 4 do begin digit := n2 mod 10; 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.

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

1. П Ч Ё Л К А x 7 = ЖЖЖЖЖЖ
2. ТОРГ x Г = ГРОТ
3. ЛАДЬЯ+ЛАДЬЯ = ФЕРЗЬ
4. М3 = КУБ
5. СМ3 = КУБИК
6. МАТЕ * М = АТИКА
7. ПРОП * О = РЦИЯ
8. ПРОП : О = РЦИЯ
9. (М + О + С +К + В + А)4 = МОСКВА
10. ВЕТКА + ВЕТКА = ДЕРЕВО
11. САР = АТОВ
12. ПЛОМБА * 5 = АПЛОМБ
13. НИКЕЛЬ * 6 = ЕЛЬНИК
14. КВАНТ * 30 = ЖУРНАЛ
15. КАПЛЯ + КАПЛЯ + КАПЛЯ + = ОЗЕРКО
16. СОРОК * 5 = ДВЕСТИ
17. SIX * TWO = TWELVE
18. ДВЕСТИ * 5 = ТЫСЯЧА
19. НАТАША + ТОНЯ = СЁСТРЫ
20. БРА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 : 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 : begin Val(Str, Result, Code); Exit end; end; 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.

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

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

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