20.3.1. Примеры программ с использованием множеств

При разработке алгоритмов и программ с множествами необходимо учесть, что Паскаль не обеспечивает ввод или вывод множеств непосредственно с помощью операторов Read или Write. Формирование множества, элементы которого вводятся с клавиатуры, можно выполнить, используя операцию присоединения, следующим образом.

Один из алгоритмов ввода множества

1. Множество :=[ ].

2. Повторять

2.1. Ввести элемент;

2.2. Множество:= Множество + [элемент].

Пока не надоест.

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

Один из алгоритмов вывода множества

1. Для Элемента от Первого_значения до Последнего_значения выполнить

Если Элемент принадлежит (In) Множеству, то

Вывести Элемент.

Рассмотрим примеры алгоритмов и программ, использующих множества.

Пример 1. Сформировать и вывести на экран множество из n символов латинского алфавита (n<20). Если вводимая буква уже есть в множестве, выдать соответствующее сообщение.

Program Mnog_Sim;

Const

N=20;

Var

S : Set Of Char;

B : Char;

I : Integer;

Begin

S := [];

For I:=1 To N Do

Begin

Writeln (’Введите букву’);

Readln(B);

If B In S Then

Writeln(’Буква ’,B,’ уже есть’)

Else

S:=S+[B];

End;

Writeln(’Буквы, входящие в множество’);

For B:=’A’ To ’z’ Do

If B In S Then

Write(B:2);

End.

Обратите внимание, что вводимые буквы могут быть и прописными, и строчными, поэтому при выводе в цикле For параметр цикла принимает все значения для букв латинского алфавита от A до z.

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

Program Glasn;

Var

P : String; {предложение}

Gl : Set Of Char; {множество гласных}

B : Char;

K,I,N : Integer;

Begin

Gl := [];

B := ’#’;

While B <> ’!’ do

Begin

Writeln (’Введите гласную, конец ввода – !’);

Readln(B);

If B <> ’!’ then

Gl := Gl+[B];

End;

Writeln (’Введите предложение’);

Readln(P);

K := 0;

N := Length(P);

For I := 1 To N Do

If P[I] In Gl Then

K := K+1;

Writeln (’Количество гласных в предложении - ’,K);

WriteLn(’Нажмите клавишу ENTER...’);

ReadLn;

End.

Пример 3. Составить программу продажи билетов на пароход. Пусть места на пароходе нумеруются (для простоты) от 1 до n (n < 250). Покупатель заказывает номера мест. Если они свободны, то ему выдаются билеты, и номера мест исключаются из числа свободных. В противном случае предлагаются номера свободных мест. Если все билеты проданы, то начинается путешествие.

Алгоритм

1. Задать множество свободных мест: от 1 до n.

2. Повторять

2.1. Вывести список свободных мест;

2.2. Запросить заказ на билеты;

2.3. Если места свободны, то

продать билеты (занять места, заказ принят),

иначе

сообщить, что некоторые места уже проданы (заказ не принят).

Пока не будут заняты все места.

3. Вывести сообщение, что все билеты проданы.

Уточняем условие. В задаче будем использовать 2 множества:

1) Свободные места (Sm);

2) Заказ (Zak).

Запишем уточненный Алгоритм.

1. Задать множество Свободных мест: от 1 до n.

2. Повторять

2.1. Вывести свободные места

2.2. Запросить заказ на билеты:

2.2.1. Заказ = [ ] – пустое множество.

2.2.2. Ввести номер_места

2.2.3. Пока номер ≠0 выполнить:

а) объединить номер_места с заказом;

б) ввести номер места.

2.3. Если заказ входит в Свободные места, то

2.3.1. Выдать сообщение: "заказ принят"

2.3.2. Исключить проданные места

(Свободные_места := Свободные_места – заказ)

Иначе

Выдать сообщение "заказ не принят".

Пока не будут заняты все места.

3. Вывести сообщение, что все билеты проданы.

Программа, реализующая этот алгоритм, приведена ниже.

Program Teploxod;

Const

N=250; { На время отладки назначьте небольшое N! }

Type

Mesta = Set Of 1..N;

Var

Sm,Zak : Mesta;{Свободные места и заказ}

I,Nom : Integer;

Begin

Sm := [1..N];{п. 1, свободные места}

Repeat {п. 2}

WriteLn;

Writeln(’ Cвободные места: ’); {п. 2.1.}

For I:=1 To N Do

If I In Sm Then

Write (I:4);

WriteLn;

Zak := []; {п. 2.2.1.}

{Формирование Заказа}

Writeln(’Введите номера мест, которые Вы покупаете. ’,

’Конец заказа - ноль’);

ReadLn(Nom); {п. 2.2.2.}

While Nom <> 0 Do {п. 2.2.3.}

Begin

Zak := Zak + [Nom];

ReadLn(Nom);

End;

If Zak <= Sm Then {п. 2.3.}

Begin

Writeln(’Заказ принят’); {п. 2.3.1.}

Sm := Sm - Zak; {п. 2.3.2.}

End

Else

WriteLn(’Заказ не принят. ’,

’Некоторые из заказываемых мест уже проданы.’);

Until Sm=[];

Writeln (’Все билеты проданы, нажмите Enter’);

Readln;

End.