Олимпиады: программирование или спорт

В.В.Пупышев

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

Традиционные олимпиады проходят по достаточно стандартной схеме. Участники собираются в определённом месте, ограничиваются во

времени, получают задания. По истечению времени, решения сдаются

жюри. Жюри рассматривает решения и начисляет баллы. Участники, набравшие наибольшее количество баллов, объявляются победителями.

Обычно, время ограничивается 3-5 часами. Часто можно слышать мнение, что олимпиады по программированию – это спорт, имеющий мало общего с настоящим программированием.

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

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

Итак, традиционно при разработке ПО выделяют следующие этапы (подобное разбиение на этапы можно посмотреть в книге [2], но менее детально).

В качестве иллюстрации будем рассматривать задачу о нахождении корней квадратного уравнения (КВУР).

1. Задача. Этот этап предполагает получение задачи. Чаще всего формулировка задачи неточна и противоречива.

Иллюстрация. Найти корни заданного квадратного уравнения.

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

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

Наша иллюстрация очень проста. В жизни часто бывает так, что формальную постановку задачи полностью записать нельзя. Такие задачи называются неформализуемыми (см. [3, 4]).

3. Выбор метода программирования. На этом этапе выбирается метод программирования. Выбирать приходится, поскольку нет единственного универсального метода программирования.

Иллюстрация. Метод программирования КВУР очевиден.

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

4. Алгоритм. Здесь строится алгоритм в терминах предметной области.

Иллюстрация. Алгоритм, в данном случае - формулы для вычисления корней уравнения.

Когда алгоритм построен, можно переходить к его кодированию, т.е.

написать программу.

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

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

Теперь нужно проверить программу на наличие ошибок. Т.е. провести тестирование и перейти к следующему этапу.

6. Отладка. На этом этапе происходит поиск и устранение ошибок, возникших на предыдущих этапах. Часто отладка может быть «размазана» по всем этапам. Т.е. нахождение и исправление ошибок можно не оставлять на отдельный этап, а проводить на каждом этапе.

Иллюстрация. Для описанной выше программы могут быть выявлены следующие ошибки.

Аварийное завершение 1. Попытка извлечь корень из отрицательного числа.

Аварийное завершение 2. Попытка деления на 0.

Корни одинаковы. Бывают уравнения с одним корнем.

«Аварийное завершение 1» возникло из-за неточности при разработке алгоритма, а именно, в математических выкладках.

«Аварийное завершение 2» возникло из-за неточности при разработке алгоритма, а именно, в математических выкладках. В данном случае уравнение не является квадратным. Тут, может быть, придётся вернуться к формулировке задачи или применить другой метод решения.

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

После завершения отладки получаем решение.

7. Решение. Это и есть цель всех предыдущих этапов.

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

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

е 8. Уточнённая задача. Эта задача возникла из новых требований.

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

Обычно уточнённая задача отличается от исходной непринципиально.

Значит, можно перейти к перепрограммированию.

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

Примеры олимпиадных задач.

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

Для окончательной убедительности будем рассматривать задачи только одной олимпиады – «Конкурсы на соискание стипендии корпорации ”Марк” и Удмуртского государственного университета в области программирования» (http://olymp.udm.ru - олимпиада «Марк»).

Достаточно рассмотреть задачи из олимпиады «Марк».

Задача 1.

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

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

НАЧАЛО ОФИЦИАЛЬНОЙ ПОСТАНОВКИ ЗАДАЧИ.

Имеется файл journal.txt записей о куплях-продажах за месяц. Правильная запись имеет формат:

Иванов И.: (Куплено) 12 (ящиков) водки "Калашников" [(от) ТОО "Копыта и рога"] (за) 300.00 [руб.] Петрова В.: (Продано) 100 (бутылок) водки "Калашников" [ (кому) ООО МММ] (за) 300.00 [руб.] Как обычно, необязательные элементы заключены в квадратные скобки. Каждая запись расположена на отдельной строчке. Файл заканчивается записью *** КОНЕЦ *** Кроме того, дан файл запасов каждого товара на начало месяца zapas.txt, записи в котором имеют форму:

Водка "Калашников" 1091 бут.

Сигареты "Ява" 11111 пач.

*** КОНЕЦ *** Нужно выдать новый файл запасов и свести баланс по всей фирме и по каждому работнику. Баланс должен быть выдан в виде файла balans.txt с записями вида:

Иванов И.:

-1956.65 руб.

Петрова В.: 2001.01 руб ИТОГО: 110000.01 руб Неправильные записи должны браковаться и отправляться на переделку, а фамилии работников, их допустивших, выдаваться начальству в виде списка nakazat.txt:

Иванов И.: 5 неверно Петрова В.: 1 неверно *** КОНЕЦ *** Когда все записи станут правильными, нужно выдавать окончательный файл баланса, в котором первая строчка должна иметь вид:

ОКОНЧАТЕЛЬНЫЙ БАЛАНС:

КОНЕЦ ОФИЦИАЛЬНОЙ ПОСТАНОВКИ ЗАДАЧИ.

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

Увидев запись вида:

Сидор сбагрил (Ваньке) 100 (бут.) ("Калаша") за (5000.00) (Сидоров — один из лучших работников и приятель шефа) Вы поняли, как туго Вам придется, тем более что накляузничать на всех работников — лучший способ не выдержать в фирме долго после испытательного срока. Поэтому Вы решили составить программу, которая без ключа работала бы буквоедски, на тестах зама, а с ключом -x — более доброжелательно и содержательно.

ЗАДАЧА

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

Tovar.txt - содержит данные (уже Ваши, правильные; в реальности Вы их зашифровали, но здесь они даны в открытом виде):

Наименование товара[, псевдонимы]*: примерная цена: базовая единица[, число другая единица]* Например, возможна строчка:

Водка "Калашников", "Калаш": 25.00: бут., 1 бутылка, 1 пузырь, Sotrud.txt - содержит данные о сотрудниках.

Фамилия[, псевдонимы]* Например:

Сидоров В., Сидор, Виталик Предоставить тест для проверки своей и других программ. Тест будет содержательно проверен на правдоподобие ошибок во входном файле.

Он состоит из файлов Tovar.txt, journal.txt, zapas.txt, Sotrud.txt. Списки псевдонимов должны быть достаточно представительными, но могут быть не исчерпывающими (времени составить полные у Вас не было, да и просмотреть еще одно написание типа Сидорофф Вы тоже могли).

ОЦЕНКА ПРОГРАММЫ

Программа прежде всего будет проверена на тестах жюри и на своем собственном тесте в буквоедском режиме. Если она не пройдет хоть один из этих тестов, она получает не более 5 очков.

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

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

Автор задачи: Н.Н.Непейвода Задача 2.

Известна задача, где требуется написать программу, печатающую свой исходный текст [1].

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

ТЕХНИЧЕСКИЕ ТРЕБОВАНИЯ

Программа должна работать без внешних модулей и файлов. Результат работы записывается в файл *.TXT в текущей директории, где * — имя Вашей программы. Например, программа INPUT.PAS должна выдавать файл INPUT.TXT

ОЦЕНКА ПРОГРАММЫ

Программа будет оцениваться следующим образом. Будет выполнена Ваша программа. Результат прочитан из файла. Из первых строк будут удалены символы ’>’. Затем будут сравнены исходный текст и полученный, если они не совпадают, задача считается выполненной неверно и получает 0 баллов. Правильные решения приносят 40 баллов.

Дополнительно 20 баллов распределятся в соответствии с длиной исходного текста программы, самая короткая программа — 20 баллов, самая длинная — 0.

Автор задачи: В.В.Пупышев.

Задача 3.

Она представляет собой продолжение задачи этапа 4 ”Превращение программы в почтовое сообщение” Внимание! Эту задачу Вы выполняете на той же системе программирования и с Вашим исходным текстом решения аналогичной задачи первого тура в качестве исходных данных. По 20 очков (из максимально возможных) может быть начислено за близость исходного и модифицированного решений. До 20 очков штрафа может быть за полностью различные программы.

Написать программу, которая при запуске с ключом ’-v’ печатает на экран 0, а при запуске без ключа выдаёт текст новой программы. Новая программа должна: при запуске с ключом ’-v’ печатать номер поколения, а без ключа печатать новую программу с описанными выше условиями.

Например, Ваша программа была написана на каком-то языке программирования. Пусть транслятор называется trans, файл с программой называется a.txt, результат работы программы в файле r.txt.

При последовательности действий:

trans a.txt ---создаёт--> a.exe a -v ---на экране--> rename r.txt a.new trans a.txt --> a.exe rename r.new a.txt trans a.txt --> a.exe rename r.new a.txt trans a.txt --> a.exe a -v ---на экране-->

ТЕХНИЧЕСКИЕ ТРЕБОВАНИЯ

Программа должна работать без внешних модулей и файлов. Результат работы записывается в файл *.new в текущей директории, где * - имя Вашей программы. Например, программа INPUT.PAS должна выдавать файл INPUT.NEW.

ОЦЕНКА ПРОГРАММЫ

Программа будет оцениваться следующим образом. Будет выполнена Ваша программа. Результат прочитан из файла. Оттранслирован, выполнен, полученная программа взята за исходную и так N раз. Потомок с номером N будет вызван с ключом ’-v’ и если он выдаст число отличное от N, такое решение получает 0 баллов. 0 баллов получают программы, у которых какой-либо потомок содержит синтаксическую ошибку.

Правильные решения приносят 40 баллов. Дополнительно 20 баллов могут быть даны за близость старого и нового текстов. Длина во внимание не принимается.

Автор задачи: В.В.Пупышев.

Рассмотрим задачу № 1. Для её решения понадобиться пройти все этапы программирования, кроме 7. Для этого этапа нужны, как минимум, две задачи. Задачи № 2 и № 3 заставляют пройти и этап 7. Таким образом, программирование олимпиадных задач задействует все этапы и мало чем отличается от реального программирования.

Есть ещё важные навыки, которые задействует олимпиада «Марк», но не отражены в жизненном цикле.

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

2. Общение с заказчиком. Т.е. умение задать нужные вопросы. Обеспечивается тем, что в формулировке задачи есть неточности.

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

Некоторые выводы.

На обычных олимпиадах стремятся к тому, чтобы задача имела полное решение и была точно сформулирована. Это можно сделать, оставаясь в рамках этапов 1, 2, 3 и 4, но этапы 2 и 3 только в простом виде (формализуемая разрешимая проблема). Этап 5 обычно присутствует как результат. Этап 6 проходит только жюри, участники проходят его неявно или вообще не проходят. Такие олимпиады назовём классическими. Этап 7 в таких классических олимпиадах невозможен из-за ограничения по времени. К таким олимпиадам относится, например, олимпиада ACM (http://acm....org). Конечно, классические олимпиады создают мнение, что олимпиады очень далеки от реального программирования.

На самом деле, реально организована олимпиада, которая требует от участников владения всеми этапами разработки.

Список литературы [1] Уэзерелл Ч. Этюды для программистов. М.: Мир, 1982.

[2] Лисков Б., Гатэг Дж. Использование абстракций и спецификаций при разработке программ: Пер. с англ. – М.: Мир, 1989.

[3] Непейвода Н.Н. Прикладная логика. Ижевск, Издательство Удмуртского университета, 1997.

[4] Непейвода Н.Н. Прикладная логика. Новосибирск, Издательство Новосибирского университета, 2000.