Лабораторная работа №6. Программирование с использованием множеств

Общие сведения

Цель работы: познакомить с понятием "множество" в языке программирования Pascal; выработать навыки работы со структурой данных множество.

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

Понятие множества в языке ПАСКАЛЬ основывается на математическом представлении о множествах: это ограниченная совокупность различных элементов. Для построения конкретного множественного типа используется перечисляемый или интервальный тип данных. Тип элементов, составляющих множество, называется базовым типом.

Множественный тип описывается с помощью служебных слов Set of, например:

type M= Set of B;

Здесь М - множественный тип, В - базовый тип.

Пример описания переменной множественного типа:

type M= Set of 'A'..'D'; var MS: M;

Принадлежность переменных к множественному типу может быть определена прямо в разделе описания переменных:

var C: Set of 0..7;

Константы множественного типа записываются в виде заключенной в квадратные скобки последовательности элементов или интервалов базового типа, разделенных запятыми, например:

['A', 'C'] [0, 2, 7] [3, 7, 11..14].

Константа вида [] означает пустое подмножество.

Множество включает в себя набор элементов базового типа, все подм- ножества данного множества, а также пустое подмножество. Если базовый тип, на котором строится множество, имеет К элементов, то число подм- ножеств, входящих в это множество, равно 2 в степени К. Пусть имеется переменная Р интервального типа:

var P: 1..3;

Эта переменная может принимать три различных значения - либо 1, либо 2, либо 3. Переменная Т множественного типа

var T: Set of 1..3;

может принимать восемь различных значений:

[ ] [1,2] [1] [1,3] [2] [2,3] [3] [1,2,3]

Порядок перечисления элементов базового типа в константах безразличен.

Значение переменной множественного типа может быть задано конструкцией вида [T], где T - переменная базового типа.

К переменным и константам множественного типа применимы операции присваивания(:=), объединения(+), пересечения(*) и вычитания(-):

['A','B'] + ['A','D'] даст ['A','B','D'] ['A'] * ['A','B','C'] даст ['A'] ['A','B','C'] - ['A','B'] даст ['C'].

Результат выполнения этих операций есть величина множественного типа.

К множественным величинам применимы операции: тождественность (=), нетождественность (<>), содержится в (<=), содержит (>=). Результат выполнения этих операций имеет логический тип, например:

['A','B'] = ['A','C'] даст FALSE ['A','B'] <> ['A','C'] даст TRUE ['B'] <= ['B','C'] даст TRUE ['C','D'] >= ['A'] даст FALSE.

Кроме этих операций для работы с величинами множественного типа в языке ПАСКАЛЬ используется операция in проверяющая принадлежность элемента базового типа, стоящего слева от знака операции, множеству, стоящему справа от знака операции. Результат выполнения этой операции - булевский. Операция проверки принадлежности элемента множеству часто используется вместо операций отношения, например:

A in ['A', 'B'] даст TRUE, 2 in [1, 3, 6] даст FALSE.

При использовании в программах данных множественного типа выполнение операций происходит над битовыми строками данных. Каждому значению множественного типа в памяти ЭВМ соответствует один двоичный разряд. Например, множество

['A','B','C','D']

представлено в памяти ЭВМ битовой строкой

1 1 1 1.

Подмножества этого множества представлены строками:

['A','B','D'] 1 1 0 1 ['B','C'] 0 1 1 0 ['D'] 0 0 0 1

Величины множественного типа не могут быть элементами списка вво- да - вывода.

В каждой конкретной реализации транслятора с языка ПАСКАЛЬ количество элементов базового типа, на котором строится множество, ограничено. В TURBO PASCAL количество базовых элементов не должно превышать 256.

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

const seLit: Set of 'A'..'D'= [];

Проиллюстрируем применение данных множественного типа на примере.

Пример. Составить программу, которая вырабатывает и выводит на экран дисплея наборы случайных чисел для игры в "Спортлото 5 из 36".

Для заполнения каждой карточки спортлото необходимо получить набор из пяти псевдослучайных чисел. К этим числам предъявляются два требования:

· числа должны находиться в диапазоне 1..36;

· числа не должны повторяться.

Program Lotto; var nb, k: Set of 1..36; kol, l, i, n: Integer; begin Randomize; WriteLn('ВВЕДИ kol'); ReadLn(kol); nb:=[1..36]; for i:=1 to kol do begin k:=[]; for l:=1 to 5 do begin repeat n:=Random(36) until (n in nb) and not (n in k); k:=k+[n]; Write(n:4) end; WriteLn end end.

 

Пример

Пример1: Дан текст. Определить каких букв больше - гласных или согласных.

Этапы решения задачи: 1. Составим блок схему программы

 

Опишем подробнее блок "Подсчитываем количество гласных и согласных букв"

 

Рассмотрим блок "Печатаем соответствующее сообщение"

 

Запишем блок-схему целиком

 

2. Переведем алгоритм на язык Паскаль

program example1; const glasn=['а','е','и','о','у','ы','э','ю','я']; soglas=['б','в','г','д','ж','з','й','л','м', 'н','р','к','п','с','т','ф','х','ц','ч','ш','щ']; var st: string; g,s,i:integer; begin write('Введите строку> '); readln(st); g:=0; s:=0; for i:= 1 to length(st) do if st[i] in glasn then inc(g) else if st[i] in soglas then inc(s); if g> s then writeln('Гласных больше') else if g< s then writeln('Согласных больше') else writeln('Согласных и гласных букв поровну'); readln; end.

Контрольные вопросы

1. Что такое множество, как оно описывается в языке Pascal?
2. Как определить новый тип данных с использованием перечисления?
3. Как описываются типизированные константы типа множество?
4. Как осуществляется ввод-вывод значений переменных типа множество?
5. Какие типы данных используются в качестве базовых при объявлении типа множество?
6. Какие операции определены над множествами?
7. Какие операции допустимы над переменными, заданными перечислением?
8. Чем похожи и чем отличаются множества и массивы?
9. Какое значение у выражений: а) x in [x]; б) [ ] <= [x,y,z]; в) [x]<>[x,x,x]

Задания

Примечание: Гласные буквы - а,е,и,о,у,ы,э,ю,я (ё обычно не входит в литерный тип); согласные - все остальные буквы, кроме ь, ъ; звонкие согласные - б,в,г,д,ж,з,й,л,м,н,р; глухие согласные - к,п,с,т,ф,х,ц,ч,ш,щ.

1. Дан текст из строчных латинских букв, за которым следует точка. Напечатать:
- первые вхождения букв в текст, сохраняя их взаимный исходный порядок;
- все буквы, входящие в текст не менее двух раз;
- все буквы, входящие в текст по одному разу.
Дана непустая последовательность слов из строчных русских букв; между соседними словами - запятая, за последним словом - точка. Напечатать в алфавитном порядке:

2. все гласные буквы, которые входят в каждое слово; все согласные буквы, которые не входят ни в одно слово;

3. все звонкие согласные буквы, которые входят хотя бы в одно слово; все глухие согласные буквы, которые не входят хотя бы в одно слово;

4. все согласные буквы, которые входят только в одно слово; все глухие согласные буквы, которые не входят только в одно слово;

5. все звонкие согласные буквы, которые входят более чем в одно слово; все гласные буквы, которые не входят более чем в одно слово;

6. все звонкие согласные буквы, которые входят в каждое нечетное слово и не входят ни в одно четное слово; все глухие согласные буквы, которые входят в каждое нечетное слово и не входят хотя бы в одно четное слово.

7. Имеются три множества символьного типа, которые заданы своими конструкторами:
Y1=['A','B','D','R','H']
Y2=['R','A','H','D']
Y3=['A','R'].
Сформировать новое множество.
Предусмотреть формирование исходных множеств с клавиатуры.

8. Подсчитать общее количество цифр и знаков '+', '-', и '*', входящих в строку s.

9. Подсчитать количество различных (значащих) цифр в десятичной записи натурального числа n и напечатать в возрастающем порядке все цифры, не входящие в десятичную запись натурального числа n.

10. Вычислить сумму тех элементов матрицы A, номера строк и столбцов которых принадлежат соответственно непустым множествам S1 и S2 типа Nom.

Cons n=10; Type Nomer= 1..n; Матрица = Array[Nomer,Nomer] of Real; Nom = Set of Номер;

Задачи повышенной сложности

1. Дан текст, являющийся русскими словами. Выполнить разделение каждого его слова на части для переноса.
Далее правила переноса русских слов.
a) Две идущие подряд гласные можно разделить, если первой из них предшествует согласная, а за второй идет хотя бы одна буква (буква й при этом рассматривается вместе с предшествующей гласной как единое целое).
b) Две идущие подряд согласные можно разделить, если первой из них предшествует гласная, а в той части слова, которая идет за второй согласной, имеется хотя бы одна гласная (буквы ъ, ь вместе с предшествующей согласной рассматриваются как единое целое).
c) Если не удается применить пункты a, b, то следует попытаться разбить слова так, чтобы первая часть содержала более чем одну букву и оканчивалась на гласную, а вторая содержала хотя бы одну гласную. Вероятность правильного разбиения увеличивается, если предварительно воспользоваться хотя бы неполным списком приставок, содержащих гласные, и попытаться, прежде всего, выделить из слова такую приставку.

2. Написать программу раздачи карт при игре в дурака, количество игроков задается с клавиатуры.

3. Для произвольного символьного множества сгенерировать все подмножества