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

Тема: Решение задач на множества.

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

Теория .

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

состоящее из элементов 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]

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

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

M:Setof 1..10;

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

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

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

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

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

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

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

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

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

IFtin [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. Вычислить значения отношений :

[2]<>[2,2,2];
[4,5,6] = [4..6];
[‘a’,’b’]=[‘b’,’a’];
[‘c’,’b’]=[‘c’..’b’];
[2,3,5,7]<=[1..9];
[3,6..8]<=[2..7,9];

Вариант 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. Вычислить значения выражений :

[2..13] * [3,13..60]+[4..10]-[5..15]*[6];
[2..10]-[4,6]-[2..12]*[8..15];
([‘0’..’7’]+[‘2’..’9’])*([‘a’]+[‘z’]);

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

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

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

P in [0,5,19] и (p=0) or (p=5) or (p=19) ?
Pin [20..50] и (p>=20) and (p<=50) ?

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

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

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

p:=[i+3, j div 2, j:sqr(i)-3];
p:=[2*i..j];
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.

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

Операция принадлежности множеству ?
2.Что будет являться разностью двух множеств ?
3.Объединение множеств ?
4.Как объявить множественный тип ?