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

1

2 Множества Выход

3 Множества. Описание типа множество. Множество – это структурированный тип данных, представляющий собой набор взаимосвязанных по какому-либо признаку или группе признаков объектов, которые можно рассматривать как единое целое. Каждый объект в множестве называется элементом множества. Все элементы множества должны принадлежать одному из скалярных типов, кроме вещественного. Этот тип называется базовым типом множества. Базовый тип задается диапазоном или перечислением. Область значений типа множество – набор всевозможных подмножеств, составленных из элементов базового типа. В выражениях на Паскаль значения элементов множества указываются в квадратных скобках: [1,2,3,4], [a, b, c],[a..z]. Если множество не имеет элементов, оно называется пустым и обозначается как [ ]. Количество элементов называется его мощностью. Для описания множественного типа используется словосочетание SET OF (множество из …). Формат записи множественных типов: type = set of ; var : ;

4 Можно задать множественный тип и без предварительного описания: var : set of ; Пример: type Simply = set of a.. h; Namber = set of ; var Pr : Simply; N : Namber; Letter : set of char; {Определение множества без предварительного описания в разделе типов} В данном примере переменная Pr может принимать значения символов латинского алфавита от a до h; N – любое значение в диапазоне ; Letter – любой символ. Попытка присвоить другие значения вызовет программное прерывание. Количество элементов множества не должно превышать 256, соответственно номера значений базового типа должны находиться в диапазоне Контроль диапазонов осуществляется включением директивы {$R+}. Объем памяти, занимаемый одним элементом множества, составляет 1 бит. Объем памяти для переменной типа множество вычисляется по формуле: Объем памяти = (Max DIV 8) – (Min DIV 8) + 1, где Max и Min – верхняя и нижняя границы базового типа.

5 Операции над множествами. При работе с множествами допускается использование операций отношения «=», «», «>=», «

6 Операции над множествами. Операция «не равно» (). Два множества А и В считаются не равными, если они отличаются по мощности или по значению хотя бы одного элемента. Например: Значение АЗначение ВВыражениеРезультат [1,2,3][3,1,2,4]ABTrue [a..z][b..z]ABTrue ['c'..'t'][t..c]ABFalse

7 Операции над множествами. Операция «больше или равно» (>=). Операция «больше или равно» используется для определения принадлежности множеств. Результат операции А >= В равен True, если все элементы множества В содержаться в множестве А. В противном случае результат равен False. Например : Значение АЗначение ВВыражениеРезультат [1,2,3,4][2,3,4]A>=BTrue [a..z][b..t]A>=BTrue [z,x,c][z,x,c][c,x]A>=BTrue

8 Операции над множествами. Операция «меньше или равно» (

9 Операции над множествами. Операция in. Операция in используется для проверки принадлежности какого-либо значения указанному множеству. Обычно применяется в условных операторах. Значение Выражение Результат А=v If A in [a..n] then … False А=X1 If A in [X0,X1,X2,X3] then … True При использовании операции in проверяемое на принадлежность значение И множество в квадратных скобках не обязательно предварительно описывать в разделе описаний. Операция in позволяет эффективно и наглядно производить сложные проверки условий, заменяя иногда десятки других операций. Например, выражение if (a=1) or (a=2) or (a=4) or (a=5) or (a=6) then … можно заменить более коротким выражением if a in [1..6] then …. Отрицание. Часто операцию in пытаются записать с отрицанием: X NOT in M. Такая запись является ошибочной, так как две операции следует подряд; Правильная конструкция имеет вид NOT (X in M).

10 Операции над множествами. Объединение множеств (+). Объединением двух множеств является третье множество, содержащее элементы обоих множеств. Например, Значение АЗначение ВВыражениеРезультат [1,2,3][1,4,5]A+B[1,2,3,4,5] [А..D][E..Z]A+B[A..Z] [] A+B[]

11 Операции над множествами. Пересечение множеств (*). Пересечением двух множеств является третье множество, которое содержит элементы, входящие одновременно в оба множества. Например, Значение АЗначение ВВыражениеРезультат [1,2,3][1,4,2,5]A * B[1,2] [A..Z][B..R]A * B[B..R] [] A * B[]

12 Операции над множествами. Разность множеств (-). Разностью двух множеств является третье множество, которое содержит элементы первого множества, не входящие во второе множество. Например, Значение АЗначение ВВыражениеРезультат [1,2,3,4][3,4,1]A – B[2] [A..Z][D..Z]A – B[A..C] [X1,X2,X3, X4 ][X4,X1]A – B[X2,X3]

13 Операции над множествами. Результат операций над двумя множествами можно наглядно представить с помощью закрашенных прямоугольников: Использование в программе данных типа set дает ряд преимуществ: значительно упрощаются сложные операторы if, увеличивается степень наглядности программы и понимания решения задачи, экономится память, время компиляции и выполнения. Имеются и отрицательные моменты, основной из них – отсутствие в языке Паскаль средств ввода-вывода элементов множества, поэтому программист сам должен писать соответствующие процедуры.

14 Пример 1 решения задачи на Турбо Паскаль Задано множество целых положительных чисел от 1 до n. Создатьиз элементов этого множества такие подмножества, элементы которых удовлетворяют следующим условиям: Элементы подмножества не большие 10; Элементы подмножестав кратны 8; Элементы подмножества не кратны 3 и 6. Program mnoj; const n=100; Type mnog=set of 1..n; var mn1,mn2,mn3:mnog; k:integer; procedure pechat (z:mnog); {процедура печати подмножеств} var i:integer; begin for i:=1 to n do if i in z then write(i:4); writeln; end; Begin {задание начальных значений подмножеств (пустые)} mn1:=[];mn2:=[];mn3:=[]; for k:=1 to n do begin {создание подмножеств} if k

15 Пример 2 решения задачи на Турбо Паскаль Дан текст. Вывести на экран те буквы из текста, которые встречаются в данном тексте только один раз. program mnogestvo; uses crt; var mn1,mn2:set of char; i:integer;Stroka:string; Begin Clrscr; writeln(Введите строку '); readln(Stroka); mn1:=[];mn2:=[]; {Пустые множества} for i:=1 to length(Stroka) do begin if Stroka[i] in mn1 then mn2:=mn2+[Stroka[i]] {mn1 – содержит все встречающиеся буквы в строке} Else {mn2 – содержит парные буквы} mn1:=mn1+[Stroka[i]]; end; for i:=1 to length(Stroka) do begin if (not(Stroka[i] in mn2)) then {Вывод тех букв, которых нет в множестве mn2} writeln(Stroka[i]); end; end.

16 Задачи для самостоятельного решения 1. Написать программу, которая напечатает в порядке убывания все цифры, не входящие в данное натуральное десятичное число (для вводимого числа использовать тип longint). 2. Написать программу, которая найдет все простые числа из промежутка 1..n (использовать решето Эратосфена). 3. Дан небольшой текст на русском языке. Написать программу, которая напечатает в алфавитном порядке все согласные буквы, входящие в этот текст (по одному разу); 4. Написать программу, которая напечатает в алфавитном порядке все символы из заданного текста, которые встречаются в этом текcте не более одного раза.