Рассмотрим работу с множествами на следующих примерах.
Государственное образовательное учреждение среднего профессионального образования
ВОРКУТИНСКИЙ ГОРНО-ЭКОНОМИЧЕСКИЙ КОЛЛЕДЖ
РАССМОТРЕНО УТВЕРЖДАЮ:
На заседании цикловой комиссии Зам. директора по УВР
«___»_____________2008 г. ______________З.Г. Штокалюк
Председатель цикловой комиссии «___»___________2008 г.
____________ О.В. Гармаш
МЕТОДИЧЕСКИЕ УКАЗАНИЯ
к лабораторной работе № 10
Тема:
«Работа с данными типа множество»
Дисциплина: «Программирование на языке высокого уровня»
для студентов специальности 230101
Разработал преподаватель Баев А.В.
2008 г.
Лабораторная работа №10
Работа с данными типа множество
Цель работы:
1. Разработка программ с использованием данных типа Множество.
Краткие сведения из теории:
Множества в Паскале, их описание. Операции над множествами
Под множеством в языке Паскаль понимают ограниченный неупорядоченный набор различных элементов одинакового типа, логически связанных друг с другом. Количество элементов, входящих в множество, может меняться в пределах от 0 до 255. Множество, не содержащее элементов, называется пустым. Множество имеет имя. Тип элементов, входящих в множество, называется базовым. В качестве базового типа можно использовать любой порядковый тип, кроме Word, Integer, Longint.
Множества должны быть объявлены либо в разделе Var, либо в разделах Type и Var, одновременно:
Var Имя множества:Set of базовый тип;
Или
Type Имя типа=Set of базовый тип;
Var Имя множества:Имя типа;
Например:
Type
TM=Set of 1..100;
TS=Set of 'a'..'z';
Var Mch:TM; {Множество целых чисел от 1 до 100}
MSym:TS; {Множество строчных латинских букв}
M: Set of 1..10; {Множество целых чисел от 1 до 10}
Значения переменных множества задаются в разделе операторов с помощью конструкторамножества, который представляет собой список элементов базового типа, заключенный в квадратные скобки.
Например:
Var M1,M2,M3:set of 1..99;
Begin . . .
M1:=[]; { Множество пустое}
M2:=[1,3,5,7,9]; { Множество нечетных чисел в первом десятке}
M3:=[2,4,6,8]; { Множество четных чисел в первом десятке}
. . .
End.
В качестве элементов в изображении множеств допускается использовать константы и выражения, тип которых совместим с базовым типом.
Типизированная константа - множество задается в виде правильного конструктора множества, например:
Type
Type_month=(Jn,Feb,Mar,Apr,May,Jun,Jul,Aug,Sep,Oct,Nov,Dec);
TDays=Set of 1..31;
Tmonth=Set of 1..12;
Tsym=Set of 'A'..'Z';
Tmno=Set of Type_month;
Const
SymMno:Tsym=['A','E','I','O','U']; {подмножество гласных букв}
DaysMno:TDays=[1,8,15,22,29]; {подмножество выходных дней месяца}
Spring_Mes:Tmonth=[3,4,5]; {подмножество весенних месяцев года}
Spring_Month:Tmno=[Mar,Apr,May]; {то же, что и предыдущее}
Над множествами определены следующие операции:
1) * - пересечение множеств: результат содержит элементы, общие для обоих множеств. Например: пусть имеется описание:
Var S1,S2,S3,S4,S5:Set of 1..10;
Begin
S1:=[1,3,4,6];
S2:=[2,4,5,1];
S3:=S1*S2; - в S3 будет содержаться [1,4].
2) +- объединение множеств : результат содержит элементы первого множества, дополненные недостающими элементами из второго множества:
S4:=S1+S2; - в S4 будет содержаться [1,3,4,6,2,5].
3) - -разность множеств: результат содержит элементы из первого множества, которые не принадлежат второму:
S5:=S1-S2; - в S5 будет содержаться [3,6].
4) =- проверка эквивалентности (или равенства): возвращает TRUE, если оба множества эквивалентны, т.е. содержат все одинаковые элементы.
5) <>- проверка неэквивалентности (или неравенства): возвращает TRUE, если оба множества неэквивалентны, т.е. содержат неодинаковые элементы.
6) <= - проверка вхождения: возвращает TRUE, если первое множество включено во второе (т.е. все элементы первого множества присутствуют также и во втором).
7) >= - проверка вхождения: возвращает TRUE, если второе множество включено в первое.
8) IN- проверка принадлежности элемента множеству. Эта операция возвращает результат TRUE, если элемент (или выражение), стоящий слева принадлежит множеству, указанному справа.
Дополнительно к этим операциям можно использовать две процедуры:
Include- включает новый элемент во множество: Include(M,elem);
где М - множество элементов некоторого базового типа, а elem - элемент того же типа, который необходимо включить в множество М.
Exclude -исключает элемент из множества: Exclude(M,elem).
В отличие от операций "+" и "-", реализующих аналогичные действия над двумя множествами, эти процедуры оптимизированы для работыс одиночными элементами множества и поэтому отличаются высокой скоростью выполнения.
Основным достоинством использования множеств является экономия памяти: внутренне устройство множества таково, что каждому его элементу ставится в соответствие один двоичный разряд (один бит). Если элемент включен в множество, то соотвествующий разряд имеет значение 1, в противном случае - 0. Минимальной единицей памяти является 1 байт, содержащий 8 бит, поэтому для хранения множества мощностью 256 элементов выделяется память 32 смежных байта.
Рассмотрим работу с множествами на следующих примерах.
Пример 1.Из множества целых чисел от 1 до 20 выделить:
1) множество чисел, делящихся на 2 и 3 одновременно;
2) множество чисел, делящихся на 2 или на 3.
Первая задача соответствует нахождению пересечения множеств чисел, одно из которых содержит числа, делящиеся на 2, а другое на 3. Вторая - объединению этих двух множеств.
Обозначим множество чисел, делящихся на 2 через М2; множество чисел, делящихся на 3 через М3; множество чисел, делящихся на 2 и 3 через М2and3; множество чисел, делящихся на 2 или 3 через М2or3.
ProgramExample_1;
Type TM=Set of 1..20; {Описание типа множества целых чисел от 1 до 20}
VarM2,M3,M2and3,M2or3:TM; {Описание множеств}
k:1..20; {Описание переменной}
Begin
M2:=[]; M3:=[]; {Пустые множества}
for k:=1 to 20 do
begin
if k mod 2 = 0 then Include(M2,k); {Включение элемента делящегося на 2 в множество М2}
if k mod 3 = 0 then Include(M3,k); { Включение элемента делящегося на 3 в множество М3}
end;
M2and3:=M2*M3; {Пересечение двух множеств}
M2or3:=M2+M3; {Объединение двух множеств}
write(' На 2 и 3 делятся числа: ');
for k:=1 to 20 do { Цикл для опеределения элементов в множестве}
if k in M2and3 then write(k:3); { вывод элементов делящихся на 6}
writeln; {Переход на новую строку экрана}
write(' На 2 или 3 делятся числа: ');
for k:=1 to 20 do
if k in M2or3 then write(k:3); readln; {Остановка для просмотра}
End.
Пример 2.«Мешанина». Если взять то общее, что есть у боба с ложкой, добавить кота и поместить в тепло, то получится муравей. Так ли это? Состоит ли муравей из кота?
ProgramExample_2;
Varyl, y2, уЗ, у4, х: Set Of Char;
s: Char;
Begin
yl: = [' б ' 'о', 'б']; у2: = ['л' , 'о', 'ж', 'к', 'а'];
уЗ:=['к', 'о', 'т']; у4:=['т', 'е', 'п', 'л', 'о'];
x:=(yl*y2)+y3-y4;
Writeln('множество х'); {вывод множества х}
For s:='a' To 'я' Do
If s In x Then Write(s);
Writeln;
If y3<=x Then Write('муравей состоит из кота') {проверка: состоит ли муравей из кота}
Else Write('муравей не состоит из кота');
End.
Пример 3.Дано натуральное число п. Составить программу, печатающую все цифры, не входящие в десятичную запись данного натурального числа в порядке возрастания.
ProgramExample_3;
Typemn = Set Of 0..9;
Vars: mn;
n: Longint;
1,k: Integer;
Begin
Writeln ('введите число n'); Readln(n);
s:=[ ];
While n<>0 Do {формирование множества цифр десятичной записи натурального числа}
Begin
k:=n Mod 10;
n:=n Div 10;
If Not (к In s) Then s:=s+[k];
End;
For k:=0 To 9 Do
If Not (k In s) Then Write(k:2); {вывод цифр в порядке возрастания}
Readln;
End.
Пример 4.«Решето Эратосфена». Составить программу поиска простых чисел в числовом промежутке [1...п]. Число п вводится с клавиатуры.
Решение. Простым числом называется число, которое не имеет других делителей, кроме единицы и самого этого числа. Для решения этой задачи воспользуемся методом «решета Эратосфена», идея которого заключается в следующем: сформируем множество М, в которое поместим все числа заданного промежутка. Затем последовательно будем удалять из него элементы, кратные 2, 3, 4 и так далее, до [n/2] (целая часть числа), кроме самих этих чисел. После такого «просеивания» в множестве М останутся только простые числа.
ProgramExample_4;
Varm: Set Of Byte;
i,k,n: Integer;
Begin
Writeln (' введите размер промежутка (до 255) '); Readln(n);
m:=[2..n]; {начальное значение}
For k:=2 To n Div 2 Do {перебираем все делители }
For i:=2 To n Do
If (i Mod k=0) And (i<>k) Then m:=m-[i];
{если число кратно делителю и отлично от него, то удаляем его}
For i:=l To n Do
If i In m Then Write(i:3); {распечатаем оставшиеся элементы }
Readln;
End.
Пример 5.Ребус.
Решение. Каждая буква — это цифра, разным буквам соответствуют разные цифры. Необходимо заменить буквы цифрами так, чтобы получилось верное равенство.
МУХА +
МУХА
СЛОН
Для решения этой задачи используется метод перебора с возвратом. Используем множество S1 для хранения цифр слова МУХА, причем будем вносить в него цифры последовательно, учитывая уже внесенные цифры. Начальное значение S1 — пусто. После выбора всех цифр первого слова создаем его числовой эквивалент и числовой образ слова СЛОН. Выделяем цифры СЛОНа (множество S2) и если слова состоят из разных цифр (то есть пересечение S1 и S2 пустое) и все цифры СЛОНа разные (то есть пересечение множеств цифр тоже пустое), то выводим решение на экран. А сейчас идет возврат — удаляем из множества S1 последнюю внесенную цифру и пытаемся выбрать еще одно ее значение. Таким образом, мы перебираем все возможные варианты и выводим на экран только те, которые удовлетворяют равенству.
Заметим, что значение буквы «М» в слове МУХА может иметь значения от 1 до 4, а буква «А» в этом же слове не может быть равна 0.
ProgramExample_5;
Typemn = Set Of 0..9;
Varm,y,x,a: 0..9; {цифры числа МУХА}
nl,n2: Integer; {числа МУХА и СЛОН}
al,a2,a3,a4: 0..9; {цифры числа СЛОН}
s1, s2:mn; {для хранения цифр каждого из чисел}
ProcedurePrint(x,у:Integer); {вывод решения в виде ребуса}
Begin
Writeln(x:5) ;
Writeln(' + ') ;
Writeln(x:5) ;
Writeln (' ')
Writeln(у:5);
End;
Begin
sl:=[ ];s2:=[ ];
For m:=l To 4 Do
Begin
sl:=sl + [m]; {заносим первую использованную цифру}
For y:=0 To 9 Do
If Not (y In si)
Then {если эта цифра не была еще взята, то добавляем ее во множество цифр числа МУХА
и выбираем цифру для следующей буквы}
Begin
sl:=sl+[y];
For x:=0 To 9 Do
If Not (x In si)
Then
Begin
sl:= si + [x];
For a:=l To 9 Do
If Not (a In si)
Then
Begin
sl:=sl+[a];
nl:=1000*m+100*y+10*x+a; {число для слова МУХА}
n2:=2*nl; {число для слова СЛОН}
al:=n2 Div 1000; {выделяем цифры СЛОНа}
a2:=n2 Div 100 Mod 10;
a3:=n2 Div 10 Mod 10;
a4:=n2 Mod 10;
s2:=[al,а2,аЗ,а4]; {множество цифр СЛОНа}
{если слова состоят из разных цифр и в слове СЛОН нет одинаковых, то выводим решение ребуса на экран}
If (sl*s2=[ ] ) And ( [al]*[a2]*[a3]*[a4]=[ ] )
Then Print (nl,n2);
sl:=sl-[a]; {удаляем занесенную цифру}
End;
sl:=sl-[x];
End;
sl:=sl-[y];
End;
si:=sl-[m];
End;
Readln;
End.