СодержаниеСодержание
СОДЕРЖАНИЕ 2
1. ВВЕДЕНИЕ 3
1.1. ОПИСАНИЕ ПРЕДМЕТНОЙ ОБЛАСТИ 3
1.2. НЕФОРМАЛЬНАЯ ПОСТАНОВКА ЗАДАЧИ 3
1.3. ОБЗОР СУЩЕСТВУЮЩИХ МЕТОДОВ РЕШЕНИЯ 3
2. ТРЕБОВАНИЯ К ОКРУЖЕНИЮ 4
3. СПЕЦИФИКАЦИЯ ДАННЫХ 4
4. ФУНКЦИОНАЛЬНЫЕ ТРЕБОВАНИЯ 4
5. ТРЕБОВАНИЯ К ИНТЕРФЕЙСУ 5
6. ПРОЕКТ 8
6.1. СРЕДСТВА РЕАЛИЗАЦИИ 8
6.2. МОДУЛИ 8
6.3. АЛГОРИТМЫ 11
ЗАКЛЮЧЕНИЕ 13
СПИСОК ЛИТЕРАТУРЫ 14Введение1. Введение
1.1. Описание предметной области
В настоящее время спортивное программирование переживает настоящий бум среди студентов и школьников. Самыми выжными соревнованиями считаются ACM ICPC и IOI соответственно. Олимпиады по программированию имеют более чем двадцатилетнюю ис-торию. При этом высокие результаты предыдущих поколений студентов и школьников стимулируют занятие олимпиадным программированием все новых и новых молодых лю-дей. Особое место на соревнованиях занимают задачи по вычислительной геометрии. Над воротами в академию Платона была надпись «Да не войдет сюда несведущий в геомет-рии». Организаторы соревнований по программированию считают примерно так же, по-этому как минимум одна геометрическая задача присутствует на каждой олимпиаде. Од-нако создание и тестирование таких задач представляет значительные трудности. Геомет-рия по сути своей дисциплина наглядная — нужно рисовать картинки и внимательно их изучать, но все данные хранятся в виде последовательности чисел. Это приводит к тому, что тесты сначала рисуются на бумаге либо создается визуализатор, работающий только на одной задаче. Целью курсовой являлось создание универсального визуализатора, кото-рый бы облегчил участь жюри и участников олимпиад при создании тестов для геометри-ческих алгоритмов.
Изначально предполагалось решить поставленную задачу, расширив формальное описание входных данных, которое используется для автоматического создания тестов [1]. Однако в ходе анализа задач прошлых лет выяснилось, что данные о фигуре не всегда идут в одном порядке и иногда перемежаются данными других фигур. Чтобы не упустить ни одной задачи, необходим более гибкий инструмент, такой как интерпретатор команд. Его использование позволит не только загрузить любые данные, но и создать новые фигуры, изменить старые, найти количественные отношения и сохранить все в новом тесте. Суще-ствует даже возможность решения задачи на интерпретаторе, что может быть полезно для быстрой проверки алгоритма, не обременяя себя написанием стандартных функций.
1.2. Неформальная постановка задачи
Визуализатор должен обеспечить
• чтение тестовых данных из файла;
• визуализацию геометрических фигур;
• возможность автомасштабирования;
• создание дополнительных построений и изменение фигур из тестового набора;
• сохранение измененного тестового набора;
• нахождение точек касания и пересечения.
1.3. Обзор существующих методов решения
В качестве вариантов решения поставленной проблемы рассматривались следующие системы: обучающие программы по геометрии и математические пакеты.
Среди обучающих программ было рассмотрено несколько экземпляров в том числе GeoGebra 3.0 [2] (обладатель десятка наград в области образовательных программ). Этот класс программ ориентирован на школьников разных возрастов, поэтому интерпретатор команд, если он есть, не позволяет использовать многие необходимые структуры: циклы, ветвления, массивы. Так как подразумевается прежде всего геометрический ввод, то не об-рабатываются вырожденные случаи, вроде пересечения совпадающих прямых. Кроме того, нет возможности программно открывать файлы.
Возможности математических пакетов изучались на примере Maple 12.0 [3]. В нем геометрия является надстройкой над системой символьных вычислений, поэтому визуали-зация является функцией, которая принимает список отображаемых объектов. К тому же поддерживаются только простейшие фигуры, в частности, нет класса многоугольников.
Перечисленные системы нельзя назвать конкурирующими разрабатываемой, это — близкие по тематике, со своими нишами рынка продукты, которые не могут быть исполь-зованы для решения поставленной задачи.
2. Требования к окружению
На компьютере должна быть установлена операционная система Windows 98 или выше.
Для загрузки данных и создания дополнительных построений достаточно навыков работы с командной строкой и опыта программирования на одном из языков. Для написа-ния решения к задаче необходимо знание языка Lua 5.1.
3. Спецификация данных
После изучения задач, ранее предлагавшихся на олимпиадах различных уровней, бы-ло выделено 8 объектов. Все объекты должны иметь поле color, которое используется для задания цвета.
Point — точка или вектор задается своими координатами (x, y).
Line — прямая задается коэффициентами уравнения ax + by + c = 0.
Segment — отрезок задается концами (begin, ending).
Ray — луч задается началом и одной из внутренних точек (begin, ending).
Circle — окружность задается центром и радиусом (center, radius).
Arc — дуга задается окружностью, на которой она лежит, и концами (cir-cle, begin, ending).
Polyline — ломаная не содержит атрибутов, но содержит список точек, перечислен-ных в порядке обхода. Доступ к ним осуществляется аналогично массивам.
Polygon — многоугольник является структурой аналогичной ломаной, разница обна-руживается на этапе визуализации.
4. Функциональные требования
Библиотека интерпретатора должна предоставлятьЛитератураСписок литературы
[1] Туфанов И. Е. Универсальный генератор тестов для системы CATS.
[2] GeoGebra Home Page, http://www.geogebra.org.
[3] Maple Home Page, http://www.maplesoft.com.
[4] CGAL Home Page, http://www.cgal.org.
[5] Ierusalimscky R. Programming in Lua, 2006.
[6] Ласло М. Вычислительная геометрия и компьютерная алгебра на C++/Пер. с англ. — М.: «Издательство БИНОМ», 1997. — 304 с.
[7] Скиена С. С., Ревилла М. А. Олимпиадные задачи по программированию. Руководство по подготовке к соревнованиям/Пер. с англ. — М.: КУДИЦ-ОБРАЗ, 2005. — 416 с.
|
|
