Название: Поиск кратчайшего пути передвижения слона по шахматному полю
Вид работы: курсовая работа
Рубрика: Математика
Размер файла: 17.48 Kb
Скачать файл: referat.me-217878.docx
Краткое описание работы: Министерство образования и науки Российской Федерации Агентство по образованию Тихоокеанский Государственный Экономический Университет Экономический институт
Поиск кратчайшего пути передвижения слона по шахматному полю
Министерство образования и науки Российской Федерации
Агентство по образованию
Тихоокеанский Государственный Экономический Университет
Экономический институт
Курсовая работа
На тему: «Поиск кратчайшего пути передвижения слона
по шахматному полю»
Проверила: Выполнил:
Прудникова Л.И., доцент ______121ПИ _________,
к.ф.-м.н ,______ Гоман Т.С.
Владивосток 2009
Содержание
Введение
Формальная постановка задачи
Методы решения
Модульная организация приложения
Общая схема взаимодействия модулей
Описание модулей
Текст программы
Руководство пользователя
Тестовый пример игры
Заключение
Список литературы
Введение
Условие решаемой задачи дословно по заданию звучит следующим образом: «найти кратчайший путь передвижения слона по заданному клеточному полю, соединяющих два заданных поля доски»
Целью представленной работы является разработка приложения “Поиск кратчайшего пути”, которое создает шахматную доску, находит кратчайший путь передвижения слона и отображает его.
Перед началом вычисления пользователь должен указывать в программе следующую информацию:
- размерность поля
- установить слона на начальную позицию и указать конечную (при помощи мыши)
После этого программа должна показать кратчайший путь (пути) движения слона, выделяя его другим цветом.
Необходимо предусмотреть контроль целостности вводимых данных.
Формальная постановка задачи
Методы решения
Существует довольно много различных методов решения подобной задачи, каждый из которых основывается на своих принципах и приемах, имеет уникальные преимущества и, соответственно, недостатки. В данной работе был использован метод нахождения кратчайшего пути на графе.
1. Задаём размер поля n
2. Проверим, чтобы слон и его местоположение должны находиться на полях одного цвета.
3. Образуем матрицу для расчёта пути размерности n+1
4. С помощью полученной матрицы во избежание выхода за шахматное поле заполним окаймляющие элементы значениями false
5. Выберем все возможные клетки, когда слон из начального местоположения и точки назначения, используя ранее полученную матрицу
6. Определим общие точки этих двух множеств:
а) если они имеют одну общую точку, то существует единственный кратчайший путь в 2 хода
б) если они имеют 2 общие точки, то существует 2 различных кратчайших пути, длиной в 2 хода
в) если точек пересечения больше 2, то слон достигает своего конечного местоположения за 1 ход.
Модульная организация приложения
Реализация проекта выполнена в рамках двух модулей. Каждый из них выполняет определенные для него функции. Разделение функций модулей выполнено в соответствии с задачами проекта. В общем случае разделение выполняется на две составные части: проведение расчетов и визуализация полученных данных.
Общая схема взаимодействия модулей
Описание модулей
Каждый из модулей реализует свой класс. Описание модулей призываются к описанию классов (их назначения) и методов классов (решения определенных задач класса).
Текст программы
Руководство пользователя
При разработке приложения применялся принятый в среде Delphi объектно-ориентированный подход реализации интерфейса. При реализации алгоритмов обработки данных использовался структурный подход при проектировании к написании программ приложения.
1. В появившемся при вызове программы окне вводим размерность поля
2. В главном окне отмечаем расположение слона и цели. Отметив на поле слона мы делаем проверку, чтобы пользователь не мог отметить клетку-цель на поле не совпадающее цвету поля слона, а также на поле где расположен сам слон.
3. Если мы вводим размерность поля меньше или больше указанного диапазона, то выводится сообщение
Текстовый пример игры.
Заключение
Результатом работы над курсовой работой создано приложение среде Delphi, которое находит в нем кратчайший путь и визуализирует его на форме приложения. Приложение является полупрофессиональным, допускает различные варианты лабиринтов, настройкой соответствующих параметров. Выполненные многочисленные тестовые примеры позволяют утверждать, что надежность программного обеспечения проекта довольно высока.
Список литературы
1. Иванов Б.Н. Дискретная математика. Алгоритмы и программы: Учеб. Пособие. – Владивосток: Изд-во ДВГТ, 2000. – 288с.
2. Молчанова Л.А., Прудникова Л.И. Delphi в примерах и задачах: Учеб. пособие. Владивосток: Изд-во ТГЭУ, 2006. – 92с.
Похожие работы
-
Колебательно движение материальной точки
Министерство образования и науки Российской Федерации Санкт-Петербургский государственный горный институт имени В.Г. Плеханова (технический университет)
-
Решение задачи линейного программирования симплексным методом
ФЕДЕРАЛЬНОЕ АГЕНТСТВО ПО ОБРАЗОВАНИЮ Государственное образовательное учреждение Высшего профессионального образования «Волгоградский государственный технический университет»
-
Вычисление корней нелинейного уравнения
Министерство образования Российской федерации Южно-Уральский Государственный Университет Аэрокосмический факультет Кафедра летательных аппаратов
-
Решение систем линейных уравнений
ФЕДЕРАЛЬНОЕ АГЕНТСТВО ПО ОБРАЗОВАНИЮ Государственное образовательное учреждение высшего профессионального образования РОССИЙСКИЙ ГОСУДАРСТВЕННЫЙ ТОРГОВО-ЭКОНОМИЧЕСКИЙ УНИВЕРСИТЕТ
-
Практическая работа по Экономико- математическому методу и прикладные модели
Федеральное агентство по образованию Всероссийский заочный финансово-экономический институт Омский филиал Кафедра математики и информатики ПРАКТИЧЕСКОЕ ЗАДАНИЕ № 2 ПО ДИСЦИПЛИНЕ: «ЭКОНОМИКО-МАТЕМАТИЧЕСКИЕ МЕТОДЫ И ПРИКЛАДНЫЕ МОДЕЛИ»
-
Анализ накладных расходов
Министерство образования и науки Российской Федерации Федеральное агентство по образованию Государственное образовательное учреждение высшего профессионального образования
-
по Экономико-математическому моделированию
На основе данных выданных преподавателем необходимо: 1. Определить параметры следующих уравнений регрессии: а) линейного; б) гиперболического; в) степенного;
-
Преимущества и недостатки систем с отрицательной обратной связью
Федеральное агентство по образованию Российской Федерации Министерство образования и науки Российской Федерации Кафедра "Экономика и управление проектами"
-
Однополостный гиперболоид
Министерство высшего образования Российской Федерации Московский государственный строительный университет РЕФЕРАТ На тему: “Однополостный гиперболоид”
-
Графы Основные понятия
Министерство образования и науки Российской Федерации Курский государственный технический университет Кафедра ПО ВТ и АС Лабораторная работа № 1 Графы. Основные понятия