Текст книги "Песни о Паскале (СИ)"

Автор книги: Олег Деревенец

сообщить о нарушении

Текущая страница: 12 (всего у книги 29 страниц)

var A, B : Extended;

...

if A = B then …       { это ненадежное сравнение }

if Abs(A-B) < 0.001 then … { надежное сравнение с точностью 0.001}

Во втором сравнении переменные A и B считаются одинаковыми, если отличаются менее чем на одну тысячную. Как видите, знаком равенства тут и не пахнет. К слову, функция Abs возвращает абсолютное значение аргумента, – ведь здесь надо получить положительное значение разности. Выражение Abs(A-B) в математике пишется так: |A-B|.

Типы данных пользователя

Богатый арсенал типов данных, запасенный в Паскале, кажется достаточным на все случаи жизни. Скоро вы убедитесь, что это не так. Но Паскаль разрешает программисту создавать свои собственные типы данных, заточенные под определенную задачу. Их называют пользовательскими типами, и строят на основе все тех же базовых типов Паскаля. Рассмотрим пример.

Предположим, ваша программа содержит много переменных типа Integer. Но, по ходу работы над проектом, вы решили заменить этот тип чисел на какой-то иной, например на Longint или даже Extended. Такую замену можно сделать редактором текста, тщательно порывшись в программе и найдя все места, где объявлены переменные. Но можно сделать лучше – объявить собственный тип данных.

Для объявления пользовательских типов в Паскале служит секция описания типов, которая начинается с ключевого слова TYPE – «тип». Внутри секции можно объявить один или несколько типов данных пользователя. Так, например, вы можете объявить свой тип на базе встроенного типа Integer.

Type TValue = Integer;

Здесь объявлен тип данных по имени TValue (Value – «значение»), он равнозначен типу Integer. Как видите, объявление типа схоже с объявлением константы. Только справа от знака равенства следует не значение, а описание типа.

Имя пользовательского типа придумывают по общим правилам для имен. В свое время мы учредили префиксы для констант и аргументов процедур, – префиксы делают программу понятней. Для констант мы договорились применять префикс «C», для аргументов процедур и функций – префикс «a». Для типов возьмем префикс «T» (от слова Type). Повторяю: префиксы – это всего лишь добровольное соглашение программистов, а не требование языка.

Теперь, когда тип TValue объявлен, его можно использовать для объявления переменных, например:

Type TValue = Integer;

Var A, B, C : TValue;

      ...

      Readln(A, B);

      C:= A+B;

Если со временем потребуется изменить типы переменных A, B и C на тип Longint, то мы исправим лишь объявление пользовательского типа.

Type TValue = Longint;

И после компиляции все переменные типа TValue примут тип Longint.

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

Совместимость и преобразование типов

Поздравляю! Теперь вам знакомы все простые типы данных – солдаты нашей армии. Сражаясь в едином строю, они будут передавать при необходимости данные друг другу. Такая передача данных должна подчиняться определенным правилам. Они просты, но заставляют программиста всякий раз задуматься: то ли я делаю? А это придает программам надежность.

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

Целое и целое

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

Var B: Byte; I: Integer; W: Word; L: Longint;

      ...

      { Эти операторы не вызовут нарушения границ диапазонов }

      I:= B;       W:=B;       L:= W;       L:=I;

      { Эти операторы могут повлечь нарушения диапазонов }

      B:=I;       I:=W;       W:=L;

Когда число N не помещается в переменной, то в неё попадает лишь младшая часть числа N (т.е. остаток от деления N mod 256 или N mod 65536).

Целое и символ

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

      Writeln ( Ord(’D’) );       { 68 }

      Writeln ( Char(68) );       { D }

Как видите, число в символ преобразуется через имя типа Char. Это общий прием, волшебная палочка для обращений типов данных. Например, булевых.

Целое и булево

Превратить булево в целое можно все той же функцией Ord.

      Writeln ( Ord(False) );       { 0 }

      Writeln ( Ord(True) );       { 1 }

А для обратного превращения воспользоваться именем типа Boolean.

      Writeln ( Boolean(0) );       { False }

      Writeln ( Boolean(1) );       { True }

Целое и перечисление

Вернемся к перечислению месяцев, вымышленному нами в предыдущей главе, где переменная была объявлена так:

var m : (Jan,Feb,Mar,Apr,May,Jun,Jul,Aug,Sep,Oct,Nov,Dec);

Превратить значение такой переменной в число можно функцией Ord. А наоборот? Пока нам этого не удавалось. Но после объявления пользовательского типа данных задача решается очень просто.

Type TMonth = (Jan,Feb,Mar,Apr,May,Jun,Jul,Aug,Sep,Oct,Nov,Dec);

Var m : TMonth;

      ...

      m:= 3;       { это ошибка }

      m:= TMonth(3); { это равнозначно m:= Apr (счет идет от нуля) }

Здесь объявлен пользовательский перечислимый тип TMonth (Month – «месяц»), далее вы вольны применять его и для объявления переменных, и для преобразования типов. Вот где проявляется сила пользовательского типа!

Вещественное и вещественное

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

Целое и вещественное

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

      Writeln ( Trunc(3.75) ); { 3 }

      Writeln ( Round(3.75) ); { 4 }

      Writeln ( Round(3.25) ); { 3 }

Напоследок рассмотрите рис. 76, где показана общая картина совместимости и преобразования простых типов данных.

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

Размеры переменных и типов данных

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

Type TMonth = (Jan,Feb,Mar,Apr,May,Jun,Jul,Aug,Sep,Oct,Nov,Dec);

Var m : TMonth;

      ...

      Writeln ( SizeOf(m) );             { 1 }

      Writeln ( SizeOf(TMonth) );       { 1 }

      Writeln ( SizeOf(Integer) );       { 2 }

      Writeln ( SizeOf(Extended) );       { 10 }

Рис.76 – Совместимость и преобразования типов

Я обозвал SizeOf псевдофункцией за то, что никаких вычислений она не делает, – результат вычисляется при компиляции программы. Ведь компилятор сам «знает» объём памяти, занимаемой любым типом данных, и подставляет в программу уже готовое число.

Псевдофункция SizeOf удобна, и вдобавок улучшает переносимость программ. Например, в разных режимах компиляции Free Pascal и в разных компиляторах размер типа Integer может отличаться (2 или 4 байта). Применяя функцию SizeOf, вам не придется задумываться об этом и менять вручную одни числа на другие, – компилятор сделает это за вас.

Итоги

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

• Тип Extended предпочтительней использовать для вычислений, тип Single – для хранения больших объёмов данных в памяти и на диске.

• Вещественные числа печатаются либо в форме с плавающей точкой, либо в форме с фиксированной точкой.

• Вещественные числа, в отличие от целых, – приближенные. Сравнивать их между собой можно лишь с некоторой точностью.

• Вещественным переменным разрешено присваивать целые значения, при этом преобразование типов происходит автоматически.

• Целым переменным нельзя присвоить вещественные значения непосредственно, для этого используют либо функцию отсечения дробной части Trunc, либо функцию округления Round.

• Порядковые типы данных допускают взаимное преобразование посредством псевдофункций, имена которых совпадают с именами типов данных.

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

• Размер памяти, занимаемый переменной любого типа, определяют псевдофункцией SizeOf. Её применение снижает зависимость программы от особенностей компиляторов и компьютерных платформ.

А слабо?

А) Напишите две функции, округляющие вещественное число:

• до большего значения (например: 3.1 –> 4; 3.9 –> 4);

• до меньшего значения (например: 3.1 –> 3; 3.9 –> 3).

Б) Ваша процедура принимает строковую переменную, вычисляет среднее арифметическое кодов её символов и печатает его с двумя цифрами после точки.

В) Напечатайте с тремя знаками после точки 20 случайных вещественных чисел в диапазоне от 0 до 10. Подсказка: для формирования дробных чисел можно делить случайное число на другое число, например, Random(10000)/1000.

Г) Напечатайте с тремя знаками после точки 20 случайных чисел в диапазоне от 0 до 10 так, чтобы числа следовали по возрастанию. Подсказка: сравнивайте очередное число с предыдущим.

Д) Программа для подсчета стоимости покупок. Для каждой покупки пользователь вводит два действительных числа: вес покупки и цену за 1 кг в рублях. Признак завершения ввода данных – нулевой вес. Программа должна напечатать общую стоимость с точностью до копейки (два знака после точки) с округлением в большую сторону. Проверьте результат на калькуляторе.

Е) Квадратный корень. Квадрат – это равносторонний прямоугольник, его площадь вычисляется по формуле S=D•D, где D – сторона квадрата. А когда площадь S известна, и надо определить сторону D? Тогда из S извлекают квадратный корень (обозначается символом V). Так, если S=9, то D=V9=3.

Для извлечения корня в Паскале есть функция SQRT. Напишите собственную функцию MySQRT, прибегнув к методу последовательных приближений. В грубом, нулевом приближении примем D₀=1. Последующее, более точные значения D будем вычислять по формуле

D_i+1 = (D_i + S/D_i)/2

Так, при S=9 получим D₁=(1+9/1)/2= 5, D₂=(5+9/5)/2= 3.4 и так далее, пока абсолютная разность между двумя последовательными значениями D станет пренебрежимо мала. Функция MySQRT должна принять число и вычислить его корень с точностью 0.0001. Внутри функции напечатайте промежуточные значения D. Подсказка: для D_i и D_i+1 вам потребуются лишь две локальные переменные.

Ж) В тесто кладут четырех главных ингредиента: муку, сахар, яичный порошок и молоко. Все это смешивается в пропорции, заданной рецептом. Например, рецепт 100:5:7:500 означает, что на 100 граммов муки кладут 5 граммов сахара, 7 граммов яичного порошка и 500 граммов молока. У пекаря есть некоторое количество всех ингредиентов, и он хочет замесить из них максимально возможное количество теста, соблюдая рецепт. Ваша программа должна ввести:

• Рецепт – это 4 целых числа.

• Исходное количество ингредиентов – это 4 действительных числа.

Программа должна напечатать:

• Общее количество полученного теста с точностью два знака после точки.

• Остатки ингредиентов – 4 числа с точностью два знака после точки.

Глава 34

Структура программы

В этой главе мы рассмотрим структуру программы, и завершим тем самым боевое построение нашего войска, начатое в 32-й главе.

Управляющие структуры

Управляющие структуры составляют основу языков программирования. Ключевых структур всего три:

• линейная последовательность – это естественный порядок выполнения операторов друг за другом, то есть слева направо и сверху вниз;

• альтернатива – выбор одного из двух или нескольких направлений исполнения операторов;

• цикл – повторное исполнение операторов до соблюдения некоторого условия.

Альтернатива и цикл представлены в Паскале несколькими операторами, из которых программист выбирает тот, что лучше подходит к решаемой задаче (рис. 77).

Рис.77 – Управляющие структуры языка Паскаль

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

• неполный условный оператор IF-THEN;

• полный условный оператор IF-THEN-ELSE;

• оператор выбора CASE-OF-ELSE-END.

Для организации циклов программист также применяет три оператора:

• цикл с проверкой условия в конце REPEAT-UNTIL;

• цикл с проверкой условия в начале WHILE-DO;

• цикл со счетчиком FOR-TO-DO и FOR-DOWNTO-DO.

Обратите внимание на условия продолжения циклов WHILE-DO и REPEAT-UNTIL, – они взаимно противоположны! Первый из них выполняется, пока условие истинно, а второй – пока оно ложно.

Странно, что из этих немногих структур лепятся столь сложные программы!

Структура программы

Программа на Паскале состоит из ряда секций (Section – «часть», «раздел»). Под структурой программы будем понимать взаимное положение этих секций. На рис. 78 показана упрощенная структура программы.

Рис.78 – Структура программы на языке Паскаль

Каждую секцию открывает своё ключевое слово. Три секции: Const, Type и Var – образуют описательную часть программы. Здесь компилятор черпает информацию о размещении данных в памяти. Секции с описаниями процедур и функций и главная программа формируют исполнительную часть, – здесь содержатся исполняемые операторы (секция кода). Все секции, кроме главной программы, необязательны. Но, при необходимости, секции могут повторяться и чередоваться в любом порядке, соблюдая два простых правила:

• любой объект программы – будь то константа, тип, переменная или процедура – объявляется до своего применения;

• главная программа располагается в тексте последней (хотя исполнение начинается именно с нее!).

Два слова о точке с запятой (;). В описательной и в исполнительной частях программы её назначение слегка различается. Если в объявлениях точка с запятой завершает оператор и обязательна, то в секции кода она разделяет операторы и не нужна за последним оператором блока.

Структура процедур и функций

Процедуры и функции – основные строительные блоки программ, в крупных проектах их сотни. Главная программа обычно содержит несколько операторов, а основная работа отдается процедурам и функциям. Такой подход не только упрощает разработку, отладку и понимание программ, но и существенно уменьшает их размер (объём занимаемой памяти). Всё, что требует алгоритм, достигается вызовом одних процедур и функций из тела других, – то есть применением вложенных вызовов. Глубина вложения таких «матрешек» практически не ограничена. Опытный программист обычно разбивает большую программу на ряд мелких и простых процедур и функций.

Внутренняя структура процедур и функций схожа со структурой программы. Это своего рода программы в программе, потому их и называют подпрограммами. На рис. 79 показана упрощенная структура процедуры с условным именем ABC.

Рис.79 – Структура процедуры

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

• любой объект объявляется до своего применения;

• тело процедуры или функции обязательно и размещается последним.

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

Обмен данными с подпрограммами

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

• через глобальные переменные;

• через параметры процедур и функций;

• возвратом результата через имя функции.

Передача данных через глобальные переменные кажется самой простой, – ведь эти переменные видны из многих частей программы. Но этот способ оправдан лишь в небольших проектах. С ростом размера и сложности программы все труднее отслеживать взаимные влияния её частей через глобальные переменные. Это запутывает программу и снижает её надежность.

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

Табл. 4 – Три способа передачи данных через параметры

Способ передачи данных

Пример заголовка процедуры

Пример вызова

По значению

:в процедуру передается значение параметра.

Procedure ABC (arg:integer);

ABC(10);ABC(X+3);

По ссылке

CONST:В процедуру передается ссылка на константу или переменную, содержащую данные.

Procedure ABC (const arg:integer);

ABC(10);ABC(X);

По ссылке

VAR:В процедуру передается ссылка на переменную, содержащую данные.

Procedure ABC (var arg:integer);

ABC(X)

Опытного программиста отличает умение эффективно передавать данные; табл. 5 поможет вам выбрать наиболее удачный способ такой передачи.

Табл. 5 – Рекомендуемые способы передачи данных

Куда передавать данные

Рекомендуемый способ

Только в процедуру или функцию

1) По значению (простые типы) 2) По ссылке CONST (сложные типы)

Только из процедуры и функции

1) Через имя функции (одно значение) 2) По ссылке VAR (несколько значений)

В обоих направлениях

По ссылке VAR (любые данные)

В каждом случае предпочтительный способ указан первым. Данные простых типов лучше передавать внутрь подпрограмм по значению. По ссылке CONST передают строки и другие сложные типы данных (скоро мы изучим их). Через имя функции возвращают лишь один результат. А если надо вернуть несколько результатов, или вернуть сложный тип данных, используют ссылки VAR.

Встроенные процедуры и функции

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

Текстовые файлы

Напоследок напомню об основных средствах обработки текстовых файлов.

Для чтения из файлов применяют следующие процедуры и функции:

Assign(F, ...) – Связать файловую переменную с файлом

Reset(F) – Открыть файл для чтения

Read(F, ...) – Прочитать часть строки файла

Readln(F, ...) – Прочитать строку файла и перейти к следующей

Eoln(F) – Проверить на конец строки

Eof(F) – Проверить на конец файла

Close(F) – Закрыть файл

Для записи в файл применяют такие процедуры:

Assign(F, ...) – Связать файловую переменную с файлом

Rewrite(F) – Открыть файл для записи

Write(F, ...) – Записать часть строки файла

Writeln(F, ...) – Записать строку файла и перейти к следующей

Close(F) – Закрыть файл

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

var F_In, F_Out : Text;

begin

Assign(F_In,’’); Reset(F); { F_In связали с клавиатурой }

Assign(F_Out,’’); Rewrite(F); { F_Out связали с экраном }

. . .

end.

Второй приём заключается в применении специального имени «CON» – от слова Console (оно предусмотрено в MS-DOS и Windows).

Assign(F_In,’Con’); Reset(F); { F_In связали с клавиатурой }

Assign(F_Out,’Con’); Rewrite(F); { F_Out связали с экраном }

В операционных системах MS-DOS и Windows существует несколько специальных имен файлов, вот некоторые из них:

AUX – Первый асинхронный коммуникационный порт

CON – Клавиатура и экран (CONsole)

NUL – Фиктивное устройство (для тестирования)

PRN – Первый параллельный принтер

Аналогичные имена применяют и в UNIX-подобных системах.

Наконец, для действий с текстовыми файлами можно применять две встроенные в язык файловые переменные: INPUT и OUTPUT. Они не нуждаются ни в объявлении, ни в открытии, ни в закрытии файлов:

Readln(Input, S); { – то же самое, что Readln(S) }

Writeln(Output, S); { – то же самое, что Writeln(S) }

Файловые переменные INPUT и OUTPUT можно передавать в качестве фактических параметров внутрь процедур и функций, а также связывать их с дисковыми файлами. Вот пример копирования файла из «MyText.in» в «MyText.out»:

var S: string;

begin

Assign(Input,’MyText.in’); Reset(Input);

Assign(Output,’MyText.out’); Rewrite(Output);

While not Eof do begin

Readln(S);

Writeln(S);

end;

Close(Input); Close(Output);

end.

Что дальше?

Мы изучили фундамент языка Паскаль, который составляют простые типы данных и управляющие структуры. Впереди интересные и серьезные проекты, в основе которых лежат сложные типы данных. Вы осилите их, если пройденный материал надежно закрепился в вашей голове. Вы чувствуете это? Нет? Тогда без ложного стыда вернитесь к началу книги, ведь повторение – мать учения!

Итоги

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

• Альтернатива организуется условными операторами и оператором выбора.

• Для циклов в Паскале предусмотрено три оператора: 1) цикл с проверкой в начале, 2) цикл с проверкой в конце и 3) цикл со счетчиком.

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

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

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

• Основная нагрузка по обработке данных возлагается на процедуры и функции – подпрограммы. Из тела одних подпрограмм вызывают другие подпрограммы, – такие вызовы называют вложенными.

• Передачу данных между подпрограммами предпочтительней выполнять через параметры и имена функций.

А слабо?

А) Найдите две ошибки в следующей программе.

var X : TNum;

type TNum = integer;

const A = 10;

begin

X:= A+B;

end.

Б) Напишите булеву функцию Test и программу для её демонстрации. Функция должна проверять, делится ли без остатка первое число на второе, например:

Writeln( Test(20, 4) );       { true }

Writeln( Test(21, 5) );       { false }

В) Напишите целочисленную функцию Division для деления первого числа на второе без применения операции DIV. Вот примеры вызовов:

Writeln( Division(20, 4) );       { 5 }

Writeln( Division(21, 5) );       { 4 }

Подсказка: внутри функции вычитайте второе число из первого. Предотвратите деление на ноль (как результат возвращайте ноль). Сделайте два варианта: 1) деление положительных чисел, 2) деление чисел с учетом знака.

Г) Пусть ваша программа распечатает все множители (кроме единицы) введенного пользователем целого положительного числа, например:

Введите число: 60

2 2 3 5

Д) Напишите функцию для ввода целого числа. Она принимает строку-приглашение и возвращает введенное число, например:

      X:= GetNumber(‘Введите стоимость покупки=’);

Глава 35

Множества

С малых лет я завидовал обладателям волшебных палочек, ковров-самолетов и прочих волшебных штучек! Смел ли я мечтать о таких игрушках? И вот познакомился с Паскалем… Мы приступаем к мощнейшим средствам этого языка – сложным типам данных. Овладейте ими, и мудреные задачи разрешатся сказочно просто!

В директорском кабинете

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

Мы находим усталого Семена Семеновича перед кипой исчерканных листков с фамилиями учеников. Чем озабочен директор? Сейчас объясню. В начале учебного года Семен Семенович распорядился, чтобы все ученики вступили в какой-либо кружок или спортивную секцию – по желанию. А теперь, спустя пару месяцев, он проверяет исполнение приказа. Директор намерен наказать тех, кто не исполнил распоряжения, и поощрить состоящих в нескольких кружках или секциях. Но, промучившись неделю со списками кружков, он готов уж отказаться от своей затеи, – задача не поместилась в директорской голове. Судите сами: ведь в школе двести пятьдесят учеников! Спасайте Семена Семеновича!

Первым делом, первым делом – оцифровка

Директорскую задачу поручим компьютеру, а тому сподручней орудовать с числами. Заменим фамилии учеников числами, назначив каждому ученику уникальный, несовпадающий с другими, номер. Переход от фамилий к номерам и обратно – простая задачка, её мы оставим Семену Семеновичу. Таким образом, наш входной файл со списками учеников будет содержать по одной строке для каждого кружка, где перечисляются через пробел номера учеников, состоящих в этом кружке. Вот пример входного файла для трех кружков.

2 11 4 13

9 17 12 11 3 5 18

14 2 13 15 20

Здесь в первый кружок записались 4 школьника, во второй – 7, а в третий – 5 учеников. Как видите, их номера перечислены в произвольном порядке, что затрудняет ручную обработку таких списков. От компьютера требуется выявить номера учеников (от 1 до 250), которых нет в таком файле. Хочется найти простое решение, а оно возможно лишь с применением нового для нас типа данных – множества.

Множества глазами математика

Слово «множество» намекает на большое количество чего-либо. Чего именно? А все равно! Множества придумали математики, а им безразлично, что считать. Так подать сюда математика, и пусть ответит за всех! Скоро явился математик, взял два кружочка – черный и белый – и, протерев свои толстые очки, стал объяснять. Вот суть его речи.

Рис. 80 – Множества точек черного (B) и белого (W) кругов

Вы полагаете, что это кружочки? Нет, друзья, это два множества точек, – одно принадлежит черному кругу, другое – белому. Обозначим первое из них латинской буквой B (от Black – «черный»), а второе буквой W (от White – «белый»). Итак, черные и белые точки этих кружков назовём элементами множеств. Сколько там этих точек? Доказано, что бесконечно много, но к свойствам множеств это не имеет отношения. Что же это за свойства?

Добавление к множеству существующих элементов

Покройте черный круг таким же или меньшим черным кругом, или почеркайте его углем, – заметите разницу? Если на белый круг наложить такой же, или почеркать его мелом, – тоже не увидите изменений. Значит, множество не изменится при добавлении к нему элементов, уже входящих в это множество. На языке математики это свойство выразится так:

B + B = B

или так:

W + W + W = W

Не правда ли, странная арифметика?

Объединение множеств

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

Рис. 81 – Объединение непересекающихся множеств G = B + W

Так мы получили новое множество, представляющее сумму или объединение двух предыдущих. Обозначим это новое множество буквой G (от Gray – «серый») и выразим то, что сделали, формулой.

G = B + W

Очевидно, что число точек во вновь образованном множестве равно их сумме в двух исходных. Пока в этом нет ничего интересного, – ведь исходные множества B и W, как говорят математики, не пересекаются. Сблизим круги так, чтобы добиться их частичного перекрытия (рис. 82).

Рис.82 – Объединение пересекающихся множеств G < B + W

Теперь количество точек в объединенном множестве будет меньше, чем в двух исходных по отдельности.

G < B + W

В общем случае при объединении множеств (как пересекающихся, так и не пересекающихся) соблюдается правило.

G ≤ B + W

Пересечение множеств

Иногда математиков (и не только их) интересует область пересечения множеств, отметим её серым цветом (рис. 83).

Рис.83 – Пересечение множеств G = B * W

Операцию пересечения множеств обозначают знаком умножения.

G = B • W

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

B • W ≤ B и B • W ≤ W

Вычитание множеств

О солнечных и лунных затмениях слышали все, а кто-то и наблюдал их. Для математика это зримые примеры вычитания множеств; взгляните на рис. 84 – чем не затмения? Серую область можно трактовать как результат вычитания одного круга из другого. На левом рисунке белый круг «отгрыз» часть черного, превратив его в серую область, а на правом – наоборот. Подобающие этим случаям формулы будут таковы.

G = B – W или G = W – B

Рис.84 – Вычитание множеств

А если вычитаемый круг окажется больше того, из которого вычитают, и полностью поглотит его? В алгебре разность получится отрицательной, а здесь? Ничего подобного! При вычитании большего множества из меньшего или равного ему получается пустое множество, оно обозначается символом Ø. Из пустого множества тоже можно вычитать, и результатом опять будет пустое множество.