Курсовая работа: Поиск кратчайшего пути передвижения слона по шахматному полю

Введение

Формальная постановка задачи

Методы решения

Модульная организация приложения

Общая схема взаимодействия модулей

Описание модулей

Текст программы

Руководство пользователя

Тестовый пример игры

Заключение

Список литературы

Введение

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

Целью представленной работы является разработка приложения “Поиск кратчайшего пути”, которое создает шахматную доску, находит кратчайший путь передвижения слона и отображает его.

Перед началом вычисления пользователь должен указывать в программе следующую информацию:

- размерность поля

- установить слона на начальную позицию и указать конечную (при помощи мыши)

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

Необходимо предусмотреть контроль целостности вводимых данных.

Формальная постановка задачи

Методы решения

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

1. Задаём размер поля n

2. Проверим, чтобы слон и его местоположение должны находиться на полях одного цвета.

3. Образуем матрицу для расчёта пути размерности n+1

4. С помощью полученной матрицы во избежание выхода за шахматное поле заполним окаймляющие элементы значениями false

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

6. Определим общие точки этих двух множеств:

а) если они имеют одну общую точку, то существует единственный кратчайший путь в 2 хода

б) если они имеют 2 общие точки, то существует 2 различных кратчайших пути, длиной в 2 хода

в) если точек пересечения больше 2, то слон достигает своего конечного местоположения за 1 ход.

Модульная организация приложения

Реализация проекта выполнена в рамках двух модулей. Каждый из них выполняет определенные для него функции. Разделение функций модулей выполнено в соответствии с задачами проекта. В общем случае разделение выполняется на две составные части: проведение расчетов и визуализация полученных данных.

Общая схема взаимодействия модулей

--> ЧИТАТЬ ПОЛНОСТЬЮ <--