Egorova1

var <имя переменной типа множества>:<имя типа множества> 2) сокращенное описание:

var <имя переменной типа множества>:set of<базовый тип>

Базовый тип, или тип компонент множества, может быть любым простым типом, кроме REAL и INTEGER (диапазон INTEGER допустим, максимальный диапазон [0..255]).

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

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

Пример 3. Имеем следующие описания переменных типа множества: var A,B:set of 0..9;

Тогда допустимы, например, следующие присваивания для построения множества: a:=[0,1,2,3,4,5]; a:=[9,4,5,6]; b:=[7,8].

Порядок следования компонент ([7,8] или [8,7]) несущественен. Первое присваивание можно записать короче, используя интервальную форму записи: a:=[0..5], второе - a:=[9,4..6]. В качестве компонент можно использовать выражения. Так, набор [3*2-1..2*4+1] эквивалентен набору [5..9]. Если окажется, что для [i..j] имеем i>j, то такое множество интерпретируется как пустое; если i=j - как множество, содержащее один элемент i.

Пример 4. Рассмотрим следующий фрагмент программы. type days=(Mon,Tue,Wed,Thu,Fri); { Дни недели }

Результатом выполнения оператора присваивания 1 будет множество d, определяемое отрезком дней недели со вторника Tue по четверг Thu, то есть множество d будет состоять из трёх элементов: Tue, Wed, Thu, что можно выразить и явно в виде: d:=[Tue,Wed,Thu].

В правой части оператора присваивания 2 стоит множество, заданное отрезком дней недели с пятницы по вторник. На первый взгляд, здесь нет ошибки, так как порядок следования элементов для множеств не имеет значения. Однако при задании отрезка этот порядок важен. В базовом типе days установлено, что Fri (пятница) идёт после Tue (вторника), поэтому множество d1 "от пятницы до вторника" пусто. Таким образом, после выполнения оператора 2 во множестве d1 вообще не окажется элементов. Такое множество называется пустым, или нуль-множеством, и обозначается пустыми квадратными скобками: [ ]. Таким образом, оператор 2 можно было коротко записать в виде: d:=[ ].

Итак, конструктор множества [X..Y] и отрезок порядкового типа X..Y не одно и то же: если X>Y, то в случае конструктора имеем пустое множество, а в случае отрезка компилятор зарегистрирует ошибку.

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

var a:set of 0..9; n1,n2:integer;

121

n1:=5; n2:=2; a:=[n1,3,n2];

Замечание. Паскаль допускает множества только из ограниченного числа элементов. Для Турбо-Паскаля число элементов множества не может быть больше 256. Поэтому просто INTEGER не может быть базовым типом множества, только диапазон INTEGER может быть базовым типом. Далее, почему такое ограничение - 256 элементов? Дело в том, что каждый элемент множества занимает 1 бит , и в системе Турбо-Паскаль под множество отводится 32 байта. Set-переменная фактически хранит не сами значения базового типа, а всего лишь бинарную информацию о каждом таком значении - есть оно во множестве или нет. Ещё одно ограничение - значения элементов множества не должны выходить за интервал 0..255. Поэтому отрицательные числа как элементы множества не приемлемы. Для множеств, содержащих знаки char, подобные затруднения не возникают, так как для типа char существует ровно 256 значений (знаков), и их порядковые номера как раз укладываются в числовой диапазон от 0 до 255.

6.2.2Операции с переменными типа set

Кпеременным типа set применимы следующие операции:

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

Пример. [1,3]=[3,1] [1]<>[2] [1..3]=[3,2,1]

[1,2,3]=[1,4,3] Это выражение даёт результат false 2. Операции ">=" и "<="

Используются для проверки принадлежности (вхождения) одного множества другому: если множество A содержится во множестве B , то A<=B даёт true.

Пример. Выражение [1,2]<=[1,2,3] даёт результат true.

Пустое множество содержится во всех множествах, то есть выражение [ ]<=[B] всегда даёт результат true.

3. Операция "in"

Используется для определения принадлежности некоторого значения множеству. Общий вид операции in:

X in A,

где X - величина (выражение) базового типа, A - множество.

Выполнение операции in: если X входит в A, то выражение "X in A" истинно, иначе - ложно.

Пример 1. Выражение [1] in [1,2] даёт результат true. Выражение [1] in [2,3] даёт результат false.

Пример 2. Пусть C - цифра. С помощью операции in можно проверить, является ли она чётной или нечётной и провести соответствующую обработку.

if C in [0,2,4,6,8] then <обработка чётной информации> else <обработка нечётной информации>

Пример 3. Множества часто используют для упрощения сложных операторов if: длинная запись

if (t=0) or (t=32) or (t=212) or (t=30) then...

эквивалентна более короткой записи if t in [0,32,212,30] then...

Пример 4. Печать элементов множества выполняется обычно с использованием операции in:

122

program pechmn(i,o); const n=30;

var P: set of 2..n; m: integer;

begin

(* Формирование множества Р *)

M

(* Печать элементов множества Р *) for m:=2 to n do

if m in P then writeln(m);

M

Замечание. Результат операции in может быть неопределённым в некоторых случаях, например:

var A: set of 1..50; x: integer;

M x:=55;

Вэтом случае операция "x in A" не всегда дает результат false.

4.Операции "+", "-", "*"

Кпеременным A и B типа set, относящимся к одному и тому же конкретному типу, применимы операции:

"+" - объединение; "-" - дополнение; "*" - пересечение.

A+B - это множество элементов, принадлежащих или A, или B, или и A, и B (одинаковые элементы не повторяются).

A*B - это множество элементов, одновременно принадлежащих и A, и B. A-B - это множество элементов, которые есть в A, но отсутствуют в B. Пример.

Выражение [1,3]+[1,4] даёт в результате множество [1,3,4]. Выражение [1,3]*[1,4] даёт в результате множество [1]. Выражение [1,3]-[1,4] даёт в результате множество [3].

Операция A:=A+x добавляет элемент x к множеству A; если x уже имелся в A, то множество A не меняется. Операция A:=A-x исключает элемент x из множества A; если x отсутствовал в A, то множество A не меняется.

6.2.3 Пример использования множества

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

простые числа в интервале [2,n].

Дано: n - integer, n ≥2.

Результат: печать простых чисел, не превосходящих n. Промежуточные данные:

m - очередное простое число: integer; R - множество чисел;

k - число из R: integer.

var n: integer;

R: set of 2..100; m,k: integer;

begin

writeln('введите целое n>=2'); readln(n);

writeln('простые числа, меньшие',n); m:=2;R:=[2..n];

repeat

while not (m in R) do m:=m+1; writeln(m);

k:=m;

while k<=n do begin

R:=R-[k]; k:=k+m;

end until R=[ ]

end.

6.3 ЛАБОРАТОРНАЯ РАБОТА #6 "СТРУКТУРИРОВАННЫЕ ТИПЫ ДАННЫХ"

Цель лабораторной работы "Структурированные типы данных" - закрепить навыки работы с массивами, полученные в предыдущих модулях 4 и 5, получить практический опыт работы с записями, которые широко распространены в программировании, а также познакомиться с множествами.

Задание к лабораторной работе включает в себя две следующие задачи. 1.Разработать программу по работе с массивом записей. Точную формулировку

условия и вариант конкретного задания см. в п.6.3.1.

2.Разработать программу по обработке целочисленной информации, список заданий см. в п.6.3.2. При решении этой задачи можно, по желанию, использовать тип множества, но можно использовать просто массивы, а в некоторых случаях обойтись вообще без структурированных типов данных. Использование множества при выполнении лабораторной работы не требуется однозначно потому, что тип множества не является обязательным и широко распространенным в программировании: любую задачу, где есть множество, можно решить и без понятия множества.

В некоторых заданиях этой работы требуется выделить отдельные цифры целого числа. Подобная задача была рассмотрена в модуле 4, а именно в примере 15 в п.4.3.3.

124

6.3.1 Записи

ЗАДАНИЕ. Выполнить на ЭВМ программу с использованием типа данных "запись" по одному из указанных ниже вариантов.

ПОЯСНЕНИЕ. Дано расписание движения самолетов. Расписание представляет собой массив записей. Каждая запись содержит информацию об одном рейсе в виде:

−номер рейса,

−тип самолета,

−конечный пункт назначения,

−список дней вылета через запятую,

−время вылета,

−время прилета,

−цена билета.

N1.

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

Пример. Определить наиболее подходящий рейс в Москву, улетающий, желательно, в понедельник в 8 утра.

N2.

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

Пример. Определить номер рейса, который более всего подходит пассажиру,

желающему прилететь в Нижний Новгород в воскресение в 19 00

N3.

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

Пример. Определить все рейсы на Москву и Екатеринбург, вылетающие в субботу или воскресенье и прибывающие в пункт назначения не позднее 17 00

N4.

Определить все рейсы до заданного города, которые вылетают в определенные дни в определенном интервале времени.

Пример. Определить все рейсы, вылетающие в воскресенье или в понедельник в г. Омск, время вылета - от 8 00 до 18 00 .

N5.

Определить все рейсы до заданного города, которые вылетают в определенные дни не позднее указанного времени.

Пример. Определить все рейсы, вылетающие в Ставрополь не позднее 12 30 по понедельникам и пятницам.

N6.

Определить все рейсы до заданных городов, которые вылетают в определенный день не позднее указанного времени.

Пример. Определить все рейсы на Нижний Новгород, Москву и Екатеринбург

вылетающие по средам не позднее 12 00 . N7.

Определить все рейсы до заданных городов, которые выполняются в определенный день и на определенном типе самолета.

Пример. Определить все рейсы, выполняемые на самолете ИЛ-86, по субботам, в города Москва, Екатеринбург и Владивосток.

N8.

125

Определить все рейсы, которые проводятся на определенном типе самолета в заданный день и в заданный интервал времени.

Пример. Определить все рейсы, вылетающие из данного аэропорта в

понедельник в интервале времени от 8 00 до 15 30 и проводимые на самолете ТУ-154. N9.

Определить все рейсы, которые выполняются на определенном типе самолета в заданный город и в заданный день.

Пример. Определить все рейсы, выполняемые на самолете ИЛ-86 по субботам в г. Москву.

N10.

Определить все рейсы до заданного города, которые вылетают после определенного часа в определенный день.

Пример. Определить все рейсы, вылетающие во второй половине дня (после

12 00 ) по понедельникам на Москву.

N11.

Определить все рейсы, прибывающие в заданный город не позднее определенного времени и в определенные дни.

Пример. Определить все рейсы, прибывающие в Нижний .Новгород не

позднее 12 00 , по понедельникам и вторникам. N12.

Определить все рейсы, прибывающие в заданный город не позднее определенного времени и в определенный день.

Пример. Определить все рейсы, прибывающие по понедельникам в Москву в

первой половине дня (до 12 00 ). N13.

Определить все рейсы до заданных городов, вылетающие по определенным дням. Пример. Определить все рейсы до Алматы или Бишкека, вылетающие по

средам и пятницам.

N14.

Определить все рейсы до заданного города, вылетающие по определенным дням. Пример. Определить все рейсы до Новосибирска, вылетающие по

понедельникам, субботам и воскресениям. N15.

Определить все рейсы до заданного города, вылетающие в любой день недели до определенного времени.

Пример. Определить все рейсы, вылетающие в первой половине дня в СанктПетербург (в любой день недели).

N16.

Определить все рейсы, которые совершаются в заданные дни на определенном типе самолета.

Пример. Определить, какие рейсы совершаются из данного аэропорта в понедельник и вторник на самолете ТУ-154.

N17.

Определить все рейсы, которые совершаются в указанный день на определенном типе самолета.

Пример. Определить, какие рейсы совершаются в среду на самолете ИЛ-86. N18.

Определить все рейсы, проводимые на определенном типе самолета с ценой билета выше некоторой цены.

Пример. Определить все рейсы, проводимые на самолете ИЛ-86 с ценой билета более 1000 руб.

N19.

126

Определить все рейсы, проводимые на определенном типе самолета с ценой билета не выше некоторой предельной цены.

Пример. Определить все рейсы, совершаемые из данного аэропорта на самолете ТУ-154 с ценой билета не более 1000 руб.

N20.

Определить все рейсы, прибывающие в заданный город не позднее некоторого контрольного времени.

Пример. Определить все рейсы, прибывающие в Симферополь не позднее

12 30 .

N21.

Определить все рейсы, на которые цена билета ниже некоторой контрольной цены. Пример. Определить все рейсы, на которые цена билета менее 800 руб.

6.3.2 Обработка целочисленной информации

ЗАДАНИЕ. Выполнить на ЭВМ программу по одному из нижеследующих заданий.

N1.

Дано множество первых n натуральных чисел. Найти в этом множестве все числа Мерсена. Простое число называется числом Мерсена, если оно может быть представлено

в виде 2 p −1, где р - простое число. N2.

Дано множество натуральных чисел. Выделить из него 4 подмножества чисел,

которые делятся на:

1) 2, 2) 22, 3) 23, 4) 24. N3.

Натуральное число называется совершенным, если оно равно сумме всех своих делителей, за исключением самого себя. Например, число 6 - совершенное, т.к. 6=1+2+3, число 8 - не совершенное, т.к. 8≠1+2+4.

Дано множество первых n натуральных чисел. Получить все совершенные числа, меньшие n.

N4.

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

N5.

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

N6.

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

N7.

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

N8.

Дано множество натуральных чисел. Из него сформировать новое, в котором каждый элемент, будучи переведён в двоичную систему счисления имеет вид 10...01.

N9.

Дано множество натуральных чисел. Найти все числа, делителями которых являются только числа 7,3 и 11.

127

N10.

Дано множество первых n натуральных чисел и натуральное число m. Получить все меньшие n натуральные числа, квадрат суммы цифр которых равен m.

N11.

Дано множество первых n натуральных чисел. Найти в нём все числа такие, что запись их совпадает с последними цифрами записи их квадрата (например, 62=36, 252=625

и т.д.).

N12.

Дано натуральное число n. Выяснить, можно ли представить n! в виде

произведения трёх последовательных целых чисел. Например: 4! = 1 2 3 4 = 24; 24 = 2 3 4.

5! = 1 2 3 4 5 = 120; 120 = 4 5 6.

N13.

Назовём натуральное число палиндромом, если его запись читается одинаково с начала и с конца (как, например, 4884, 393, 1). Найти все меньшие 100 числа-палиндромы, которые при возведении в квадрат также дают палиндромы.

N14.

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

N15.

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

N16.

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

N17.

Два натуральных числа называются дружественными, если каждое из них равно сумме всех делителей другого, кроме самого этого числа. Найти все пары дружественных чисел, лежащих в диапазоне от 200 до300.

N18.

Назовём натуральное число палиндромом, если его запись читается одинаково с начала и с конца (как, например, 4884, 393, 1). Найти все меньшие 100 числа-палиндромы, которые при возведении в квадрат также дают палиндромы.

N19.

Дано натуральное число n. Получить в порядке возрастания n первых натуральных чисел, которые не делятся ни на какие простые числа, кроме 2, 3 и 5.

N20.

Дано множество натуральных чисел. Найти для каждого числа все простые числа, не превосходящие его.

N21.

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

N22.

Дано множество натуральных чисел. Определить, можно ли представить каждое число множества как сумму кубов каких-нибудь трёх натуральных чисел.

N23.

Дано множество натуральных чисел. Найти все числа этого множества, равные сумме кубов своих цифр.

N24.

Дано множество натуральных чисел. Заменить каждое из них на число, которое получается из исходного вычеркиванием чётных цифр (0,2,4,6,8).

128

N25.

Дано множество натуральных чисел. Найти в этом множестве число, которое делится на 2k (k принимает максимально возможное для этого множества значение).

6.4КОНТРОЛЬНЫЕ ВОПРОСЫ И ЗАДАНИЯ ПО МОДУЛЮ 6

6.4.1Что такое запись ? Отличие записи от массива.

6.4.2Объявление переменной типа записи в Паскале. Поле записи. Примеры.

6.4.3Как обратиться к определенному полю записи ? Примеры.

6.4.4Оператор With: назначение, общий вид, примеры использования.

6.4.5Вариантная запись, ее отличие от фиксированной записи. Примеры.

6.4.6Что такое множество ? Отличие множества от массива и записи.

6.4.7Объявление переменной типа множества в Паскале. Базовый тип множества.

6.4.8Присваивание значения переменной типа множества. Конструктор множества.

6.4.9Операции с переменными типа множества: ‘=’, ‘<>’, ‘>=’, ‘<=’, ‘in’, ‘+’, ‘-‘, ‘*’.

129

7 РАБОТА С ПОДПРОГРАММАМИ В ПАСКАЛЕ

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

1)нисходящее проектирование программы (проектирование "сверху-вниз");

2)модульное программирование;

3)структурное кодирование.

Цель изучения данного модуля - познакомиться с основными понятиями модульного программирования, рассмотреть правила оформления модулей (подпрограмм ) в Паскале,

атакже приобрести практический опыт работы с подпрограммами.

7.1МОДУЛЬНОЕ ПРОГРАММИРОВАНИЕ

7.1.1 Понятие модуля

Модульное программирование - это процесс разделения программы на отдельные логические части (модули), и последовательное программирование каждой части. Обычно для решения задачи программист пишет основную (главную) программу и несколько подпрограмм. Для общности программу и подпрограммы называют модулями.

Программу, состоящую только из большого числа операторов, называют монолитной (до этого мы писали только такие программы).

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

Что дает разбиение алгоритма на отдельные модули ?

1.Часто некоторую последовательность действий требуется повторить в нескольких местах программы. Чтобы не копировать одинаковые действия, их можно оформить в виде модуля и записать только один раз. В том месте программы, где должна быть соответствующая последовательность действий, оформляется вызов модуля, то есть указывается его имя и параметры. Итак, модульная структура программы позволяет сократить текст программы.

2.Декомпозиция программы на отдельные модули существенно повышает понятность, читабельность программы (особенно если текст ее сложен и труднообозрим). Такую программу легче и разрабатывать, и модифицировать. Поэтому разбивать большую программу на отдельные модули рекомендуется даже в тех случаях, когда эти модули используются однократно.

3.Разбиение программы на отдельные модули позволяет вести ее разработку коллективу программистов, так как. отдельные модули могут разрабатываться независимо друг от друга.

Модуль - это оформленная по специальным правилам последовательность операторов, реализующая логически завершенную часть алгоритма.

Модуль, в котором записано обращение к другому модулю, называется вызывающим; второй модуль называется вызываемым.

130