Общее условие.Создать пакет и набор тестов для демонстрации возможностей.
Требование.Для сдачи должен быть предоставлен следующий набор файлов.
- schema.sql – файл, содержащий SQL для создания таблиц;
- insert.sql – файл, содержащий SQL для добавления необходимых данных в таблицы;
- package.sql – файл, с реализацией пакета;
- test1.sql, test2.sql, …, testN.sql – набор файлов с тестами, в количестве достаточном для полной демонстрации/проверки работы всех функций пакета.
Пересечение многоугольников.Заданы набор N-угольников (N > 2) на плоскости. Многоугольники задаются последовательным перечислением координат своих вершин. Обход вершин осуществляется против часовой стрелки. Реализовать следующие возможности: - хранение многоугольников в таблице (предусмотреть хранение любого числа многоугольников); - добавление/удаление многоугольника; - добавление/удаление вершины многоугольника; - проверка многоугольника на выпуклость; - проверка пересечения 2-х многоугольников; - получение многоугольника – результата пересечения двух многоугольников; - вывод многоугольника на экран (приблизительное текстовое представление сформировать в таблице информацию о каждой клетке); - вычисление площади многоугольника; - вычисление площади пересечения многоугольников;
- поиск многоугольников с максимальной и минимальной площадью
Шахматы.Рассматривается классическая игра на 64 клеточной доске с классическим набором фигур. Реализовать следующие возможности: - хранение шахматных досок в таблице БД (предусмотреть хранение любого количества досок); -хранение партий в таблице БД (предусмотреть хранение любого числа партий); - создание/удаление партий; - реализовать шахматные часы: фиксация времени на ход каждого из игроков, вывод сообщения о том, что время вышло; установка времени на партию при ее создании, предусмотреть возможность бессрочных партий; - вывод текущего состояния партии (вывод шахматной доски); - хранение истории партии; - вывод истории партии в соответствии с классической шахматной нотацией; - вывод состояния партии на N-м ходу белых/черных; - процедура «ход фигуры» с обязательной проверкой допустимости такого хода; - откат хода, откат партии на любой ход.
Балда.Написать пакет для игры в балду. В центральной строке таблицы 5х5 клеток записывается любое пятибуквенное слово. Игроки по очереди добавляют в клетки по одной букве, таким образом, чтобы получилось новое слово наибольшей длины (слова могут ломаться, но не по диагонали). За каждую буквы нового слова игрок получает 1 очко. Игра заканчивается, когда все клетки заполнены. Реализовать следующие возможности: - хранение таблиц (предусмотреть возможность хранения любого количества таблиц); - хранение словаря допустимых слов (с возможностью просмотра, удаления, редактирования и добавления новых слов); - создание/удаление новой партии (ввод слова, регистрация участников, тип игры: со словарем или без и т.п.); - процедура «ход игрока» - добавление буквы на поле и заявленное слово (предусмотреть проверку слова на существование, на наличие в словаре); - вывод текущего состояния партии (вывод таблицы); - хранение истории партии; - вывод текущего счета партии; - вывод истории (кто какой ход делал, какое слово получил и какой счет); - вывод состояния партии на N-м ходу белых/черных; - процедура «ход фигуры» с обязательной проверкой допустимости такого хода; - откат хода, откат партии на любой ход.
Кроссворд.Написать пакет для работы с классическими кроссвордами. Реализовать следующие возможности: - хранение сетки кроссворда в таблице БД (предусмотреть возможность хранения любого числа сеток); - хранение вопросов кроссворда в таблице БД; - процедуры поставить/снять слово; - проверка допустимости выставляемого слова; - вывод текущего состояния сетки кроссворда на экран. - получение описания по номеру слова.
Японский кроссворд.Написать пакет для работы с черно-белыми японскими кроссвордами. Реализовать следующие возможности: - хранение сетки кроссворда в таблице БД (предусмотреть возможность хранения любого числа сеток); - хранение числе-ключей к строкам/столбцам кроссворда в таблице БД; - добавление/удаление сеток в таблицу БД; - процедуры заполнить-очистить ячейку/ячейки (одну или ряд); - проверка допустимости заполнения ячейки; - вывод текущего состояния сетки кроссворда на экран; - проверка финального состояния кроссворда на правильность.
Задача коммивояжера.Использовать жадный алгоритм для решения задачи коммивояжера. Реализовать следующие возможности. - хранение графа и расстояний в таблице БД (предусмотреть возможность хранения любого числа графов); - добавление/удаление узла в граф; - задание расстояния между городами – узлами графа; - вывод графа на экран; - выбор начального города – узла графа; - процедуру решения и вывод решения на экран; - хранение решения в таблице БД.
Сдача.Задан некоторый набор монет. Необходимо сформировать указанную сумму наименьшим числом монет. Реализовать следующие возможности: - хранение набора монет в таблице БД (предусмотреть возможность хранения любого числа наборов); - добавление/удаление набора; - добавление/удаление монеты из набора; - вывод заданного набора на экран; - процедура получения минимального поднабора может из указанного набора для формирования заданной суммы. - хранение всех решений в таблице БД. - кеширование результатов предыдущих вычислений (если набор монет не менялся и вводим ту же сумму, то возвращаем результат из кеша).
Реверси.Реализовать пакет для игры в реверси (правила можно посмотреть в интернете). - хранение досок в таблице БД (предусмотреть возможность хранения любого количества досок); - создание/удаление партии (регистрация игроков); - процедура «ход игрока», проверка допустимости хода, изменение состояния доски, пересчет очков. - хранение истории партии (кто куда ставил и сколько очков на данный момент). - вывод доски на экран.
Китайский кроссворд (sudoku).Реализовать пакет для работы с китайскими кроссвордами (правила можно посмотреть в интернете). Реализовать следующие возможности. - хранение сетки кроссворда в таблице БД (предусмотреть возможность хранения любого числа сеток); - добавление/удаление сеток в таблицу БД; - процедуры поставить цифру в ячейку / убрать цифру из ячейки (можно убирать только те, которые были поставлены игроком); - проверка допустимости заполнения ячейки; - вывод текущего состояния сетки кроссворда на экран; - откат хода (вплоть до самого начала) – хранить историю - проверка финального состояния кроссворда на правильность.
Шашки.Рассматривается классическая игра на 64 клеточной доске. Реализовать следующие возможности: - хранение доски в таблице БД (предусмотреть хранение любого количества досок); -хранение партии в таблице БД (предусмотреть хранение любого числа партий); - создание/удаление партии; - вывод текущего состояния партии (вывод доски); - хранение истории партии; - вывод истории партии; - вывод состояния партии на N-м ходу белых/черных; - процедура «ход игрока» с обязательной проверкой допустимости такого хода; - откат хода, откат партии на любой ход.
Словарь.Реализовать метрическое пространство (набор слов + метрика) слов русского/английского языка. Необходимы следующие возможности: - хранение набора слов в БД; - добавление/удаление/замена слова; - вычисление расстояния между словами по метрике Левенштейна; - из МУХИ сделать СЛОНа. Найти кратчайший путь от одного слова словаря к другому. Расстояние по метрике Левенштейна между словами в цепочке не должно превышать заданного N > 0; - предусмотреть кеширование расстояний между двумя словами в таблице БД.
Лабиринт.Реализовать волновой алгоритм нахождения кратчайшего выхода из лабиринта. Реализовать следующие возможности: - хранение лабиринта в таблице БД (предусмотреть хранение любого числа лабиринтов); - вывод лабиринта на экран (x – стена, space – проход, s – начало, e-выход). - редактирование лабиринта (установить/убрать стену, установить выход, установить старт); - запуск нахождения решения; - вывод решения на экран.
Дерево чисел.Описание. Реализовать следующие возможности. - хранение дерева в таблице БД (предусмотреть хранение любого числа деревьев). - добавление/удаление узлов; - вывод дерева на экран; - подсчет суммы в поддереве.
Хранения дерева в БД I.Описание. Реализовать следующие возможности. - хранение дерева в таблице БД (предусмотреть хранение любого числа деревьев). - добавление/удаление узлов; - вывод всех узлов; - вывод листьев.
Описание механизма хранения:
Каждый узел хранит ключ, информационное поле, номер узла-предка, L и R целочисленные поля. L и R формируются в порядке обхода дерева левый-правый-центр.
Хранения дерева в БД II .Описание. Реализовать следующие возможности. - хранение дерева в таблице БД (предусмотреть хранение любого числа деревьев). - добавление/удаление узлов к указанному; - вывод всех узлов на указанный момент времени; - вывод листьев.
Описание механизма хранения:
Используются две таблицы. В первой хранятся только информационные узлы без связей между ними. Во второй – все возможные пути между узлами(родительский узел, узел-потомок, расстояние, дата установления связи, дата окончания связи)
Сапер. Реализовать пакет для игры в классического сапера. Следующие возможности. - хранение поля для сапера в таблице БД (предусмотреть возможность хранения произвольного числа полей); - генерация начального состояния поля; - вывод текущего состояния поля на экран; -процедура «ход игрока» (мина, не мина, пустое место);
«Жадный» турист.Реализовать пакет для решения задачи о рюкзаке жадным алгоритмом. Необходимо реализовать следующие возможности:
- хранение нескольких исходных множеств вещей;
- решение задачи и хранение полученных решений;
- печать полученного решения;
- печать оставшегося места в рюкзаке для указанного решения;
Распределение файлов по дискетам.Реализовать пакет для решения задачи о распределении вещей по ящикам жадным алгоритмом. Необходимо реализовать следующие возможности:
- хранение нескольких исходных множеств вещей;
- решение задачи и хранение полученных решений;
- печать полученного решения;
- печать оставшегося места в ящиках для указанного решения;
- процедуры «создать решение», «положить вещь в ящик», «убрать вещь из ящика»
