Разработка виртуальной лаборатории для поиска минимального маршрута
Курсовой проект - Компьютеры, программирование
Другие курсовые по предмету Компьютеры, программирование
абораторного стенда.
2.Node - класс, описывающий вершину графа:
oint x, y - координаты узла;
ovoid setCoords(int x, int y) - устанавливает координаты;
oint[] getCoords() - возвращает координаты;
3.Edge - класс, реализующий ребро графа:
oint[] nodes - ID вершин, которые соединяет ребро;
oint[] getNodes - возвращает вершины, соединяемые ребром.
4.Front - класс, интерпретирующий фронт волнового алгоритма:
oint[] nodes - вершины, образующие фронт;
ovoid add(int index) - добавляет вершину во фронт;
oint findNode(int index) - проверка на наличие во фронте; если вершина найдется, то возвратится ее индекс во фронте, инасе возвратится -1;
oint[] getNodes() - возвращает вершины фронта;
oint getNodesCount() - возвращат размер фронта;
ovoid remove(int index) - удаляет вершину из фронта.
5.Graph - класс, описывающий граф:
oEdge[] edges - массив рёбер графа
oNode[] nodes - массив вершин графа;
oFrontd[] fronts - масств созданных фронтов волнового алгоритма.
oint edgesCount, nodesCount, frontdCount - число рёбер, узлов и размеченных фронтов в графе;
oint finish, start - концы маршрута;
ovoid addEdge(int[] nodes)- добавляет в граф ребро;
ovoid addFront() - создает новый фронт в графе;
ovoid addToFront(int index) - добавляет узел во фронт;
ovoid removeEdge(int[] nodes) - удаляет ребро;
ovoid removeFront() - удаляет текущий фронт;
oboolean isAllNodesMarked() - проверка на полную раскраску графа;
ovoid removeFromFront(int index) - удаление вершины из фронта.
. Laboratory - класс апплета виртуального стенда:
oString answer - строка ответа аттестующегося;
oGraph graph - граф, на котором реализуется задание;
oint step - текущий шаг прохождения лабораторной работы;
ovoid changeMark(Graphics g, int clickedNode) - изменение разметки вершины;
ovoid initComponents() - инизиализация компонентов интерфейса;
ovoid paintEdge(Graphics g, int first, int second) - отрисовка ребра;
ovoid paintNode(Graphics g, int index) - отрисовка вершины;
ovoid paintGraph(JPanel panel, int nodesCount) - отрисовка графа;
ovoid setNewStartNode(Graphics g, int node) - установка новой начальной точки на четвертом этапе - вычислении эксцентриситетов;
Рисунок 2 - Схема классов виртуального стенда
4. Описание формата ответа и тестовых наборов
.1 Формат ответа
Формат строки ответа, возвращаемой методом апплета getResults(), имеет следующий вид:
pathLength exct1 exct2 … exctN rad diam
.., где pathLength - длина кратчайшего пути в графе, описанном матрицей смежности, exct1 exct2 … exctN - эксцентриситеты для графа на N вершинах, rad - радиус графа, diam - диаметр графа.
В качестве примера приводится строка, полученная в результате работы с графом, заданным следующей матрицей смежности:
0001011000001000001011000001001000011000001011000
После всех необходимых измерений, получились следующие результаты:
?длина кратчайшего пути - 5;
?эксцентриситеты - 3 5 4 3 5 4 3;
?радиус графа - 3
?диаметр графа - 5
Строка ответа будет выглядеть следующим образом:
3 5 4 3 5 4 3 3 5
4.2 Формат тестового набора
В тестовый набор на задание с графом на N вершинах входит N+3 проверки - на каждую часть ответа, вводимую студентом. Каждая проверка описана в таблице 1.
Таблица 1. Формат тестового набора.
Входная строкаВыходная строкаmin_pathдлина кратчайшего пути для заданного графаexct1эксцентриситет для первой вершины заданного графаexct2эксцентриситет для второй вершины заданного графа………………………………………………..exctNэксцентриситет для N-ой вершины заданного графаradiusрадиус заданного графаdiameterдиаметр заданного графа
5. Виртуальный стенд
На первом шаге студенту предоставляется интерфейс для ввода начальных данных - количества вершин в графе, а также начала и конца пути (рисунок 3).
Рисунок 3 - ввод начальных данных
По этим данным строятся вершины графа, отмечаются концы пути. Предоставляется интерфейс для отрисовки рёбер (рисунок 4).
Рисунок 4 - отрисовка рёбер
Затем становится возможным создание фронтов и раскраска графа по методу волнового алгоритма с целью нахождения длины кратчайшего пути (рисунок 5). Как только вершина конца пути попадает во фронт, становится доступным поле для ввода длины минимального маршрута, а также кнопка для перехода на следующий этап.
Рисунок 5 - поиск кратчайшего пути.
Следующий шаг - это раскраска графа, начиная от каждой вершины по очереди, с целью нахождения эксцентриситетов (рисунок 6).
.
Рисунок 6 - определение эксцентриситетов
Когда для каждой вершины будет определен эксцентриситет, будет произведен переход к последнему шагу - вводу радиуса и диаметра графа по данным предыдущего этапа (рисунок 7).
Рисунок 7 - ввод радиуса и диаметра графа
По нажатии кнопки Завершить работу методом getResult() ответ студента отправится на проверку.
6. Проверяющий сервер
При анализе ответа студента проверяется каждое задание в отдельности. Сопоставляются с эталонными значениями:
?длина кратчайшего пути;
?каждый эксцентриситет;
?радиус графа;
?диаметр графа.
Таким образом, за каждое верно введенное значение студент получает 100/(N+3) баллов из расчета, что полностью верный ответ - это 100 баллов.
Благодаря такой системе оценивания, можно более тонко дать характеристику навыкам и знаниям аттестующегося: результатом становится не просто флаг выполнено / не выполнено, а числовая характеристика.
7. Задания и тестовые наборы
Ниже представлено несколько вариантов заданий и тестовые наборы для них.
Таблица 2. Задания для виртуальной лабораторной работы.
ЗаданиеВходящий тестовы наборВыходящий те?/p>