2.5. Множественный тип

     Множественный тип является реализацией математической теории множеств. Реализованы только конечные множества на базе порядкового типа. Диапазон значений множественного типа представляет собой мощность множества для определенного порядкового типа (базового типа). Каждое возможное значение множественного типа является подмножеством возможных значений базового типа. Базовый тип не должен иметь более 256 возможных значений, и порядковые значения верхней и нижней границы базового типа должны не превышать диапазона от 0 до 255. В силу этого базовый тип множества не может быть коротким целым (Shortint), целым (Integer), длинным целым (Longint) или словом (Word). Внутреннее представление множества представляет собой массив бит, в котором каждый бит указывает, является элемент принадлежащим множеству или нет. Максимальное число элементов множества - 256, так что множество никогда не может занимать более 32 байт. Число байт, занятых отдельным множеством, вычисляется, как:

ByteSize = (Max div 8) - (Min div 8) + 1

     где Мin и Мах - нижняя и верхняя граница базового типа этого множества. Номер байта для конкретного элемента E вычисляется по формуле:

ByteNumber = (E div 8) - (Min div 8)

     а номер бита внутри этого байта по формуле:

BitNumber = E mod 8

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

     Описатель множества определяет значения множественного типа и получается путем записи выражений, заключенных в квадратные скобки ([]). Каждое выражение определяет значение множества. Любой множественный тип может принимать значение [], которое называется пустым множеством, тип которого совместим по присваиванию с типом любого множества. Любая группа элементов, описанная, как х..у, объявляет элементами множества все значения в диапазоне х..у. Если х больше, чем у, то х..у не описывает никаких элементов и [x..y] обозначает пустое множество. В конкретном описателе множества все значения выражения в группах элементов должны быть одного порядкового типа.

     В соответствии с математическими определениями реализованы операции пересечения (*), объединения (+) и разности (-). Результаты операций соответствуют правилам логики работы с множествами:

         1. Порядковое значение c содержится в a + b только тогда, когда оно содержится в a или в b.

         2. Порядковое значение c содержится в a - b только тогда, когда оно содержится в a и не содержится в b.

         3. Порядковое значение c содержится в a * b только тогда, когда он содержится в обоих множествах a и b.

     Если наименьшим порядковым значением,  которое является членом результата операций над множествами, является a, а наибольшим - b, то типом результата будет множество a..b.

     Для множественных операций сравнения, если операндами являются множества a и b, то при их сравнении получаются следующие результаты:

         1. Выражение a = b истинно только когда a и b содержат одни и те же элементы, в противном случае a <> b.

         2. Выражение a <= b истинно, когда каждый элемент множества а является также элементом множества b.

         3. Выражение a >= b истинно, когда каждый элемент множества b является также элементом множества a.

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

     В отличие от других производных типов, для множественного типа операция селектирования - то есть позиционирование не конкретный элемент множества - отсутствует. Для организации вывода элементов множества типичным является подход, основанный на переборе всех значений базового типа с проверкой наличия каждого значения базового типа в множестве, в случае которого осуществляется вывод. Например, для вывода элементов множества Collection, представляющих собой значения ограниченного типа 1..100 на базе целого, целесообразно реализовать следующий вычислительный процесс:

...

for Elem:= 1 to 100 do

  if Elem in Collection then write ( Elem )

...

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

Collection:= [ Elem ] + Collection

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

     Приведем несколько примеров констант-множеств:

type

  Digits  = set of 0..9;

  LatLetters = set of 'A'..'Z';

const

  EvenDigits: Digits = [0,2,4,6,8];

  Vowels    : LatLetters = ['A','E','I','O','U','Y'];

     Разберем решение типичной задачи, связанной с обработкой данных множественного типа.

Текст задания

     Дан текст из строчных латинских букв, за которыми следует точка. Требуется вывести первые вхождения букв в текст, сохраняя их взаимный порядок.

Решение

program CollectSample;

var

  let: set of 'a'..'z';

  c: char;

begin

  let:= []; {множество букв в рассмотренной части текста}

  read( c );

  while c <> '.' do begin

    if not ( c in let ) then begin {первое вхождение}

      write( c );

      let:= let + [ c ]

    end;

    read( c )

  end;

  writeln

end.

Варианты заданий

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

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

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

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

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

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

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

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

9.      Дан некоторый текст, за которым следует точка (в сам текст точка не входит). Определить, является ли этот текст правильной записью формулы:

<формула>::= <терм> | ( <формула> <знак> <формула> )

<знак>::= + | - | *

<терм>::= <имя> | <целое>

<имя>::= <буква> | <имя> <буква> | <имя> <цифра>

<целое>::= <цифра> | <целое> <цифра>

<буква>::= а | б | в | г | д | е | ж

<цифра>::= 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9

10.  Описать логическую функцию path( G, N, K, D ), которая определяет, есть ли в ориентированном графе G путь из вершины N в вершину K, и, если есть, присваивает параметру D длину (число дуг) кратчайшего пути из N в K. Использовать следующее представление графа: type node= (b1,b2,b3,b4,b5,b6,b7,b8); neib= set of node; graph1= array [node] of neib; (G[x] √ множество вершин, в которые ведут дуги из вершины x.)

11.  type state= (a,b,c,d,e,g,h); states= set of state; routs= array [state] of states; Описать процедуру ruotexist(r, n, k), которая по рейсам r (r[x]- множество городов, в которые можно за один рейс доехать автобусом из города x) определяет k √ множество городов, в которые можно попасть автобусом (за один рейс или через другие города) из города n.

12.  type name= (George, Alex, Piter, Ann, Paul, John, Fred, Natalie, Robert); guests= set of name; group= array[name] of guests; Описать логическую функцию anywhere( gr ), определяющую, есть ли в группе gr хотя бы один человек, побывавший в гостях у всех остальных из группы (gr[x]- множество людей, бывших в гостях у человека с именем x; x не принадлежит gr[x]).

13.  type product= (broth, butter, milk, flesh, fish, salt, chees, sugar, tee, cofe); assort= set of product; shops= array [1..20] of assort; Описать процедуру is( s, a, b, c ), которая по информации из массива s типа shops (s[i] √ это множество продуктов, имеющихся в i-ом магазине) присваивает параметрам a, b, c типа assort следующие значения: a- множество продуктов, которые есть во всех магазинах; b- множество продуктов, каждый из которых есть хотя бы в одном магазине; c- множество продуктов, которых нет ни в одном магазине.

14.  Дано целое n от 2 до 1000. Используя метод ╚решето Эратосфена╩, напечатать в убывающем порядке все простые числа из диапазона n..2n. (Суть метода: выписываются все целые числа, большие 1; выбирается первое из них (это 2, простое число) и вычеркиваются все кратные ему числа, кроме него самого; затем берется следующее из не вычеркнутых чисел (это 3, также простое число) и вычеркиваются все кратные ему, опять же кроме него самого; и так для каждого не вычеркнутого ранее числа. В конце концов, останутся только простые числа, начиная с 2.)

15.  В порядке убывания вывести все целые числа из диапазона 1..4900, которые представимы в виде n^2+2k^2, но не представимы в виде 7ij+j+3 (n, k, i, j >= 0).

16.  В возрастающем порядке вывести все целые числа из диапазона 1..10000, представимые в виде n2 + m2, где n, m >= 0.

17.  Дан текст, за которым следует точка. В алфавитном порядке вывести (по разу) все строчные русские гласные буквы, входящие в этот текст.

18.  Дан текст из строчных латинских букв, за которым следует точка. Вывести все буквы, входящие в текст не менее двух раз.

19.  Дан текст из строчных латинских букв, за которым следует точка. Вывести все буквы, входящие в текст по одному разу.

20.  type nat= 1..10000; Описать функцию digits( n ), подсчитывающую количество различных значащих цифр в десятичной записи натурального числа n.

21.  type nat= 1..10000; Описать функцию print( n ), выводящую в возрастающем порядке все цифры, не входящие в десятичную запись натурального числа n.

22.  Дан текст из цифр и строчных латинских букв, за которым следует точка. Определить, каких букв √ гласных (a, e, i, o, u) или согласных √ больше в этом тексте.

23.  const n= 10; type number= 1..n; matrix= array [number, number] of real; num= set of number; Описать функцию sum( A, s1, s2 ), вычисляющую сумму тех элементов матрицы A, номера строк которых принадлежат соответственно непустым множествам s1 и s2 типа num.

24.  type letters= set of ▒a▓..▓z▓; Описать процедуру print( A ), печатающую в алфавитном порядке все элемента множества A, имеющего тип letters.

25.  type M= set of 0..99; Описать функцию card( A ), подсчитывающую количество элементов в множестве A типа M.

26.  type month= 1..12; Описать функцию days( m ), определяющую количество дней в месяце m (невисокосного года).

27.  Дано 100 целых чисел от 1 до 50. Определить, сколько среди них чисел Фибоначчи.

28.  Дано 100 целых чисел от 1 до 50. Определить, сколько среди них чисел, первая значащая цифра в десятичной записи которых 1 или 2.

29.  Описать функцию count( s ), подсчитывающую общее количество цифр, входящих в строку s.

30.  Описать функцию count( s ), подсчитывающую общее количество знаков ▒+▓, ▒-▒ и ▒*▓, входящих в строку s.