Операция определения принадлежности

Элемента множеству

Эта логическая операция обозначается служебным словом in. Результат операции имеет значение true, если элемент входит в множество, и false в против­ном случае.

Примеры

1) Выражение 5 in [3..7] имеет значение true, так как 5Î[3; 7];

2) выражение 'a' in ['A'..'Z'] имеет значе­ние false, так как маленькой латинской буквы 'а' нет среди больших латинских букв.

Примечание. Операцию проверки принадлежности эле­мента множеству удобно использовать для исключения более сложных проверок. Например, оператор вида:

If (ch='a') or (ch='b') or (ch='x') or (ch='y') Then... − может быть переписан в компактной и наглядной форме:

If ch in ['a', 'b', 'х', 'у'] Then...

Сравнение множеств

Для сравнения множеств используются операции от­ношения:

= − проверка на равенство (совпадение) двухмножеств;

<> − проверка на неравенство двух множеств;

<=, < − проверка на вхождение первого множества во второе множество;

>=, > − проверка на вхождение второго множества в первое множество.

Пример 1

Составить программу выделения следующих множеств из множества целых чисел от 1 до 30:

− множества чисел, кратных 2;

− множества чисел, кратных 3;

− множества чисел, кратных 6;

− множества чисел, кратных 2 или 3.

Вопросы для обсуждения

1. Сколько множеств надо описать? Каков тип их элементов? (Четыре множества с элементами типа Byte.)

2. Каково начальное значение множеств? (Начальное значение множеств − пустое множество.)

3. Как формируются множества? (Первые два фор­мируются перебором всех чисел данного промежутка и отбором подходящих, а третье и четвертое получаются из первых двух путем применения операций пересече­ния или объединения.)

4. Как осуществить вывод сформированных множеств? (Вывод множеств производится ТОЛЬКО поэлементно, поэтому удобно составить процедуру и передавать в нее множество, элементы которого и будут выводиться на экран. Для этого в разделе типов надо создать соответст­вующий тип и использовать его в дальнейшем.)

Программа для решения данной задачи выглядит так:

Program Example_139;

Const n = 30;

Type mn=Set Of 1..n;

Var n2, n3, n6, n23: mn;

{n2 - множество чисел, кратных 2,

n3 - кратных 3, n6 - кратных 6,

n23 - кратных 2 или 3}

k: Integer;

Procedure Print(m: mn);

Var i: Integer;

Begin

For i:=1 To n Do

If i In m Then Write(i:3);

Writeln;

End;

Begin

n2:=[ ]; n3:=[ ];

{начальные значения множеств}

For k:=1 To n Do {формирование n2 и n3}

Begin

{если число делится на 2, то

заносим его в n2}

If k Mod 2=0 Then n2:=n2+[k];

{если число делится на 3, то

добавляем его в n3}

If k Mod 3=0 Then n3:=n3+[k];

End;

{числа, кратные 6, - это те, которые

кратны и 2, и 3, поэтому это пересечение

двух первых множеств, а числа, кратные 2

или 3, - это объединение этих

же множеств}

n6:=n2*n3; n23:=n2+n3; {вывод множеств}

Writeln('числа, кратные 2');

Print(n2);

Writeln('числа, кратные 3');

Print(n3);

Writeln('числа, кратные 6');

Print(n6);

Writeln('числа, кратные 2 или 3');

Print(n23);

Readln;

End.

Задание

Изменить программу так, чтобы результатом ее рабо­ты являлось множество чисел, делящихся на 3, но не делящихся на 2.

Пример 2

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

Вопросы для обсуждения

1. Сколько множеств надо задать и каков тип их эле­ментов? (Четыре множества с элементами символьного типа.)

2. Как сформировать множества? (С помощью опера­тора присваивания: например,

s1:=['б', 'о', 'б'])

3. Как сформировать искомые множества? (С помощью операций пересечения, объединения, вычитания множеств.) Программа для решения этой задачи приведена ниже:

Program Example_140;

Var y1, y2, у3, у4, х: Set of Char;

s: Char;

Begin

у1:=['б', 'о', 'б'];

y2:=[ 'л', 'о', 'ж', 'к', 'а'];

у3:=['к', 'о', 'т'];

у4:=['т', 'е', 'п', 'л', 'о'];

х:=(у1*у2)+у3-у4;

Writeln ('множество х');

{вывод множества х}

For s:='a' То 'я' Do

If s in x Then Write (s); Writeln;

{проверка: состоит ли муравей из кота}

If у3<=х Then Write ('муравей состоит

из кота')

Else Write('муравей не состоит

из кота');

End.

Пример 3

Дано натуральное число n. Составить программу, пе­чатающую в порядке возрастания все цифры, не входя­щие в десятичную запись данного натурального числа.

Вопросы для обсуждения

1. Какое множество нужно сформировать? (Множест­во цифр, входящих в десятичную запись данного числа.)

2. Как сформировать это множество? (С помощью операций div и mod последовательно выделить цифры данного числа и занести их во множество.)

3. Как получить искомый результат и как его вывести?

Программа для решения этой задачи такова:

Program Example_141;

Type mn=Set Of 0..9;

Var s: mn;

n: Longint;

k: Integer;

Begin

Writeln('введите число n');

Readln(n);

s:=[ ]; {формирование множества цифр

десятичной записи натурального числа}

While n<>0 Do

Begin

k:=n Mod 10;

n:=n Div 10;

If Not (k in s) Then s:=s+[k];

End;

{вывод цифр в порядке возрастания}

For k:=0 To 9 Do

If Not (k in s) Then Write(k:2);

Writeln;

Readln;

End.

Пример 4

"Решето Эратосфена". Составить программу поиска простых чисел в промежутке [1; n]. Число n вводится с клавиатуры.

Решение

Простым называется число, которое не имеет других делителей, кроме единицы и самого этого числа. Для решения этой задачи воспользуемся методом "решета Эратосфена", идея которого заключается в следующем: сформируем множество М, в которое поместим все чис­ла заданного промежутка. Затем последовательно будем удалять из него элементы, кратные 2, 3, 4 и так далее, до [n/2] (целая часть числа). После такого "просеива­ния" в множестве М останутся только простые числа.

Примечание. Легко доказать, что можно удалять числа, кратные 2, 3, 4 и так далее, до [sqrt(n)], то есть до целой части квадратного корня числа n.

Ниже приведен вариант решения этой задачи.

Program Example_142;

Var m: 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:=1 To n Do

If i in m Then Write(i:3);

Readln;

End.

Пример 5

Дан ребус:

МУХА

МУХА

СЛОН

Решение

Каждой букве соответствует некоторая цифра, разным буквам соответствуют разные цифры. Необходимо заме­нить буквы цифрами так, чтобы получилось верное ра­венство. Найти все решения (если есть несколько).

Для решения этой задачи применим метод перебора с возвратом. Используем множество S1 для хранения цифр слова муха, причем будем заносить в него цифры последовательно, учитывая уже внесенные цифры. Началь­ное значение S1 − пустое множество. После выбора всех цифр первого слова формируем соответствующее число и находим число, соответствующее слову СЛОН. Выделяем цифры СЛОНа (множество S2), и если слова состоят из разных цифр (то есть пересечение S1 и S2 пустое) и все цифры СЛОНа разные, то выводим реше­ние на экран. Далее удаляем из множества S1 послед­нюю внесенную цифру и пытаемся выбрать еще одно ее значение. Таким образом, мы перебираем все возможные варианты и выводим на экран только те, которые удовлетворяют равенству.

Заметим, что букве “М” в слове МУХА может соот­ветствовать цифра от 1 до 4, а букве “А” в этом же слове не может соответствовать 0.

Ниже приводится одно из решений.

Program Example_143;

Type mn=Set Of 0..9;

Var m, y, x, a: 0..9; {цифры числа МУХА}

 n1, n2: Integer; {числа МУХА и СЛОН}

a1, a2, a3, a4: 0..9;  

{цифры числа СЛОН}

s1, s2: mn;

{для хранения цифр каждого из чисел}

Procedure Print (x,у: Integer); 

{вывод решения в виде ребуса}

Begin

Writeln(x:5);

Writeln('+');

Writeln(x:5);

Writeln(' _____');

Writeln(y:5);

End;

Begin

s1:=[ ]; s2:=[ ];

For m:=1 To 4 Do

Begin

s1:=s1+[m];

{заносим первую использованную цифру}

For у:=0 To 9 Do {если эта цифра не

была еще взята, то добавляем ее во

множество цифр числа МУХА и выбираем

цифру для следующей буквы}

If Not (у in s1) Then

Begin

s1:=s1+[y];

For x:=0 To 9 Do

If Not (x in s1) Then

Begin

s1:=s1+[x];

For a:=1 To 9 Do

If Not (a in s1) Then

Begin

s1: =s1+[a];

n1 :=1000*m+100*y-10*x+a;

{число для слова МУХА}

n2:=2*n1;

{число для слова СЛОН}

a1:=n2 Div 1000;

{выделяем цифры СЛОНа}

а2:=n2 Div 100 Mod 10;

a3:=n2 Div 10 Mod 10;

a4:=n2 Mod 10;

s2:=[a1, a2, a3, a4];

{множество цифр СЛОНа}

{если слова состоят из разных

цифр и в слове СЛОН нет

одинаковых букв, то выводим

решение ребуса на экран}

If (s1*s2=[ ]) And

([al]*[a2]*[a3]*[a4]=[ ])

Then Print(n1, n2);

s1:=s1-[a];

{удаляем занесенную цифру}

End;

s1:=s1-[x];

End;

s1:=s1-[y];

End;

s1:=s1-[m];

End;

Readln;

End.