Математика
Паскаль
{'A','K','B','L'}
{1,2,...,N}
['A','K','B','L']
пустое множество []
[1..N]
ТЕМА: "МНОЖЕСТВА".
Ход урока.
ТЕОРЕТИЧЕСКИЙ МАТЕРИАЛ К УРОКУ.
Наряду с числом множество является фундаментальным математическим понятием. Паскаль - один из немногих алгоритмических языков, который имеет встроенные средства для работы с множествами.
В математике под множеством понимается некоторый набор элементов. Например, множество фигур на плоскости (прямоугольник, круг, ромб, квадрат). В математике рассматриваются конечные и бесконечные множества, состоящие из произвольных элементов. В Паскале множества всегда конечные, причем состоят из небольшого числа элементов (в Турбо Паскале - до 255).
Постоянные множества и в математике и в Паскале задаются перечнем их элементов.
|
Математика |
Паскаль |
| {1,2,3} {'A','K','B','L'} {1,2,...,N} |
[1,2,3] ['A','K','B','L'] пустое множество [] [1..N] |
В квадратных скобках могут находиться не только константы, но любые выражения типа элементов множества, например, [2++x,8-3].
К множествам применимы следующие операции.
объединение С=А
В
пересечение С=А
В
разность С=А\В
Под множеством в языке паскаль понимают ограниченный, неупорядоченный набор различных элементов одинакового типа. Можно, например говорить о множестве радиодеталей, транспортных средств, станков и т.д. всему множеству в целом дается имя. Тип элементов, входящих в множество, называется базовым. В качестве базового типа можно использовать простые типы: стандартный (кроме действительного), перечисляемый и ограниченный. Множества должны быть объявлены в var или type.
var имя множества: set of базовый элемент;
Например:
var god: set of 1880..2000;
c: set of char;
type имя типа= set of базовый элемент;
var имя множества:
имя типа;
set of 'a'..'z' - множество прописных английских букв;
set of
1..100 - множество целых чисел от 1 до 100;
set of (winter, spring, summer,
outumn) - множество времен года
set of char - множество всех
символов.
В языке паскаль имеются следующие операции над множествами:
+ - объединение
множеств;
* - пересечение множеств;
- - вычитание множеств;
=,<>
- проверка множеств на равенство, неравенство;
<=,>= - проверка
множеств на включение;
in - проверка на принадлежность элемента множеству ( c
in a).
Все значения множества представляются в памяти последовательностями битов одинаковой длины. За каждое значение базового типа "отвечает" один бит. Если множество содержит некоторый элемент, в "ответственном" за него бите хранится 1, если не содержит - хранится 0.
Пример: var x: set of 1..15;
Внутреннее представление X
x:=[];
000000000000000>
x:=[2,3,5]; 011010000000000>
x:=[1..15];
111111111111111>
Операции над множествами сводятся к поразрядным логическим операциям над последовательностями битов, пример, объединение множеств выполняется путем поразрядного логического сложения битов:
x:=[2,3,5];
011010000000000>
y:=[3,5,7,8]; 001010110000000>
z:=x+y;
011010110000000>
Поразрядные документы
входят в набор команд процессора ЭВМ, поэтому выполняется быстро.
Средства
работы с множествами позволяют в некоторых случаях сократить программы и сделать
их более наглядными и эффективными за счет уменьшения числа проверок.
Задача №1. Имеются три множества символьного типа, которые заданы своими конструкторами: Y1=['A','B','D','R','M']; Y2=['R','A','H','D']; Y3=['A','R']; Сформировать новое множество: X=(Y1*Y2)+(Y1\Y2). Вывести на печать полученное множество x, проверить, включено ли y3 во множество x. (файл MNOG1.PAS)
Решение.
program mnog1;
var
y1,y2,y3,x: set of
char;
c:char;
begin
y1:=['a','b','d','r','m'];
y2:=['r','a','h','d'];
y3:=['a','r'];
x:=(y1*y2)+(y1-y2);
write('множество
x=');
for c:='a' to 'r' do
if c in x then write(c);
writeln;
if
y3<=x then write('y3 включено в x')
else write('y3 не включено в
x');
end.
Задача №2. Из множества целых чисел 1..20 выделить: множество чисел, делящихся без остатка на 6; множество чисел, делящихся без остатка или на 2, или на 3. (файл MNOG2.PAS).
Решение.
program mnog2;
const
n=20;
var n2,n3,n6,n23: SET OF 1..N;
k:1..N;
begin
n2:=[ ]; n3:=[
];
for k:=2 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('на 6
делятся числа:');
for k:=1 to n do
if k in n6 then
write(k:3);
writeln;
writeln('на 2 или на 3 делятся числа:');
for k:=1
to n do
if k in n23 then write(k:3);
end.
Задача №3. Дан текст (например, 5a7233111bge2257cde.) Признаком конца текста является точка. Вывести на экран цифры, которые встречаются в тексте. (файл MNOG3.PAS).
Решение.
program mnog3;
var z:
SET OF
0..9;
k,i:integer;
si:char;
begin
readln;
write('=>');
z:=[
];
repeat
read(si);
k:=ord(si)-ord('0');
if k in [0..9] then
z:=z+[k]
until si='.';
if z=[ ] then writeln ('В тексте нет цифр')
else
begin
write('В тексте имеются следующие цифры:');
for i:=1 to 9 do
if i
in z then write (i:2);
writeln;
end;
end.
Задача №4. Известен
набор продуктов - хлеб, масло, сыр, молоко, имеющихся в ассортименте магазинов.
В три магазина доставлены отдельные виды этих продуктов. Требуется построить
множества a,b,c, которые содержат соответственно:
- продукты, имеющиеся
одновременно во всех магазинах;
- продукты, имеющиеся по крайней мере в одном
из магазинов;
- продукты, которых нет ни в одном из магазинов.
Решение. файл
MNOG4.PAS).
program mnog4;
uses crt;
const
n=3;
type
produkt=(xleb,maslo,sir,moloko);
accort=set of
produkt;
magazin=array[1..n] of accort;
var
m1:magazin;
x:produkt;
a,b,c,xm1:accort;
i,j,iw,m:integer;
begin
clrscr;
for i:=1 to n do
begin xm1:=[ ];
writeln('Вводи номера
продуктов',i:2,'-го магазина=');
repeat
read(iw);
case iw of
1:
x:=xleb;
2: x:=maslo;
3: x:=sir;
4:
x:=moloko;
end;
xm1:=xm1+[x];
until
eoln;
m1[i]:=xm1;
end;
a:=m1[1]; b:=[]; c:=[xleb..moloko];
for i:=1
to n do
begin b:=b+m1[i];
a:=a*m1[i];
c:=c-b;
end;
for i:=1 to n
do
begin
case i of
1: writeln('продукты, имеющиеся одновременно во всех
магазинах');
2: writeln('ассортимент продуктов');
3: writeln('продукты,
которых нет ни в одном магазине');
end;
for x:=xleb to moloko do
if x
in a then
case x of
xleb: write('хлеб');
maslo:write('масло');
sir:
write('сыр');
moloko:write('молоко');
end;
if i=1 then a:=b else
a:=c;
writeln;
end;
end.
Задача №5. Сформировать множество, в которое входят только латинские буквы, встретившиеся во входной строке, и множество знаков препинания из входной строки. (Самостоятельно!)
program mnog5;
var LB:
SET OF 'a'..'z'; PR: SET OF '!'..'?';
C,I,J:char;
begin
readln;
write('=>');
LB:=[ ]; PR:=[
];
repeat
read(C);
if C in ['a'..'z'] then LB:=LB+[C] ELSE IF C IN
['!',';',':','.',',','?']
THEN PR:=PR+[C]
until
EOLN;
writeLN('Латинские буквы:');
for i:='a' to 'z' do
if i in lb then
write (i:2);
writeln;
writeln('знаки препинания');
for j:='!' to '?'
do
if j in pr then write(j:2);
end.
Задание для работы в группах по теме "Множества"
