Конспект по теме: Множества в Паскале Учитель информатики: Батракова Л. В
| Вид материала | Конспект |
- Конспект по теме: Двумерные массивы Учитель информатики Батракова, 97.71kb.
- Конспект по теме: Одномерные массивы Учитель информатики Батракова, 270.14kb.
- Конспект по теме: введение в язык программирования Паскаль Учитель информатики Батракова, 271.14kb.
- Конспект лекций по курсу "Алгоритмические языки и программирование". Тема "Множества", 120.08kb.
- Учитель информатики Батракова, 79.15kb.
- Никогда не спрашивай, по ком звонит колокол… Руководители проекта, 84.79kb.
- Конспект бинарного урока по изобразительному искусству и информатике (5 класс), 96.06kb.
- Тема урока: Программирование ветвлений на Паскале, 61.32kb.
- Урок геометрии и информатики. Тема урока по учебному плану: Построение правильных многоугольников, 131.04kb.
- Т. С. Зайцева Программируем на Паскале Зайцева Татьяна Сергеевна, 34.82kb.
Конспект по теме: Множества в Паскале
Учитель информатики: Батракова Л.В.
____________________________________________________________________________________________
Множества
Определение: Множество – это произвольный тип, состоящий из ограниченного, неупорядоченного набора различных элементов одинакового (указанного заранее) базового типа.
В качестве базового типа могут выступать только перечислимый, ограниченный и тип char (поскольку число символов в Паскале ограничено – до 256).
Описание. Множество в Паскале описывается так:
Type <идентификатор типа>= set of <базовый тип>;
var <имя переменной> : <идентификатор типа>;
Здесь идентификатор типа и имя переменной – любое алфавитно–цифровое наименование (не более 8 символов), базовый тип – такой тип Паскаля, который допускает число элементов не более 256 – это максимальное число элементов во множестве Паскаля.
Так как во множестве может быть только до 256 элементов, поэтому типы ShortInt, Word, Integer, LongInt, хоть и перечислимые, базовыми для множеств быть не могут.
Элементы множества внутренне нумеруются, начиная с нуля.
Внутреннее представление множеств чрезвычайно компактно: один элемент расходует всего 1 бит памяти (равный 1, если такой элемент во множестве присутствует, и 0, если его во множестве нет). Поэтому множество на базе полного типа char будет занимать в памяти всего 32 байта.
Элементами множества могут быть только однотипные объекты. Скажем, только цифры или только буквы. Когда же требуется поместить одновременно и цифры, и буквы, то цифры обозначают символами (заключают их в апострофы).
Примеры:
Type T1=set of byte;
T2=set of char;
Color=(red, green, blue);
T3=set of color;
Var p1:T1;
p2:T2;
p3:T3;
p4: set of 1..3;
Константы множественного типа записываются в виде заключенной в квадратные скобки последовательности элементов или интервалов базового типа, разделенных запятыми, например:
['A', 'C'] [0, 2, 7] [3, 7, 11..14].
Константа вида [] означает пустое подмножество.
Множество включает в себя набор элементов базового типа, все подмножества данного множества, а также пустое подмножество. Если базовый тип, на котором строится множество, имеет К элементов, то число подмножеств, входящих в это множество, равно 2 в степени К.
Пусть имеется переменная p интервального типа:
var
p: 1..3;
Эта переменная может принимать три различных значения - либо 1, либо 2, либо 3. Переменная p4 множественного типа может принимать восемь различных значений:
[ ] [1,2]
[1] [1,3]
[2] [2,3]
[3] [1,2,3]
Порядок перечисления элементов базового типа в константах безразличен.
Один и тот же элемент можно упоминать в перечислении сколько угодно раз, во множество он все равно войдет в единственном числе. Множества ['a','b','c'] и ['a','c','c','a','b','a'] в Паскале одинаковы.
Элементами множеств могут быть константы и переменные базового типа, и даже выражения, тип результата для которых совпадает с базовым типом множества.
Инициализация величин множественного типа производится с помощью типизированных констант:
const seLit: Set of 'A'..'D'= [];
Так как каждому значению множественного типа в памяти ЭВМ соответствует один двоичный разряд, то выполнение операций происходит над битовыми строками данных.
Например, множество
['A','B','C','D']
представлено в памяти ЭВМ битовой строкой
1 1 1 1.
Подмножества этого множества представлены строками:
['A','B','D'] 1 1 0 1
['B','C'] 0 1 1 0
['D'] 0 0 0 1
Операции, определенные над множествами
Множества сопоставимы, если они построены на одном и том же базовом типе.
Все операции, которые мы будем рассматривать, работают только для сопоставимых операндов.
- Операция присваивания (оператор :=)
const
NMAX = 100;
var
x : byte;
s : Set of byte;
...
x:=3;
s:=[];
s:=[1,2,x,NMAX];
s:=[x+1,x+2,x+3];
- Проверка на равенство (оператор =)
Результат будет равен TRUE, если множества состоят из одинаковых элементов, и равен FALSE в противном случае.
| Результат - истина | Результат - ложь |
| [1,2,3] = [1,3,2] | [1,2] = [1] |
| [5,x] = [x,5] | [5,x] = [5,x+1] |
| [] = [] | [] = [1] |
var
S1, S2, S3: Set of char;
...
S1:=['a','b','c','d'];
S2:=['c','d','b'];
S3:=['a','b','d','b','c','a'];
if S1=S2 then... {результат FALSE, оператор не выполнится}
if S1=S3 then... {результат TRUE, оператор выполнится}
-
Проверка на неравенство (оператор < >)
Результат будет равен TRUE, если во множествах не совпадает хотя бы один элемент.
| Результат - истина | Результат - ложь |
| [1,2] <> [1] | [1,2,3] <> [1,3,2] |
| [5,x] <> [5,x+1] | [5,x] <> [x,5] |
Для предыдущего примера
if S1<>S2 then... {результат TRUE, оператор выполнится}
if S1<>S3 then... {результат FALSE, оператор не выполнится}
-
Проверка на подмножество (оператор <=)
Для (S1<=S2) результат будет равен TRUE, если все элементы S1 содержатся в S2.
| Результат - истина | Результат - ложь |
| ['a','b'] <= ['a'..'z'] | ['0'..'9'] <= ['a'..'z'] |
| [] <= S | S <= [] |
if S1<=S2 then... {результат FALSE}
if S2<=S1 then... {результат TRUE}
Проверка на надмножество (оператор >=)
Для (S1>=S2) результат будет равен TRUE, если все элементы S2 присутствуют в S1.
| Результат - истина | Результат - ложь |
| [] <= S | [] >= S |
| [x,x+1] >= [x+1] | [1..3] >= [0..4] |
if S1>=S2 then... {результат TRUE}
if S2>=S1 then... {результат FALSE}
Естественно, если S1<=S2, то S2>=S1.
-
Проверка, входит ли элемент во множество (оператор in)
Для выражения E in S результат будет равен TRUE, если значение Е имеет базовый тип множества S и входит в него.
| Результат - истина | Результат - ложь |
| 5 in [0..5] | x in [x-1,x-2] |
| [] in [0..5] | x in [] |
Var S: Set of char;
ch1, ch2: char;
i: byte;
...
S:=['h','e','l','l','o'];
ch1:='e';
ch2:='x';
i:=0;
if ch1 in S then... {результат TRUE}
if ch2 in S then... {результат FALSE}
if i in S then... {ошибка! тип i не совпадает с базовым типом множества}
Можно проверить и присутствие элемента в явно заданном множестве:
if ch in ['a'..'z'];
Так же распишем проверку того, что значение попадает в диапазон:
if ch in ['a'..'x','A'..'X'] then ...
if m in [100..200] then ...
Эта операция - самая употребляемая в программировании из всех операций над множествами. В самом деле, нам не так уж часто приходится объединять математические множества, зато проверить, является ли введенная буква гласной или четным двузначным числом - задачи очень распространенные.
Например, пусть нам необходимо подсчитать количество русских гласных в заданной строке. Эта функция может выглядеть так:
function CountGlasn1 (str: string) : word;
var
Glas: Set of char;
n: word;
i: byte;
begin
Glas:=['а','о','у','ы','и','э','е','ё','ю','я'];
n:=0;
for i:=1 to length(str) do
if str[i] in Glas then
n:=n+1;
CountGlasn1:=n;
end;
Множество используется в тексте всего один раз. Поэтому мы можем не вводить переменную-множество, а записать его в явном виде.
function CountGlasn2 (str: string) : word;
var
n: word;
i: byte;
begin
n:=0;
for i:=1 to length(str) do
if str[i] in ['а','о','у','ы','и','э','е','ё','ю','я'] then
n:=n+1;
CountGlasn2:=n;
end;
-
Объединение множеств (оператор +)
Результат операции (A + B) - множество, которое состоит из всех элементов множества A и всех элементов множества B. Дубликаты значений, естественно, уничтожатся.
| Операция | Результат |
| [1,2,3,4,4] + [3,4,4,5,6] | [1,2,3,4,5,6] или [1..6] |
| ['1','2'] + ['8','9'] | ['1','2','8','9'] |
| [x] + [] | [x] |
| [x] + [x+1] + [x+2] | [x..x+2] |
S1:=[1,2];
S2:=[2,3,4];
S3 := S1+S2; {Теперь S3=[1,2,3,4]}
Отсюда мы легко можем вывести простые правила:
S+[]=S {S - любое, [] - пустое множество}
S+S=S
если A<=B, то A+B=B
если A>=B, то A+B=A
-
Разность множеств (оператор -)
Результат операции (A - B) - множество, которое состоит из тех элементов, которые входят в множество A, но не входят во множество B.
| Операция | Результат |
| [1,2,3,4,4] - [3,4,4,5,6] | [1,2] |
| ['1','2'] - ['8','9'] | ['1','2'] |
| [x] - [] | [x] |
| [] - [x] | [] |
S1:=[1,2];
S2:=[2,3,4];
S3:=S1-S2; {теперь S3=[1]}
S3:=S2-S1; {теперь S3=[3,4]}
Выведем и для этой операции несколько правил:
S-[]=S
S-S=[]
если A<=B, то A-B=[]
если A>=B, то B-A=[]
Результат "многоместных" разностей зависит от порядка вычислений, который устанавливается компилятором. Поэтому использовать такие выражения нежелательно.
-
Пересечение множеств (оператор *)
Результат операции (A * B) - множество, состоящее из тех элементов, которые входят и в множество A, и в множество B.
| Операция | Результат |
| [1,2,3,4,4] * [3,4,4,5,6] | [3,4] |
| ['1','2'] * ['8','9'] | [] |
| [A] * [A,B] * [A,B,C] | [A] |
S1:=[1,2];
S2:=[2,3,4];
S3:=S1*S2; {теперь S3=[2]}
Правила, которые можно вывести для пересечения множеств:
S*[]=[]
S*S=S
если A<=B, то A*B=A
если A>=B, то A*B=B
Примеры:
Пример 1. Вывести все различные символы заданной строки, отсортировав их по кодам.
program pr1;
var
s: string;
procedure PrintSymbols (str: string);
var
i: byte;
symb: Set of char;
begin
symb:=[];
{набираем символы во множество}
for i:=1 to length(str) do
symb:=symb+[str[i]];
{печатаем полученные символы}
for i:=0 to 255 do
if chr(i) in symb then
write(chr(i),' ');
writeln;
end;
begin
writeln('Программа печатает все различные символы строки,');
writeln('упорядочивая их по ASCII-кодам.');
writeln('Введите исходную строку: '); readln(s);
PrintSymbols(s);
end.
Пример 2. Подсчитать, сколько раз встречаются в данном тексте указанные буквы [a,b,c] и указанные цифры [2,3,4,5].
program pr2;
var sumb,sumc,i:integer;
text:string;
bukwy,cifry:set of char;
lit:char;
begin
bukwy:=['a','b','c' ]; cifry:=['2','3','4','5' ];
sumc:=0; sumb:=0;
writeln(' введи текст ' ); readln (text);
for i:= 1 to length(text) do
begin
lit:=text[i];
if lit in bukwy then sumb:=sumb+1;
if lit in cifry then sumc:=sumc+1;
end;
writeln ('букв a,b,c ',sumb);writeln(' цифр 2,3,4,5 ', sumc);
end.
Пример 3. Из множества целых чисел от 1 до 20 выделить во множество N2 числа, кратные 2, во множество N3 – кратные 3, во множество N6 – кратные 6 (т.е. кратные и 2 и 3), во множество N23 – кратные либо 2, либо 3.
program pr3;
const n=20;
var n2,n3,n6,n23: set of 1..n;
k: integer;
begin
n2:=[ ]; n3:=[ ];
for k:=1 to n do
begin
if k mod 2 = 0 then n2:=n2+[k];
if k mod 3 = 0 then n3:=n3+[k]
end;
n6:=n2*n3;
n23:=n2+n3;
{ вывод результатов}
writeln ; writeln(' на 6 делятся : ' );
for k:=1 to n do
if k in n6 then write(' ', k);
writeln; writeln(' на 2 или на 3 делятся : ' );
for k:=1 to n do
if k in n23 then write (' ', k )
end.
Пример 4. Составить программу, которая вырабатывает и выводит на экран дисплея наборы случайных чисел для игры в "Спортлото 5 из 36". Для заполнения каждой карточки спортлото необходимо получить набор из пяти псевдослучайных чисел. К этим числам предъявляются два требования:
-числа должны находиться в диапазоне 1..36;
-числа не должны повторяться.
Program pr4;
var
nb, k: Set of 1..36;
kol, l, i, n: Integer;
begin
Randomize;
WriteLn('ВВЕДИ kol');
ReadLn(kol);
nb:=[1..36];
for i:=1 to kol do
begin
k:=[];
for l:=1 to 5 do
begin
repeat
n:=Random(36)
until (n in nb) and not (n in k);
k:=k+[n];
Write(n:4)
end;
WriteLn
end
end.
Плюсы и минусы использования множеств
Достоинства множеств:
- мы получаем гибкий, удобный для анализа механизм представления наборов значений;
- множества очень компактно располагаются в памяти;
- множества Паскаля с набором операций над ними - это готовая структура для работы с математическими конечными множествами;
- множества удобны для накапливания произвольно поступающих значений.
Последнее утверждение хочется пояснить. Пусть требуется напечатать все различные символы заданной строки, отсортировав их по кодам. В этом случае, набирая символы из строки во множество, мы сразу получим и сортировку, и удаление дубликатов.
Недостатки множеств:
- множество нельзя вывести на экран;
- множество можно вводить только по элементам.
Контрольные вопросы
1. Что называется множеством в Паскале и как оно описывается?
2. Какие операции допустимы со множествами?
3. Как задаются значения (элементы) множества и сколько (максимально) их может быть?
4. Сколько места в памяти занимает один элемент множества?
5. Какие операции определены над множествами?
Практические задания
1. Пусть дан массив типа char (состоящий из произвольных символов). Подсчитать в нем общее число цифр и знаков "+" и "–".
2. Дан текст из малых латинских букв. Напечатать первые вхождения букв в текст, сохраняя их исходный взаимный порядок.
3. Дан текст из цифр и малых латинских букв. Определить, каких букв – гласных (a,e,i,o,u) или согласных – больше в этом тексте.
4. Дано натуральное число N (N<=32767). Представляя его в виде множества цифр, подсчитать количество различных цифр в записи этого числа.
5. Дано натуральное число N (N<=32767). Представляя его в виде множества цифр, напечатать в возрастающем порядке все цифры, не входящие в запись этого числа.
6. Дан текст из малых латинских букв. Напечатать:
а) все буквы, входящие в текст не менее двух раз,
б) все буквы, входящие в текст по одному разу,
в) в алфавитном порядке напечатать (по разу) все буквы, входящие в этот текст.
7. Дан текст из малых русских букв, состоящий из нескольких слов. Напечатать:
а) все гласные буквы, которые входят в каждое слово,
б) все согласные буквы, которые не входят ни в одно слово,