Geum.ru

Конспект лекций по информатике для специальностей 2102, 2103 Автор доц., к т. н. Каширская Е. Н

Вид материалаКонспект

Содержание


7.1. Свойства множеств
7.2. Операции над множествами
Подобный материал:
1   ...   13   14   15   16   17   18   19   20   ...   25

7.1. Свойства множеств

  1. Все элементы базового типа, образующие множество, должны быть различны. Запись элементов множества (2, 2, 3, 4) некорректна, поскольку два элемента тождественны.

2. Порядок расположения элементов во множестве не фиксируется, то есть множества представляют собой неупорядоченные совокупности объектов (элементов). Множества (1, 3, 5, 6), (6, 1, 3, 5) и (5, 3, 1,6) одинаковы.

Важным качеством данного типа значений является наличие новых операций по их обработке.

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


В языке программирования Паскаль имеются следующие операции над множествами:
  1. + объединение множеств;
  2. * пересечение множеств;
  3. – вычитание множеств;
  4. =, < > проверка множеств на равенство, неравенство; множество А равно множеству В, если каждый элемент множества А является элементом множества В и наоборот, каждый элемент множества В является элементом множества А; иначе множества А и В неравны друг другу; результат операции будет логического типа: True или False;
  5. <= проверка множества на включение; множество А включено в множество В, если элементы множества А являются также элементами множества В; результат операции А <= В – логический: True или False;
  6. IN проверка на принадлежность какого-либо значения множеству; результат операции – логический: True или False; операция S IN A служит для проверки, принадлежит ли элемент базового типа S множеству А.

Пример. Решето Эратосфена. Составить программу, реализующую алгоритм определения набора простых чисел, не превышающих некоторого заданного числа, то есть алгоритм построения “решета Эратосфена”.

Program Resheto;

const N = 256; {Верхняя граница значений элементов множества}

var S: Set of 2..N;

C, M, P: integer;

begin writeln(‘Введите границу’);

read(P);

writeln(‘Простые числа до ‘, P: 3);

S := [2..N];

For C := 2 to P do

If C in S then

begin writeln(C: 3);

for M := 1 to (P div C) do

S := S – [C * M];

end;

end.

Пример. Если взять то общее, что есть у боба с ложкой, добавить кота и поместить в тёплое место, то получится муравей. Так ли это? Состоит ли муравей из кота?

Пусть Y1, Y2, Y3 и Y4 – заданные множества символьного типа. Они получают значения с помощью операторов присваивания;

Y1 := [‘B’, ‘E’, ‘A’, ‘N’] – боб,

Y2 := [‘S’, ‘P’, ‘O’, ‘O’, ‘N’] – ложка,

Y3 := [‘C’, ‘A’, ‘T’] – кот,

Y4 := [‘C’, ‘O’, ‘L’, ‘D’] – холод,

[‘A’,’N’,’T’] – муравей.

Применяя соответствующие операции над множествами, формируем новое множество:

X := (Y1 * Y2) + Y3 – Y4;


Program A28A;

Var Y1, Y2, Y3, Y4, X: Set of Char; (* множества *)

S: Char; (* символ *)

Begin

Y1 := [‘B’, ‘E’, ‘A’, ‘N’]; {боб}

Y2 := [‘S’, ‘P’, ‘O’, ‘O’, ‘N’]; {ложка}

Y3 := [‘C’, ‘A’, ‘T’]; {кот}

Y4 := [‘C’, ‘O’, ‘L’, ‘D’]; {холод}

X := (Y1 * Y2) + Y3 – Y4;

write(‘X=’);

for S := ‘A’ to ‘Z’ do

if S in X then write(S);

writeln;

if Y3 <= X

then write(‘Yes’)

else write(‘No’);

end.

Здесь для вывода значений нового множества Х используется оператор цикла For. Параметром цикла является символьная переменная S, которая принимает значение каждого символа латинского алфавита от ‘A’ до ‘Z’. Если значение переменной S принадлежит множеству Х, то оно выводится на экран дисплея.

Для решения второй части задачи “Состоит ли муравей из кота?” используется операция включения <= в условном операторе.

Пример. Из множества целых чисел [2..20] выделить следующие множества:
  • делящихся на 6 без остатка:
  • делящихся без остатка на 2, или на 3 или на 2 и 3;

Введём обозначения:

N2 – множество чисел, делящихся на 2;

N3 – множество чисел, делящихся на 3;

N6 – множество чисел, делящихся на 6;

N23 – множество чисел, делящихся на 2 и 3;

Program A23;

Const N = 20; (* размерность множества*)

Var N2, N3, N6, N23: Set of Integer;

K: Integer;

Begin

N2 := [ ]; (* начальное значение N2 *)

N3 := [ ]; (* начальное значение 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 (‘ on 6 devite: ‘);

For K := 1 to N do

If K in N6 then write(K: 3);

writeln;

writeln(‘ on 2 or 3 devite: ‘);

For K := 1 to N do

If K in N23 then write(K: 3);

End.

На экране:

on 6 devite:

6 12 18

on 2 or 3 devite:

2 3 4 6 8 9 10 12 14 15 16 18 20


Пример. Составить программу, реализующую алгоритм построения множеств из символов, проверки вхождения произвольного символа в построенные множества, сравнения двух множеств.

Program Mnogestvo;

Type M = Set of ‘A’..’Z’;

Var M1, M2: M;

B: Char;

Begin M1 := [ ];

M2 := [ ];

Repeat writeln(‘введите символ-элемент 1-го множества‘);

read(B);

M1 := M1 + [B];

Until B =’.’;

Repeat writeln(‘введите символ-элемент 2-го множества‘);

read(B);

M2 := M2 + [B];

Until B =’.’;

writeln(‘ все встретившиеся буквы: ‘);

for B := ‘A’ to ‘Z’ do

if B in M1 + M2 then write(B: 2);

writeln(‘ общие буквы: ‘);

for B := ‘A’ to ‘Z’ do

if B in M1 * M2 then write(B: 2);

if M1 = M2 then writeln(‘ множества совпадают ‘);

if M1 < > M2 then writeln(‘ множества не совпадают ‘);

if M1 >= M2 then writeln(‘ 2-ое есть подмножество 1-го ‘);

if M1 <= M2 then writeln(‘ 1-ое есть подмножество 2-го ‘);

End.