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

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

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


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


Жанр:

   

Драматургия


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

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

      procedure Report; virtual;

      end;

implementation

      {– Реализация объекта «ЧЕЛОВЕК» –}

constructor TPerson.Init(aBearing: integer; const aName, aFam : string);

begin

mBearing := aBearing;

mName := aName;

mFam := aFam;

end;

procedure TPerson.Report;

begin

Writeln(mBearing:6, 'Фамилия: '+mFam:20, ' Имя: '+mName);

end;

end.

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

USES Person;

Сохраните новую версию файла под именем «P_61_3» и убедитесь, что она компилируется без ошибок. Затем вставьте в первичный файл приведенное ранее объявление типа для наследника TMilitary. В итоге заготовка будущей программы станет такой.

{ P_61_3 – Демонстрация принципов наследования и полиморфизма }

uses Person;       { Объект TPerson импортируется из модуля Person }

type { объект «ВОЕННОСЛУЖАЩИЙ» }

TMilitary = object (TPerson)

mRank : string; { воинское звание }

constructor Init(aBearing: integer; const aName, aFam, aRank : string);

procedure Report; virtual;

end;

begin

end.

Реализация методов

Отсюда приступим к реализации переопределенных методов нового объекта. Начнем с конструктора. Конечно, он мог бы повторить действия объекта-предка, но это неразумно. Ведь цель объектной технологии – упростить программирование, избежать повторов, не так ли? Избежать повтора здесь очень просто: внутри конструктора наследника вызовем конструктор предка, передав ему нужные параметры.

      TPerson.Init(aBearing, aName, aFam);

Вызов конструктора предка содержит имя этого предка – префикс TPerson. Обращение потомка к методам предка – обычная практика. По этой причине в Паскале учреждено ключевое слово INHERITED – «унаследованный». Если предварить им вызов унаследованного метода, то префикс с именем предка станет излишним.

      inherited Init(aBearing, aName, aFam);

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

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

constructor TMilitary.Init(aBearing: integer; const aName, aFam,

      aRank : string);

begin

      inherited Init(aBearing, aName, aFam); { вызов метода предка }

      mRank:= aRank;

end;

Переходим к методу Report наследника. Здесь, вдобавок к прочим данным, надо распечатать ещё и воинское звание. Прочие данные распечатаем унаследованным методом Report, а воинское звание – дополнительным оператором печати. Вы уже догадались, что реализация метода будет такова.

procedure TMilitary.Report;

begin

      inherited Report;       { вызов метода предка }

      Writeln('Воинское звание: '+mRank);

end;

Породив «военного человека», возьмёмся за мирное строительство, создадим объект, исполняющий роль гражданского служащего. Назовем его TCivil, а род его пойдет от того же предка TPerson. У гражданских своя гордость и своя служебная лестница, ступеньки которой – категории – нумеруются числами. Хранить информацию о карьерном росте будем в числовом поле, назовем его mLevel – «уровень». Так же, как и для военного, нам придется дополнить конструктор объекта и метод распечатки Report. Ход рассуждений будет прежним, а потому не буду повторять его, сделайте эту работу сами.

Сотворив наследников «человека» – объекты TMilitary и TCivil, мы почти разобрались в механизме наследования. А где же полиморфизм? В чем он проявляется? Для ответа обратимся к динамическим объектам.

Динамические объекты

Динамические переменные знакомы нам с 52-й главы. Указатели на объекты ничем не отличаются от таковых для других типов данных. Например, указатель на тип TPerson объявляется так:

type PPerson = ^TPerson;

Теперь можно объявить переменную этого типа, взять для неё память в куче, а затем инициализировать поля конструктором.

var P : PPerson;       { указатель на объект }

begin

      New(P);       { выделение памяти в куче }

      P^.Init(1985, 'Иван', 'Грозный'); { инициализация объекта }

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

      P:= New(PPerson, Init(1985, 'Иван', 'Грозный'));

Обратите внимание, что первый параметр функции – это тип-указатель PPerson, а не тип объекта TPerson!

Примечание. В языке Delphi и совместимом с ним режиме Free Pascal применяют иной синтаксис вызова конструктора, например:

var P : TPerson;       { это указатель на объект! }

...

P:= TPerson.Init(1985, 'Иван', 'Грозный'); { создается динамический объект }

Дело в том, что все объекты в Delphi – это динамические переменные, и переменная типа TPerson является указателем на объект. Для создания таких объектов применяют не функцию New, а вызов конструктора с префиксом, совпадающим с названием типа объекта.

Полиморфизм

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

var P1 : PPerson; { указатель на предка }

      P2 : PMilitary; { указатель на потомка }

      P3 : PCivil;       { указатель на потомка }

Здесь P1 является указателем на предка, а P2 и P3 – на разных его потомков. Отчасти полиморфизм состоит в том, что указателю на предка разрешено присваивать указатели на любого его потомка, то есть следующие операторы не вызовут протеста компилятора.

      P1:= P2;

      P1:= P3;

Скажете, пустая формальность? Зря вы так! Воистину здесь скрыт глубокий смысл, поскольку через указатель на предка можно вызывать методы его потомков. Но при условии, что эти методы унаследованы от предка как виртуальные. Так, в следующем примере указателю P1 трижды присваиваются указатели на объекты разных типов: сначала на предка TPerson, а затем на двух его потомков, после чего всякий раз вызывается виртуальный метод Report. Но в реальности происходит вызов трех разных методов Report – соответственно типу объекта, на который в текущий момент ссылается указатель P1. Так срабатывает механика полиморфизма!

      P1:= New(PPerson, Init(1985, 'Иван', 'Грозный'));

      P1^.Report;       { вызывается TPerson.Report }

      P1:= New(PCivil, Init(1995, 'Мария', 'Рыбкина', 12));

      P1^.Report;       { вызывается TCivil.Report }

      P1:= New(PMilitary, Init(1985, 'Андрей', 'Быков', 'Майор'));

      P1^.Report;       { вызывается TMilitary.Report }

Кажется, что полиморфизм одушевляет объект и делает его умнее: объект сам «понимает», как ему исполнить то, или иное желание программиста. Тот лишь вызывает нужный метод, не вникая в детали. Это похоже на управление телевизором или другим прибором. Стоит подать напряжение, и все они включатся: хоть и по-разному, но каждый по-своему правильно.

Но мощная механика полиморфизма срабатывает лишь для родственных объектов, состоящих в отношении предок-потомок. Именно в таких отношениях находятся созданные нами объекты. А вот пример иного рода.

type TA = object

      constructor Init;

      procedure Report; virtual;

      end;

      TB = object

      constructor Init;

      procedure Report; virtual;

      end;

Здесь объявлены два типа объектов с одноименными виртуальными методами. Но полиморфизмом тут и не пахнет, поскольку объекты не родственны меж собой!

В завершение темы изучите программу «P_61_3», где собрано все, что было сказано о «человечьих» объектах.

{ P_61_3 – Демонстрация принципов наследования и полиморфизма }

uses Person;       { Объект TPerson импортируется из модуля Person }

type PMilitary = ^TMilitary; { указатель на объект «ВОЕННОСЛУЖАЩИЙ» }

      TMilitary = object (TPerson)

      mRank : string; { воинское звание }

      constructor Init(aBearing: integer; const aName, aFam,

      aRank : string);

      procedure Report; virtual;

      end;

      PCivil = ^TCivil; { указатель на объект «ГРАЖДАНСКИЙ СЛУЖАЩИЙ» }

      TCivil = object (TPerson)

      mLevel : integer;       { должностная категория }

      constructor Init(aBearing: integer; const aName, aFam : string;

      aLevel: integer);

      procedure Report; virtual;

      end;

      {– Реализация объекта «ВОЕННОСЛУЖАЩИЙ» –}

constructor TMilitary.Init(aBearing: integer; const aName, aFam,

      aRank : string);

begin

inherited Init(aBearing, aName, aFam);

mRank:= aRank;

end;

procedure TMilitary.Report;

begin

inherited Report;

Writeln('Звание: '+mRank);

end;

      {– Реализация объекта «ГРАЖДАНСКИЙ СЛУЖАЩИЙ» –}

constructor TCivil.Init(aBearing: integer; const aName, aFam : string;

      aLevel: integer);

begin

inherited Init(aBearing, aName, aFam);

mLevel:= aLevel;

end;

procedure TCivil.Report;

begin

inherited Report;

Writeln('Категория: ', mLevel);

end;

var Persons : array[1..3] of PPerson; { массив указателей на ПРЕДКА }

i : integer;

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

{ Массив заполняется объектами РАЗНЫХ, но родственных типов }

Persons[1]:= New(PPerson, Init(1985, 'Иван', 'Семенов'));

Persons[2]:= New(PCivil, Init(1995, 'Мария', 'Рыбкина', 12));

Persons[3]:= New(PMilitary, Init(1985, 'Андрей', 'Быков', 'Майор'));

{ В ходе распечатки вызывается метод ФАКТИЧЕСКОГО объекта }

for i:=1 to 3 do Persons[i]^.Report;

Readln;

end.


Сокрытие полей и методов

Объяснять ли вам, из чего строят современные программы? Из сотен «умных» объектов, которые образуют ветвистую иерархию родственных связей, открывающую простор полиморфизму.

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

Схожий прием используют и в объектном программировании. Поля и методы, доступ к которым наследникам не нужен, прячут в объекте-предке так, что они становятся невидимыми за пределами предка. И тогда спрятанные имена можно использовать в наследниках повторно по иному назначению. Не будет ли здесь путаницы? Нет, поскольку методы предка не знают о новых именах и обращаются к старым. А методы наследника не видят старых имен и обращаются к новым. Разумеется, что разработчик объекта-предка тщательно отбирает те поля и методы, что потребуются создателям потомков.

Сокрытие имен объекта организовано очень просто: в объявление объекта вставляют ключевые слова PRIVATE (личный) и PUBLIC (общедоступный). Эти слова разбивают объявление объекта на две части – приватную и общедоступную, например:

type TParent = object       { объект–предок }

      private

      A, B : integer;

      function Calc(arg: integer): integer;

      public

      Constructor Init(a, b : integer)

      function GetSum: integer; virtual;

      end;

Здесь поля A и B, а также функция Calc, скрыты от взоров потомков. Поэтому программист, импортировавший объект типа TParent, может спокойно добавить в него свои поля или методы с теми же самыми именами, например, так:

type TChild = object (TParent) { объект–наследник }

      A, B : string;

      procedure Calc;

      ...

      end;

Здесь в потомке поля A и B имеют другой тип, а имя Calc принадлежит не функции, а процедуре. Но и сейчас поля и методы предка с этими же именами все ещё существуют! Но доступны только предку, вот и все.

А если в объявлении объекта не указаны ключевые слова PRIVATE и PUBLIC? Тогда все его поля и методы по умолчанию будут общедоступными.

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

Итоги

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

• Объект – это сложный тип данных, совмещающий в себе собственно данные и процедуры, обрабатывающие их.

• Объектно-ориентированное программирование основано на трех дополняющих друг друга механизмах: инкапсуляции, наследовании и полиморфизме.

• Инкапсуляция – это объединение данных и процедур, их обрабатывающих, в едином объекте.

• Наследование позволяет создавать новые типы объектов на базе существующих. Так создается иерархия родственных объектов.

• Полиморфизм состоит в схожем поведении объектов родственных типов.

А слабо?

А) Разработайте иерархию «человечьих» объектов в соответствии со следующим рисунком (новые типы объектов выделены цветом).

Дайте новым типам объектов подходящие имена, дополните их надлежащими полями, переопределите конструкторы и метод Report. Затем исследуйте механизм полиморфизма на предке и всех его потомках.

Б) Мощность множеств в Паскале не превышает 256, и часто этого бывает недостаточно. Сконструируем свой тип множеств, назовем его TBigSet, мощность которого составит 65536 (соответствует диапазону для типа Word). Оформим это множество как объект.

type

TSetArray = array [0..4096] of word; { хранит 65536 бит (4096*16) }

PSetArray = ^ TSetArray; { тип-указатель на массив }

TBigSet = object

      mArray : PSetArray; { указатель на динамический массив }

      Constructor Init; { создает динамический массив mArray )

      Destructor Done; { освобождает память, занятую массивом }

      procedure ClearAll; { опустошает множество }

      procedure SetAll; { делает множество полным }

      procedure Insert(N); { вставляет элемент N в множество }

      procedure Delete(N); { удаляет элемент N из множества }

      function Member(N):Boolean; { проверяет принадлежность N к множеству }

      function IsEmpty:Boolean; { проверяет пустоту множества }

      procedure Union(BS: TBigSet); { добавляет другое множество }

      procedure InterSect(BS: TBigSet); { формирует пересечение множеств }

      procedure Load(var F: text); { вводит множество из файла }

      procedure Save(var F: text); { выводит множество в текстовый файл }

end;

Примените здесь сведения из главы 48, а также идеи из задачи 49-В (глава 49). Так, включение в множество и исключение из него элемента N может быть выполнено установкой и сбросом бита в массиве mArray^.

      mArray^[N div 16]:= mArray^[N div 16] or (1 shl (N mod 16))

      mArray^[N div 16]:= mArray^[N div 16] and not (1 shl (N mod 16))

Объединение с другим множеством Union(BS:TBigSet) можно сделать логическим суммированием массивов:

for I:=0 to 4095 do mArray^[ I ]:= mArray1^[ I ] or BS.mArray^[ I ]

И так далее. Напишите реализацию всех методов объекта и примените его к решету Эратосфена и прочим задачам из главы 38.

Глава 62

Самое интересное только начинается!

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

Крупицы мастерства

Чем зарабатывает программист? – создает программы. У хорошего мастера дело спорится, и товар его добротен. Как скорее достичь мастерства? За что браться, с чего начать? Вот несколько советов.

Постигайте языки программирования

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

А что другие языки? Среди них отметим Си – один из самых используемых. Но почему не Паскаль?

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

По мере того, как компьютеры становились мощнее, а программы сложнее, требования к их надежности возросли – ошибки программистов крайне дороги! Сторонники Си осознали необходимость типизации данных и прочих мер повышения надежности и позаимствовали эти идеи из Паскаля. С другой стороны слишком суровый контроль типов в Паскале был слегка ослаблен – в разумных пределах. Это и другие новшества, добавили языку гибкости, и Паскаль пробился в области, где безраздельно хозяйничал Си. Нынешние потомки Паскаля – языки Ada и Modula – применяют для создания надежных, ответственных программ (авиация, космос, вооружения). Но это секрет, о котором «настольные» программисты не знают, и для них C/C++ – «языки профессионалов». Впрочем, в «настольном» программировании эти языки все ещё востребованы, хотя и вытесняются где-то более современными Java и C#.

Ещё одна популярная сфера – разработка сайтов. Тем, кто углубится в WEB-программирование, пригодятся PHP, Perl, JavaScript, Pyton и другие WEB-языки (они все плодятся и плодятся!).

Особняком от «толпы» языков программирования держится Ассемблер (Assembler переводится как «сборщик»). Его относят к языкам низкого уровня, – в отличие от Паскаля, Си и многих других, причисляемых к языкам высокого уровня. За что же так «унижен» Ассемблер? За то, что оперирует с потрохами процессора: адресами памяти, регистрами, флагами. Программирующий на Ассемблере должен хорошо представлять устройство компьютера и процессора, – на низком уровне нужна высокая квалификация! Ассемблер – удел профессионалов, и к нему прибегают там, где другие языки не годятся.

Технологии – не упускайте их из виду!

Изучая современные языки, вы постигните и технологии разработки крупных проектов: модульное и объектное программирование. И это не все. Технологии не стоят на месте, и новинки стремительно сменяют одна другую. Держите «руку на пульсе», следите за развитием технологий, – кто зазевался, тот отстал!

Изучайте типовые алгоритмы и структуры данных

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

Расширяйте кругозор

Программист, не «въезжающий» в решаемую задачу, – самое жалкое существо на свете! Увы, такие бедолаги – не редкость, и на то есть причины, – ведь компьютеры распространились повсеместно, где их только нет!

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

Угождайте пользователю

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

Проверяйте входные данные

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

Тщательно тестируйте свои творения

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

Комментируйте свои действия

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

Мы нередко возвращаемся к готовой программе спустя месяцы и годы после ее внедрения. За это время забывается почти все, что придумали. А если вашу программу будет править кто-то другой… – я не завидую этому парню! И здесь вновь выручат комментарии.

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

• C – для констант;

• T – для типов данных;

• a – для аргументов процедур и функций;

• m – для полей записей и объектов.

Переменным лучше давать имена существительных, а для процедур и функций подходят глаголы. Глобальным переменным предпочтительно давать длинные развернутые имена. Наоборот, локальные переменные, назначение которых очевидно (счетчики циклов, временные значения и тому подобное), лучше называть коротко – одной-двумя буквами.

«Вылизывайте» структуру программы

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

Программисты, на старт!

По многим школьным предметам проводят олимпиады, в том числе по информатике. Цель этих олимпиад – выявить самых способных. Профильные факультеты ВУЗов с удовольствием принимают победителей олимпиад на льготных условиях. Ради этого можно постараться, не так ли? Если вам это интересно, я открою некоторые тайны олимпиад по информатике.

Этапы и участники олимпиад

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

Участники соревнуются в двух возрастных группах: старшей (11-й класс), и младшей (10-й класс и моложе). В отличие от олимпиад по прочим предметам, программисты обеих возрастных групп решают одни и те же задачи. На ранних этапах каждая возрастная группа оценивается отдельно. А вот на всероссийском и международном этапах все возрасты оценивают вместе, и чемпионом может стать любой. Не смущайтесь своих юных лет. Чуете в себе силы? Так смело врубайтесь в скопище бойцов!

Определение победителей и призеров

Обычно «олимпийцам» предлагают решить несколько задач, и для каждой из них следует написать программу. Разумеется, что время на решение ограничено (обычно это от 3 до 5 часов на все задачи). По истечении этого времени судьи приступают к тестированию программ. Тесты приготовлены заранее, но неизвестны участникам. Каждую программу проверяют на нескольких тестах, а баллы начисляют за каждый успешно выполненный тест. Щедрость теста зависит от его сложности и сложности решаемой задачи. В конце концов, побеждает тот, кто наберет больше баллов.

Олимпиады программистов отличает ещё одна особенность: для проверки решений здесь применяют тестирующие программы. Они автоматически компилируют исходный текст, а затем несколько раз запускают исполняемый файл, передавая ему всякий раз условия очередного теста. Это ускоряет проверку работ и придает ей объективность. Тестирующие программы применяют на областном и последующих этапах.

Организация туров

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

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

И вот соревновательный тур настал: билеты с условиями задач розданы, часы включены. В течение тура участник может задавать жюри вопросы для устранения неясностей в условиях задач. Вопросы задают только в письменной форме (другие участники их слышать не должны!) и формулируют так, чтобы ответом было «да» или «нет». Нельзя, например, спросить, в каких пределах находится число N, но можно выяснить, является ли это число положительным («да» или «нет»?).

По окончании тура, участники покидают рабочие места, и начинается официальное тестирование их решений. Решение задачи – это исходный файл на выбранном языке (обычно на Паскале или Си). Тесты запускают в присутствии участника с использованием упомянутой тестирующей системы. Успешное решение должно компилироваться и выдавать правильные решения на предлагаемые тесты. Если тест не проходит, соответствующие ему баллы не начисляются. Жюри не рассматривает исходный текст как таковой, его интересуют лишь правильность прохождения тестов. Участник вправе опротестовать результат тестирования, если, по его мнению, на это есть основания (например, ошибка в тестовых данных). Протест подается в жюри в письменной форме. Жюри рассматривает все протесты и принимает своё решение. По окончании тестирования и рассмотрения протестов, жюри подводит официальные итоги, объявляя победителей и призеров олимпиады.

Олимпиадные задачи

Как выглядит олимпиадная задача? – пример найдете в приложении М. В чем особенности таких задач?

Прежде всего, отметим способ ввода и вывода данных. То и другое выполняется только через текстовые файлы, которым присваивают заранее оговоренные имена. Так, если для файла с решением оговорено имя «ABC.PAS», то входной файл будет называться «ABC.IN» а выходной – «ABC.OUT». На эти расширения имен рассчитаны упомянутые тестирующие системы.

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

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

Таковы особенности олимпиад по информатике, теперь обсудим подготовку к ним.

Подготовка к олимпиаде

Предметные олимпиады – это ступень на лестнице профессионального роста. Советы программисту-ремесленнику отчасти годятся и «спортсмену». И все же в олимпиадном программировании есть свои особенности.

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

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

Табл. 13 – Некоторые ресурсы Сети по олимпиадному программированию

Ресурс

Ссылка

Алгоритмы

http://algolist.manual.ru

Алгоритмы

http://bestalgorithm.ru

Олимпиады по программированию


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

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