Министерство образования и наукиРоссийской Федерации
Агентство по образованию
Тихоокеанский Государственный ЭкономическийУниверситет
Экономический институт
Курсовая работа
На тему: «Поиск кратчайшего пути передвижения слона
по шахматному полю»
Проверила: Выполнил:
Прудникова Л.И., доцент ______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с.