355 500 произведений, 25 200 авторов.

Электронная библиотека книг » Олег Деревенец » Песни о Паскале (СИ) » Текст книги (страница 13)
Песни о Паскале (СИ)
  • Текст добавлен: 6 ноября 2017, 03:30

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


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


Жанр:

   

Драматургия


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

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

(B – B) – B = Ø

(Ø – W) – B = Ø

Вот такими интересными свойствами обладают множества!

Подмножества и надмножества

На рис. 85 белый круг полностью поглощен черным. Тогда говорят, что множество точек белого круга составляет подмножество точек черного. Или так: множество точек черного круга является надмножеством точек белого. Математик выразит это формулой:

B > W


Рис.85 Надмножество (B) и подмножество (W)

А если круги совпадают и полностью перекрывают друг друга? Тогда говорят, что множества равны, и любое из них является и подмножеством, и надмножеством другого. В общем случае:

если B ≥ W, то B является надмножеством W;

если B ≤ W, то B является подмножеством W.

Числовые множества

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


Рис.86 – Множества чисел

Так мы получили два конечных множества чисел. Одно из них, обозначенное буквой A, содержит числа 8, 7, 9, 3, 5, 2. Другое обозначено буквой B и включает числа 5, 4, 6, 1, 2. Эти множества математики записали бы так:

A = { 8, 7, 9, 3, 5, 2 }

B = { 5, 4, 6, 1, 2 }

Для записи множеств они используют фигурные скобки. Обратите внимание: числа в скобках следуют в произвольном порядке. Это значит, что порядок перечисления элементов множества не важен. Учтите также, что числа 2 и 5 входят в оба множества.

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

A + { 8, 7 } = A

Множество A после объединения с множеством {8,7} не изменилось, поскольку уже содержало эти числа.

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

Объединение множеств содержит все числа исходных множеств, при этом повторения (дубликаты) отбрасывают:

G = A + B = { 8, 7, 9, 3, 5, 2 } + { 5, 4, 6, 1, 2 } = { 8, 7, 9, 3, 5, 2, 4, 6, 1 }

Хотя числа 2 и 5 входили в оба исходных множества, в объединении они встречаются по разу.

Пересечение множеств содержит только числа, входящие в оба множества:

A * B = { 8, 7, 9, 3, 5, 2 } * { 5, 4, 6, 1, 2 } = { 5, 2 }

Разность множеств A–B содержит числа, состоящие в множестве A, но отсутствующие в множестве B:

A – B = { 8, 7, 9, 3, 5, 2 } – { 5, 4, 6, 1, 2 } = { 8, 7, 9, 3 }

Разность множеств B–A содержит числа, состоящие в множестве B, но отсутствующие в множестве A:

B – A = { 5, 4, 6, 1, 2 } – { 8, 7, 9, 3, 5, 2 } = { 4, 6, 1 }

Эти «вычисления» легко проверить по рис. 86.

Мощность множества, полные и неполные множества

Мощность множества – это наибольшее количество элементов, которое может содержаться в нём. В нашем числовом примере мощность множества равна девяти.

Множество, содержащее все возможные свои элементы, называют полным. В нашем случае полным является объединение множеств A+B.

Множество, содержащее не все возможные элементы, является неполным. Так, множества A и B по отдельности – неполные.

Все это рассказал нам математик. А что же Семен Семенович, или мы забыли о директоре? Нет, конечно, но к директорской задаче мы вернемся после ознакомления с «паскалевскими» множествами.

Итоги

• Множество – это совокупность различимых объектов (точек, чисел, предметов), которую мы воспринимаем как нечто целое. Отдельные объекты множества называют его элементами.

• К множествам применим ряд операций: объединение, пересечение, вычитание, сравнение.

• Объединение двух множеств содержит по одному элементу из каждого исходного множества.

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

• Разность множеств содержит элементы уменьшаемого множества за исключением элементов вычитаемого множества.

• Первое множество является подмножеством второго, если все элементы первого принадлежат второму. И тогда второе множество будет надмножеством первого. Множества совпадают, если содержат одни и те же элементы.

А слабо?

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

• Пересекается ли множество легковых автомобилей с множеством грузовых? А множество желтых автомобилей с множеством черных?

• Может ли быть непустым пересечение множества желтых автомобилей с множеством автобусов?

• Свидетель дорожно-транспортного происшествия сообщил, что с места преступления скрылся грузовой автомобиль синего цвета. Как вычислить группу подозреваемых автомобилей?

• На улице висит знак: грузовым проезд запрещен. Как определить множество автомобилей, въезд которым разрешен?

Б) Два государства, назовем их A и B, спорят о некой территории, – каждое считает ее своей. Нарисуйте на листочке предполагаемую карту, заштрихуйте спорную область, а затем объясните:

• Как вычислить спорную область государств?

• Как вычислить бесспорную область, включая оба государства?

• Заштрихуйте область, отвечающую формуле G = (A-B) + (B-A).

• Заштрихуйте область, отвечающую формуле G = A+B – A•B. Совпадает ли она с той, что вычислена по предыдущей формуле?

В) Дайте ответы на следующие вопросы.

• Является ли множество ваших одноклассников подмножеством учеников вашей школы?

• Пересекается ли множество ваших друзей с множеством ваших одноклассников?

• Является ли множество ваших друзей подмножеством ваших одноклассников?

Глава 36

Множества в Паскале

Зная силу математических множеств, Никлаус Вирт – «отец» языка Паскаль – ввел в язык тип данных множество и предусмотрел операции с ним.

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

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

Множества объявляются конструкцией вида

SET OF <диапазон или тип>

Вот примеры объявления переменных типа множество.

      { объявление множества } { возможные элементы множества }

var SN1 : set of 10..100;       { числа от 10 до 100 }

      SN2 : set of byte;       { числа от 0 до 255 }

      SC1 : set of ’a’..’z’;       { только малые латинские буквы }

      SC2 : set of Char;       { все символы }

Поскольку мощность множеств в Паскале не превышает 256, множества SET OF BYTE и SET OF CHAR представляют множества предельной мощности.

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

Переменным типа множество присваивают значения выражений того же типа, вот примеры таких операторов.

      SN1:= [10, 20, 50];       { содержит три элемента }

      SN2:= [11..20, 51..60];       { содержит 20 элементов }

      SN2:= [0..255];       { содержит 256 элементов от 0 до 255 }

      SN2:= SN1;       { копия другого множества }

      SC1:= [’z’, ’y’, ’x’];       { содержит три элемента }

      SC2:= [’0’..’9’];       { содержит 10 элементов }

Как видите, для записи множеств в Паскале используют квадратные скобки, а не фигурные. Что позволено в записи множеств, и что запрещено?

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

SN1:= [5..8];       { множество задано диапазоном }

SN1:= [8, 7, 6, 5]; { то же множество, но в другом порядке }

SN1:= [5..8, 6, 6]; { трижды указано число 6, дубликаты будут отброшены }

Множеству любого типа можно присвоить пустое значение, например:

SB1:= []; SN1:= [];       SC1:= [];

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

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

var k, n : byte;       c: char;

      ...

      k:= 10; n:= 20;

      SN1:= [1..k, n+5];       { 1..10, 25 }

      c:= ’m’;

      SC1:= [c, ’a’, ’b’];       { ’m’, ’a’, ’b’ }

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

SN1:= [5..200];       { в объявлении SN1 указан диапазон от 10 до 100 }

SC1:= [’a’, ’b’, 5]; { вместо символа ’5’ указано число 5 }


Операции с множествами

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

Вычислительные операции – объединение, пересечение и вычитание – записывают на Паскале так:

      SN2:= [3, 7] + [5, 2];       { объединение = [2, 3, 5, 7] }

      SN2:= [2..10] * [8..20]; { пересечение = [8, 9, 10] }

      SN2:= [2..10] – [8..20]; { разность = [2..7] }

Множества, объединенные знаками операций и круглыми скобками, образуют выражение, например:

      SN2:= (SN1 + [0..15]) * SN2;

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

      SN1:= SN1 + K;       { сложение множества с числом – ошибка }

Правильно будет так:

      SN1:= SN1 + [ K ];       { добавляется множество из одного элемента }

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

Сравнение множеств

Множества можно сравнивать между собой, получая в результате булево значение – TRUE или FALSE.

Два множества равны, если содержат одни и те же элементы.

if SN1 = SN2       then … else …

Множества неравны, если одно из них содержит, хотя бы один элемент, которого нет в другом.

if SN1 <> [15, 17, 19] then … else …

Проверка на подмножество (<=) отвечает на вопрос: все ли элементы первого множества входят во второе?

if SN1 <= SN2 then … else …

Проверкой на надмножество (>=) выясняют, все ли элементы второго множества входят в первое.

if SN1 >= SN2 then … else …


Проверка на вхождение элемента в множество (операция IN)

Входит ли некоторый элемент в множество? Это можно выяснить так:

var N : byte; S : set of byte;

      ...

      if ([N] * S) <> [] then { N входит в S } else { не входит }

Понятно, что, если число N входит в множество S, то пересечение [N]*S не будет пустым. Но проще выяснить это операцией IN – она введена специально для этого. Операция дает TRUE, если значение перечислимого типа входит в данное множество, например:

      if N in S then { N входит в S } else { не входит }

      if 20 in S then { 20 входит в S } else { не входит }


Решение директорской задачи

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

2 11 4 13

9 17 12 11 3 5 18

14 2 13 15 20

Надо составить список нигде не числящихся разгильдяев.

Можно ли воспринимать эти списки как множества? Вероятно, да, судите сами:

• каждый список содержит номер ученика не более одного раза (ошибочные повторные записи все равно отбросят);

• порядок следования в списке не важен;

• список может быть пустым (если никто не записался в этот кружок).

Хорошо, а будет ли множеством список всех учеников школы? Конечно. Такое множество будет полным, поскольку содержит все возможные элементы. А раз так, директорскую задачку решим через множества.

Множество тех, кто записался хотя бы в один кружок, найдем объединением отдельных множеств-кружков (S1 + S2 + S3). Вычтя это объединение из полного множества учеников, получим множество уклонившихся. Вот и все решение! На Паскале это запишется так:

var R, S1, S2, S3 : set of 1..250;

begin

      S1:= [ 2, 11, 4, 13 ];       { 1-й кружок }

      S2:= [ 9, 17, 12, 11, 3, 5, 18 ]; { 2-й кружок }

      S3:= [ 14, 2, 13, 15, 20 ];       { 3-й кружок }

      R:= [1..250] – (S1 + S2 + S3); { R – множество уклонившихся }

end.

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

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

Итоги

• Множества – это инструмент, взятый в Паскаль из математики.

• В Паскале применяют конечные множества, элементами которых могут быть числа, символы и булевы значения. Мощность множеств в Паскале не превышает 256.

• В Паскале предусмотрен ряд операций с множествами: объединение, пересечение, вычитание, сравнение, а также проверка на вхождение элемента в множество.

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

• Операция IN – удобное средство для проверки вхождения одного элемента в множество, она тоже дает булев результат.

А слабо?

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

type TNumbers = set of 1..300;

      TChars = set of char;

      TBytes = set of byte;

var c1, c2 : TChars;

      b1, b2 : TBytes;

begin

      c1:= [1..9];

      c2:= ['1'..'9'];

      c2:= c2 + ’0’;

      c2:= c2 + [0];

      b1:= c1;

      b2:= b1 + [1,7,3];

      Writeln(b1=b2);

      Writeln(1 in b2);

      Writeln([1] in b2);

      Writeln(b1 in b2);

end.

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

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

Глава 37

Ввод и вывод множеств

Мы узнали о множествах и приспособили их к директорской задаче. Чтобы покончить с нею доделаем ещё пару пустяков: организуем ввод и вывод множеств. Для ввода-вывода строк и простых типов данных годятся процедуры Read[ln] и Write[ln]. Но сейчас все не так просто, – эти процедуры не способны работать, ни с множествами, ни с другими сложными типами данных. Однако ж «нормальные герои всегда идут в обход», – пойдем так и на этот раз.

Вывод множества в текстовый файл

Начнем с вывода числового множества на экран (или в файл, – что одно и то же). Так мы получим средство для последующей проверки вводимых множеств.

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

{ P_37_1 – вывод множества в файл }

type TSet = set of 1..255;       { объявление типа «множество» }

      {– Процедура вывода множества в файл –}

procedure WriteSet(var aFile: text; const aSet : TSet);

var k : integer;

begin

      for k:=1 to 255 do       { цикл по всем элементам множества}

      if k in aSet       { если K входит в множество }

      then Write(aFile, k:4);       { печатаем в строке }

      Writeln(aFile); { по окончании – переход на следующую строку }

end;

      {– Программа для проверки процедуры WriteSet –}

var S1 : TSet;       F: text;

begin

      Assign(F, ''); Rewrite(F); { связываем файл с экраном! }

      S1:= [3, 10, 25];       { значение множества }

      WriteSet(F, S1);             { печатаем }

      Readln;

      Close(F);

end.

В первой строке объявлен тип данных TSet, он может содержать целые числа от 1 до 255. Процедура распечатки WriteSet принимает по ссылке два параметра: файловую переменную и множество, которое надо распечатать. Внутри процедуры работает цикл FOR, перебирающий все возможные элементы множества. Те из них, что содержатся в нём, печатаются в текущей строке. По завершении цикла оператор Writeln переводит позицию записи на следующую строку файла.

Обратите внимание: множество передано в процедуру по ссылке CONST. Передача в процедуры множеств, строк и других сложных типов данных по ссылкам CONST и VAR – это обычная практика. Так повышается скорость работы программ и уменьшается объём памяти, занимаемый параметрами.

Теперь взгляните на оператор Assign(F,''), который назначает файловой переменной пустое имя файла. Так файловая переменная связывается с экраном дисплея (при выводе данных), либо с клавиатурой (при вводе). А когда вам потребуется вывести результаты в дисковый файл, достаточно будет задать нужное имя файла, не меняя процедуры WriteSet (этот прием – подстановка пустого имени – не работает в Pascal ABCNet).

Примечание. В современные версии Паскаля (Delphi) для обработки множеств введён вариант цикла FOR-IN-DO. С ним распечатка множества станет ещё проще:

      for k in aSet do Write(aFile, k:4);


Ввод множества из текстового файла.

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

{ P_37_2 – ввод и вывод числового множества }

type TSet = set of 1..255; { объявление типа «множество» }

      {– Процедура чтения множества из файла –}

procedure ReadSet(var aFile: text; var aSet : TSet);

var k : integer;

begin

aSet:= [];

      While not Eoln(aFile) do begin { пока не конец строки }

      Read(aFile, K);       { читаем очередное число }

      aSet:= aSet+[K];       { и добавляем к множеству }

      end;

      Readln (aFile);       { переход на следующую строку }

end;

      {– Процедура распечатки множества в файл –}

procedure WriteSet(var aFile: text; const aSet : TSet);

var k : integer;

begin

      for k:=1 to 255 do       { цикл по всем элементам множества}

      if k in aSet       { если входит в множество }

      then Write(aFile, k:4); { печатаем в строке }

      Writeln(aFile);       { по окончании переход на следующую строку }

end;

      {– Программа для проверки процедуры ввода –}

var S1 : TSet;       F, D: text;

begin

      Assign(F, ''); Rewrite(F); { вывод на экран }

      Assign(D, ''); Reset(D); { ввод с клавиатуры }

      S1:= [];       { перед вводом опустошаем множество }

      ReadSet(D, S1);       { вводим множество из файла }

      WriteSet(F, S1); Readln; { распечатаем для проверки }

      Close(F); Close(D);

end.

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

Директорская задача, первый вариант

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

      R:= [1..250] – (S1 + S2 + S3);

Теперь добавим ввод и вывод множеств. Чтобы не занимать место повторами показанных ранее процедур, я представлю решение в целом.

{ P_37_3 – решение директорской задачи, вариант 1 }

const CMax = 20;       { мощность множества, реально 250 }

type TSet = set of 1..CMax; { объявление типа «множество» }

procedure WriteSet(var aFile: text; const aSet : TSet);

{ взять из P_37_2 }

procedure ReadSet(var aFile: text; var aSet : TSet);

{ взять из P_37_2 }

var R, S1, S2, S3 : TSet;

      FileIn, FileOut: text;

begin {– Главная программа –}

      { Открытие входного файла }

      Assign(FileIn, 'P_37_3.in'); Reset(FileIn);

      { Создание выходного файла }

      Assign(FileOut, 'P_37_3.out'); Rewrite(FileOut);

      { Ввод множеств из входного файла }

      S1:=[]; ReadSet(FileIn, S1);

      S2:=[]; ReadSet(FileIn, S2);

      S3:=[]; ReadSet(FileIn, S3);

      R:= [1..CMax] – (S1+S2+S3); { Решение }

      WriteSet(FileOut, R);       { Вывод решения в выходной файл }

      Close(FileIn); Close(FileOut);

end.

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

2 11 4 13

9 17 12 11 3 5 18

14 2 13 15 20

А в выходной файл попали следующие числа.

1 6 7 8 10 16 19

Легко убедиться в том, что никто из этих учеников не состоит в кружках.

Директорская задача, второй вариант

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

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

20

2 11 4 13

9 17 12 11 3 5 18

14 2 13 15 20

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

{ P_37_4 – решение директорской задачи, вариант 2 }

type TSet = set of byte; { объявление типа «множество» }

{ Здесь надо поместить процедуры ввода и вывода множеств }

procedure WriteSet(var aFile: text; const aSet : TSet);

{ взять из P_37_2 }

procedure ReadSet(var aFile: text; var aSet : TSet);

{ взять из P_37_2 }

var R, S : TSet;

      FileIn, FileOut: text;

      N: integer; { общее число учеников }

begin

      Assign(FileIn, ' P_37_4.in'); Reset(FileIn);

      Assign(FileOut, ' P_37_4,out'); Rewrite(FileOut);

      Readln(FileIn, N);       { читаем общее число учеников }

      S:= []; { очищаем перед вводом }

      { пока не конец файла, объединяем участников всех кружков }

      while not Eof (FileIn) do ReadSet(FileIn, S);

      R:= [1..N] – S;       { Решение }

      WriteSet(FileOut, R);

      Close(FileIn); Close(FileOut);

end.

Согласитесь, программа стала и гибче, и проще. Однако к первому её варианту мы ещё вернемся.

Итоги

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

• Вывод (распечатка) множества выполняется циклом со счетчиком, внутри которого проверяется вхождение каждого элемента в множество.

• Ввод множества из текстового файла основан на операции объединения по отдельности прочитанных элементов.

А слабо?

А) Напишите процедуры для ввода и вывода множества символов. Можно ли здесь для счетчика цикла применить символьную переменную?

Б) Напишите функцию, принимающую числовое множество и возвращающую количество содержащихся в нём элементов.

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

Г) Напишите две функции, принимающие строку и возвращающие:

• строку, в которой символы исходной строки встречаются лишь по разу и следуют в алфавитном порядке, например «PASCAL» –> «ACLPS»;

• то же, но порядок следования символов такой же, как в исходной строке, например «PASCAL» –> «PASCL».

Глава 38

Множества в «бою»

Множества, множества… – заполучив столь острое оружие, удержимся ли не пустить его в ход? Вот ещё несколько задач, – мы изрубим их в капусту!

Активисты, шаг вперед!

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

Положим для простоты, что в школе лишь три кружка, их списки представлены множествами S1, S2 и S3. Выявить тех, кто состоит одновременно в кружках S1 и S2 легко, – достаточно найти пересечение S1*S2. Точно так же поступим с другими парами: S1 и S3, S2 и S3. Объединив все три пересечения, мы выявим интересующих нас школяров. Итак, решение задачи выразится формулой.

      R := S1*S2 + S1*S3 + S2*S3;

Попадут ли в это множество ученики, состоящие во всех трех кружках? Если да, то, как их отделить от прочих? Придумайте, как выявить тех, кто состоит:

• в трех кружках:

• в двух кружках и не более;

• только в одном из кружков.

Надеюсь, что с этим проектом, назовем его «P_38_1», вы справитесь сами, желаю успеха!

Подвиг контрразведчика

Контрразведка некоторого государства обнаружила утечку информации из лабораторий секретного учреждения. Для поимки шпиона позвали сыщика Шерлока Ивановича Холмского. Первым делом, он попросил списки сотрудников лабораторий. Лаборатории именовались латинскими буквами: «A», «B», «C» и так далее, причем некоторые сотрудники допускались в несколько лабораторий. Шерлок Иванович оцифровал списки, заменив фамилии сотрудников их табельными номерами, то есть, уникальными числами. Затем сгруппировал эти числа по лабораториям и составил табл. 6.

Табл. 6 – Исходные данные для «вычисления» завербованного сотрудника

Лабо–ратория

Номера сотрудников, допущенных в лабораторию

A

1 2 4 5 9 11 13 15 22 23 24 25 27 30 31 37 41 42 43 44 45 46 48 50 51 56 64 70 72 73 74 75 76 77 82 84 86 87 89 92 95 97 98 101 102 103 104 105 106 107 108 111 113 116 117 118 124 125 127 130 132 133 134 138 143 144 145 147 149 150

B

16 21 22 23 24 25 26 27 28 29 31 33 35 37 39 41 44 47 49 50 51 52 54 55 56 57 59 61 62 65 66 69 70 71 72 77 78 79 81 83 84 85 91 92 93 94 95 96 98 100 101 103 107 108 109 112 113 115 117 118 119 121 122 124 129

C

1 3 5 9 12 19 22 25 33 34 41 42 46 50 52 55 56 57 58 59 61 66 69 72 80 81 82 84 87 88 94 97 99 100 101 102 112 119 121 123 125 129 134 137 138 139 149 152 153 154 155 157 158 165 166 168 171 172 180 184 185 190 193 194 198 199 205 213 216 220

D

5 6 7 8 9 10 11 12 13 14 16 18 21 22 23 24 27 28 29 30 31 32 34 35 38 40 41 42 43 44 45 46 47 48 51 52 53 54 55 57 58 59 60 61 62 63 64 65 66 67 70 71 73 74 75 76 78 79 80 81 82 84 85 86 88 89 91 92 93 94 95 96 97 98 99 100 104 105 106 107 108 111 112 113 115 116 117 118 119 120

E

10 15 16 26 33 40 42 44 50 53 65 67 74 79 82 83 85 87 90 91 93 99 106 108 110 120 121 124 125 132 135 146 148 149 151 156 157 158 163 166 168 169 171 175 183 184 189 195 197 205 206 207 216 220 221 225 226 227 241 244

F

8 12 21 25 26 29 30 31 34 48 49 50 52 55 59 60 62 70 71 73 83 85 90 91 92 93 94 96 97 99 100 102 103 104 105 106 108 119 121 122 124 127 128 130 132 141 142 144 156 160 165 166 169 171 173 176 179 191 192 195 199 200 207 209 220 221 222 224 226 229 233 234 236 239 240

G

23 24 26 27 29 30 35 36 41 42 44 45 46 49 52 55 56 58 60 61 63 64 65 68 72 74 76 77 81 82 86 87 88 90 93 94 95 96 97 98 100 101 102 107 108 109 112 113 114 115 117 120 123 127 132 133 135 137 138 143 145 146 147 150 152 155 156 159 161 162 163 164 165 168 170 172 177 178 179 180

H

15 17 19 20 21 22 23 26 28 29 30 32 33 34 36 38 41 42 44 45 46 48 49 52 57 60 62 65 66 68 73 74 77 78 83 84 85 88 89 90 91 92 95 96 97 98 99 100 101 102 103 104 107 108 115 116 118 127 128 129 130 131 134 135 136 137 139 145 146 150 151 152 154 157 160 161 164 166 167 172 173 177 178 179 180 182 185 188 189 190 193 195 197 204 207

Дальнейшее разбирательство показало, что утечка секретов случалась только из лабораторий «A», «D», «G» и «H» (в таблице они выделены серым цветом). При этом секреты остальных лабораторий («B», «C», «E» и «F») остались нетронутыми. Это направило дедуктивную мысль в правильное русло.

«Очевидно, – рассуждал Шерлок Иванович, – шпионить может тот, кто допущен в «дырявые» лаборатории. Из этого круга исключим тех, кто работает в нетронутых лабораториях, иначе их секреты тоже стали бы известны». Рассудив так, Шерлок Иванович достал ноутбук, и через 30 минут агент был вычислен, – подозреваемым оказался сотрудник с номером 45. Установленная за ним слежка подтвердила подозрение, и шпион был задержан.

Слабо ли вам повторить подвиг контрразведчика? Воспроизведите программу, написанную Шерлоком Ивановичем, я подскажу вам только её первую строку.

{ P_38_2 – подвиг контрразведчика }


В тридевятом царстве

Это случилось на затерянном в океане материке, что носил на себе несколько царств-государств. Жители материка – те ещё скряги – тратили для названий своих стран всего по одной букве: «A», «B», «C» и так далее. И мы будем их так называть. Границами стран служили каналы, специально для того прорытые; каналы были пронумерованы. Некоторые страны выходили к океану, берега которого тоже были пронумерованы и служили границами.

Самым могущественным было царство «A». Однако, ввиду его обширности и частых политических перемен, тамошний государь никак не мог уяснить точные границы своей страны. Он толком не знал даже ближайших соседей, – сведения были самыми разноречивыми. Когда терпение монарха лопнуло, он повелел своим инженерам запустить спутник, который бы исследовал границы и внес ясность в этот вопрос.

Слово царя – закон, и вскоре спутник кружился на орбите. С высоты ясно наблюдались берега океана и каналы, составлявшие границы царств. Рис. 87 показывает то, что «увидел» спутник. Буквами обозначены названия стран, а числами – участки границ. В центре континента темным цветом выделено обширное царство «A». К нему примыкают несколько стран, отмеченные серым, – это его соседи. Страны, примыкающие к царству «A» уголками своих границ, соседями не считаются. Они и все прочие «не соседи» отмечены белым цветом, а вокруг – океан.


    Ваша оценка произведения:

Популярные книги за неделю