Решение задачи на работу с множеством.

Цель работы: Познакомиться с понятием множества. Научиться использовать операции по работе с множеством в программах.

 

 

Теория.

 

Множества относятся к структурированным типам. Множество- совокупность различных элементов одинакового типа. В отличие от массива порядок перечисления элементов во множестве не имеет значения, и количество элементов заранее не определено. Количество элементов, входящих во множество, может меняться от 0 до 256. Значения множества задаются в квадратных скобках перечислением элементов через запятую. Например:

[] – пустое множество;

[2,3,7,11] – множество из целых чисел;

[‘a’, ‘c’, ‘f’] – множество из символов;

[1..10] – множество из элемента ограниченного типа;

[k..2*k] – элемент множества задается текущим значением переменной K.

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

<имя>: SET OF <тип компонент>;

<тип компонент> - является базовым типом, может быть простым типом, кроме вещественног.

Множество можно задавать 2-мя способами.

1) Сначала определить в разделе TYPE, затем в разделе VAR

2) Сразу определить в разделе VAR.

Значениями множества может быть только значение базового типа.

Операции над множествами

Для получения новых множественных значений используется 3 операции: объединение, пересечение и разность множеств.

1) Объединение: обозначается знаком «+». Объединением двух множеств является множество, составленное из элементов обоих множеств. [2,7,3]+[1,7,4,5,2]→[2,7,3,1,4,5]

2) Пересечением двух множеств является множество, состоящее из элементов, одновременно входящих в оба множества. Обозначается знаком «*».

[2,7,3]*[1,7,4,5,2] →[2,7]

3) Разностью двух множеств является множество,

состоящее из элементов 1-го множества, которые не являются

элементами второго множества. Обозначается знаком «-.».

[2,7,3] - [1,7,4,5,2] →[2,7]

C помощью множественных операций можно строить

Множественные выражения. Например:

[1,2,5,6,7] * [2..6] + [3,9] → [2,3,5,6,9]

К множествам применимы также операции отношения, которые приведены в таблице:

 

 

Операции отношения	Значения
True	False
A=B	А и В совпадают	В противном случае
A<>B	А и В не совпадают
A<=B	Элементы А принадлежат множеству В
A>=B	Все элементы множества В принадлежат множеству А
X IN A	Элемент Х входит в А Х- значение базового типа

 

 

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

M: Set of 1..10;

M: = [2,3,5,7]; {множеству М присваивается значение}

6 IN M→false {число 6 не входит во множество М}

[3,5,7]<=M→true {[3,5,7] принадлежит множеству М}

М=[1,2,3] → false {множество М не равно [1,2,3]}

[ ]<=M→true {пустое множество [ ] меньше множества М}

(7 in M) and ([7]<=M)→ true

Операцию проверки принадлежности IN удобно использовать для упрощения сложных условий в операторе IF. Например, оператор

IF (t=0) or (t=15) or (t=40) or (t=100) then ….

Может быть составлен более компактно и наглядно:

IF t in [0,15,40,100] then …

Пример программы.

Вводится последовательность букв латинского алфавита, оканчивающаяся точкой. Определить общее вхождение в эту последовательность букв f,a,y,e.

Program primer;

Var k: integer;

Litera: char;

Begin

K:=0

Read(litera);

While litera <> ‘.’ Do

Begin

If litera in [f,a,y,e] then k:=k+1;

Read(litera);

End;

Writeln(‘вхождение букв f,a,y,e в текст =’, K);

END.

 

Задание 1.

Вариант 1. Если в базовом типе n различных значений, то сколько различных значений в построенном на его основе множественном типе?

 

Вариант 2. Даны следующие описания переменных:

Type bits = set of 0..1;

Var x: bits;

y: set of (a,b,c);

z: set of ‘*’..’*’;

Ответить на следующие вопросы:

а) Каков базовый тип каждого из указанных множественных типов?

б) Сколько и какие значения может принимать каждая из переменных x, y, z?

 

Вариант 3. Даны следующие описания переменных:

Type день недели = (пн, вт, ср, чт, пт, сб, вс);

Описать множественный тип,включающий в себя множества из:

а) названия любых дней недели;

б) названия рабочих дней недели.

 

Вариант 4. Какие из следующих описаний не верны и почему?

Type точки = set of real;

байт = pasked Вариант [1..8] of 0..1;

данные = set of байт;

месяц = (ян, фев, маар, апр, май, июнь, авг, сен, окт, ноя, дек);

М1= set of месяц;

М2= set of июн..авг;

М3= set of дек..фев;

М4= set of (июн, июл, авг);

 

Вариант 5. Какие из следующих конструкций являются множествами (в смысле языка Паскаль), а какие нет и почему?

a) [9,6,3,0]; f) [true..false];

b) [2..3,5,7]; g) [2, sqrt(9)];

c) [1..15,4..18]; h) [‘=’,’>=’, ‘>’];

d) [‘*’, ‘*’]; i) [[], [5]];

e) [0..0]; j) [odd(7), 0<2].

Вариант 6. Вычислить значения отношений:

a) [2]<>[2,2,2];

b) [4,5,6] = [4..6];

c) [‘a’,’b’]=[‘b’,’a’];

d) [‘c’,’b’]=[‘c’..’b’];

e) [2,3,5,7]<=[1..9];

f) [3,6..8]<=[2..7,9];

g) []<=[‘0’..’9’];

h) ‘q’ in[‘a’..’z’];

i) trunc(3.9) in[1,3,5];

j) odd(4) in [];

k) [2]<[1..3];

 

Вариант 7. Вычислить значения выражений:

a) [1,3,5]+[2,4]; b) [1,3,5]*[2,4]; c) [1,3,5]-[2,4];

d) [1..6]+[3..8]; e) [1..6]*[3..8]; f) [1..6]-[3..8];

g) [2,4]+[1..5]; h) [2,4]*[1..5]; i) [2,4]-[1..5];

j) [ ]+[4]; k) [ ]*[4]; c) [ ]-[4];

 

Вариант 8. Вычислить значения выражений:

a) [2..13] * [3,13..60]+[4..10]-[5..15]*[6];

b) [2..10]-[4,6]-[2..12]*[8..15];

c) ([‘0’..’7’]+[‘2’..’9’])*([‘a’]+[‘z’]);

Вариант 9. Упростить (А и В - множества):

a) A*B-A; b) A-(A-B);

b) A*B-A; b) A-(A-B);

 

Вариант 10. Эквивалентны ли выражения:

a) P in [0,5,19] и (p=0) or (p=5) or (p=19)?

b) P in [20..50] и (p>=20) and (p<=50)?

 

Вариант 11. Даны следующие описания переменных:

Var p: set of 0..9; I,j: integer

Если i=3 и j=5 то, какое значение получит переменная P при выполнении следующего оператора присваивания:

a) p:=[i+3, j div 2, j:sqr(i)-3];

b) p:=[2*i..j];

c) p:=[I, j, 2*I, 2*j].

Вариант 12. Даны следующие описания переменных:

Var s: set of char;

c, d: char;

Переменной s присвоить:

а) пустое множество;

б) множество из строчных гласных латинских букв (a, e, I, o, u);

в) множество из всех цифр;

г) множество из литер,которые больше с, но меньше d (c<d)/

Вариант 13. Даны следующие описания переменных:

TYPE строка = pasked Вариант[1..100] of char;

Описать функцию счет(s), подсчитывающую общее количество цифр и знаков ‘+’, ‘-’, и ‘*’, входящих в строку s.

Контрольные вопросы

 

1. Операция принадлежности множеству?

2.Что будет являться разностью двух множеств?

3.Объединение множеств?

4.Как объявить множественный тип?

Лабораторная работа № 6