Министерство образования и науки Российской Федерации
Агентство по образованию
Тихоокеанский Государственный Экономический Университет
Экономический институт
Курсовая работа
На тему: «Поиск кратчайшего пути передвижения слона
по шахматному полю»
Проверила: Выполнил:
Прудникова Л.И., доцент ______121ПИ_________,
к.ф.-м.н,______ Гоман Т.С.
Владивосток 2009
Содержание
Введение
Формальная постановка задачи
Методы решения
Модульная организация приложения
Общая схема взаимодействия модулей
Описание модулей
Текст программы
Руководство пользователя
Тестовый пример игры
Заключение
Список литературы
Введение
Условие решаемой задачи дословно по заданию звучит следующим образом: «найти кратчайший путь передвижения слона по заданному клеточному полю, соединяющих два заданных поля доски»
Целью представленной работы является разработка приложения “Поиск кратчайшего пути”, которое создает шахматную доску, находит кратчайший путь передвижения слона и отображает его.
Перед началом вычисления пользователь должен указывать в программе следующую информацию:
- размерность поля
- установить слона на начальную позицию и указать конечную (при помощи мыши)
После этого программа должна показать кратчайший путь (пути) движения слона, выделяя его другим цветом.
Необходимо предусмотреть контроль целостности вводимых данных.
Формальная постановка задачи
Методы решения
Существует довольно много различных методов решения подобной задачи, каждый из которых основывается на своих принципах и приемах, имеет уникальные преимущества и, соответственно, недостатки. В данной работе был использован метод нахождения кратчайшего пути на графе.
Задаём размер поля n
Проверим, чтобы слон и его местоположение должны находиться на полях одного цвета.
Образуем матрицу для расчёта пути размерности n+1
С помощью полученной матрицы во избежание выхода за шахматное поле заполним окаймляющие элементы значениями false
Выберем все возможные клетки, когда слон из начального местоположения и точки назначения, используя ранее полученную матрицу
Определим общие точки этих двух множеств:
а) если они имеют одну общую точку, то существует единственный кратчайший путь в 2 хода
б) если они имеют 2 общие точки, то существует 2 различных кратчайших пути, длиной в 2 хода
в) если точек пересечения больше 2, то слон достигает своего конечного местоположения за 1 ход.
Модульная организация приложения
Реализация проекта выполнена в рамках двух модулей. Каждый из них выполняет определенные для него функции. Разделение функций модулей выполнено в соответствии с задачами проекта. В общем случае разделение выполняется на две составные части: проведение расчетов и визуализация полученных данных.
Общая схема взаимодействия модулей
Описание модулей
Каждый из модулей реализует свой класс. Описание модулей призываются к описанию классов (их назначения) и методов классов (решения определенных задач класса).
Текст программы
Руководство пользователя
При разработке приложения применялся принятый в среде Delphi объектно-ориентированный подход реализации интерфейса. При реализации алгоритмов обработки данных использовался структурный подход при проектировании к написании программ приложения.
В появившемся при вызове программы окне вводим размерность поля
В главном окне отмечаем расположение слона и цели. Отметив на поле слона мы делаем проверку, чтобы пользователь не мог отметить клетку-цель на поле не совпадающее цвету поля слона, а также на поле где расположен сам слон.
Если мы вводим размерность поля меньше или больше указанного диапазона, то выводится сообщение
Текстовый пример игры.
Заключение
Результатом работы над курсовой работой создано приложение среде Delphi, которое находит в нем кратчайший путь и визуализирует его на форме приложения. Приложение является полупрофессиональным, допускает различные варианты лабиринтов, настройкой соответствующих параметров. Выполненные многочисленные тестовые примеры позволяют утверждать, что надежность программного обеспечения проекта довольно высока.
Список литературы
Иванов Б.Н. Дискретная математика. Алгоритмы и программы: Учеб. Пособие. – Владивосток: Изд-во ДВГТ, 2000. – 288с.
Молчанова Л.А., Прудникова Л.И. Delphi в примерах и задачах: Учеб. пособие. Владивосток: Изд-во ТГЭУ, 2006. – 92с.
Другие работы по теме:
Транспорт XXI века
Поиск самого экономичного автомобиля неизменно обращает нас к транспортному средству, приводимому в движение ногами водителя. В последнее время появился и новый способ передвижения — веломобиль.
Шахматы
Содержание: Страница Введение. РАЗДЕЛ 1. О появлении шахмат РАЗДЕЛ 2. Влияние шахмат на человеческий ум РАЗДЕЛ 3. Шахматы в Казахстане РАЗДЕЛ 4. Правила игры в шахматы
Макс Эйве
5-й в истории Шахмат чемпион мира (1935-1937), международный гроссмейстер (1950), международный арбитр (1951). Президент ФИДЕ (1970-1978). Шахматный литератор. Доктор математики; преподаватель математики, механики и астрономиию
Проблемы ограниченности пропускной способности автодорог
Определение кратчайшего пути между двумя точками. Данный метод позволяет определить кратчайший путь между 2-мя точками в городе. Этот метод может быть применен для определения сегментов улиц, через которые должен проходить маршрут транспортного средства для минимизации пройденного пути, времени или иного фактора.
Поиск оптимального пути в ненагруженном орграфе
Понятия теории графов. Понятия смежности, инцидентности и степени. Маршруты и пути. Матрицы смежности и инцедентности. Алгоритм поиска минимального пути в ненагруженном ориентированном орграфе на любом языке программирования, алгоритм фронта волны.
Моделирование систем
Составление таблицы значений функции алгебры логики и нахождение всех существенных переменных. Связный ориентированный и взвешенный граф. Построение функции полиномом Жегалкина. Текст программы для алгоритма Дейкстры. Определение единиц и нулей функции.
Рассказы о животных
Борис Степанович Житков, один из зачинателей отечественной детской литературы, написал много замечательных произведений о природе и животных. В его рассказах животные всегда помогают человеку, они умны, сообразительны, верны хозяину. Среди этих рассказов: «Беспризорная кошка», «Про обезьянку» и другие.
Просто так, сказки для маленьких детей
«Просто так, сказки для маленьких детей» Дж. Р. Киплинга — это сказки о животных, наполненные юмором. В них тесно переплетаются сказочное и обыденное. Автор на вопросы «как?» и «почему?» даёт свои неожиданные ответы и рассказывает, например, о том, откуда у слона взялся хобот, отчего леопард стал пятнистым, как появились домашние животные.
Выбор жизненного пути мини-сочинение
Автор: Сочинения на свободную тему Среди десятков и сотен принимаемых человеком решений самую важную роль и влияние играет выбор жизненного пути.Потребность этого выбора возникает тогда, когда человек начинает осознавать себя в обществе и размышлять о своих потребностях.
Заяц и ёж
Эта сказка братьев Вильгельма и Якоба Гримм повествует о том, как ёж с ежихой хитростью победили в бегах своего быстроногого соперника — зайца: на старте был ёж, на финише — его жена, чего косой и не заметил. Умный и находчивый ёж высмеял зайца — «господина, вроде как бы знатного и уж очень надменного». На приветствие ежа в доброе воскресное утро заяц небрежно кивнул и грубо сказал: «Чего это ты так рано бегаешь тут по полю?» — «Гуляю», — ответил ёж. — «А по-моему, на таких коротких ножках далеко не уйдёшь».
Слон-живописец
Автор: Михалков С. Слон-живописец написал пейзаж, Но раньше, чем послать его на вернисаж, Он пригласил друзей взглянуть на полотно: Что, если вдруг не удалось оно?
Слон
Автор: Куприн Александр. Маленькая девочка Надя (6 лет) заболела, по словам доктора Михаила Петровича, «равнодушием к жизни». Единственное средство вылечить — развеселить. Но девочка ничего не хочет.
Сочинение по мотивам картины В.Г . Перова Охотники на привале с прямой речью
Сочинение по мотивам картины В.Г . Перова "Охотники на привале " (с прямой речью) Автор: Разное Как-то раз три друга Николай, Федор и Иван собрались на охоту. Долго они ходили по полю в поисках дичи. Подстрелив несколько гусей и уток, решили сделать привал. Как всегда во время обеда друзья, начали рассказывать охотничьи байки.
Расчет антенны типа Волновой канал
5 Эскиз антенны и схема питания Рисунок 5.1 – Эскиз антенны и схемы питания где, 1 – директоры 2 – активный вибратор 3 – рефлектор 4, 5, 11 – элементы симметрирующего устройства для возбуждения вибратора.
Велосипед
Способы быстрого передвижения люди искали на протяжении почти всей своей эволюции. Для этого использовались как животные (лошади, собаки, волы, слоны и так далее), так и изобретённые ими технические средства.
Орегонский путь
(также иногда Орегонская тропа , англ. Oregon Trail) — историческая дорога, проложенная в 1830-е годы, длиной около 3200 км. Дорога связывала долину реки Миссури с долинами в современном штате Орегон, и была пригодна для передвижения повозок. Эта старейшая из дорог, связывавших Великие Равнины с западом США.
Площадь Бастилии
План Введение 1 История 1.1 Крепость Бастилия 1.2 Бастильский слон 1.3 Июльская колонна 2 Достопримечательности 3 События и манифестации Список литературы
Христофор Колумб 4
Христофор Колумб (1451, Генуя, - 20.5.1506, Вальядолид), мореплаватель, по происхождению генуэзец. В 1476-1484 годах жил в Лиссабоне и на португальских островах Мадейра и Порту-Санту. Опираясь на античное учение о шарообразности Земли и на неверные расчёты учёных 15 века, Колумб составил проект западного, по его мнению кратчайшего, морского пути из Европы в Индию.
База данных расписания поездов
Сущность и основные функции СУБД Microsoft Access. Алгоритм создания базы данных расписания поездов и параметров их передвижения. Проектирование форм для сводных таблиц с помощью конструктора окон. Разработка отчетов и запросов на выборку данных.
СУБД Microsoft Access о расписании поездов
Разработка базы данных "Расписание поездов", которая позволит узнавать все сведения о движение поездов: пункт отправления и прибытия поезда, время отправления и прибытия с начальной и конечной станции, цены и льготы. Руководство по ее использованию.
Бази даних в Excel, Access з викликами на VBA
Введення формул з математичними, статистичними функціями та функціями для роботи з базами даних. Звичайне сортування бази даних по одному полю. Експорт таблиці з середовища MS Excel до середовища MS Access. Алгоритм програми на VBA, її інтерфейс.
Экспертная система для решения задачи о коммивояжере
Разработка, макетирование и реализация экспертной системы для решения задачи о коммивояжере, используя возможности языка Prolog. Составление графа "Карта Саратовской области" и решение проблемы поиска кратчайшего пути между двумя пунктами на карте.
Поиск кратчайшего пути в многоугольнике
Разработка программы в среде Delphi для нахождения кратчайшего пути между стартом, лежащим в одной из вершин многоугольника, и финишем, находящимся на одной из сторон. Установка опорных точек, контроль целостности вводимых данных, методы решения задачи.
Решение задачи о кратчайшем маршруте
методом Форда 1. Постановка сетевой транспортной задачи. На практике часто встречается задача определения кратчайшего маршрута по заданной сети из начального пункта до конечного пункта маршрута. Транспортная сеть может быть представлена в виде графа (рис.1), дуги которого - транспортные магистрали, а узлы - пункты отправления и назначения.
Объект Recordset и текстовые файлы ASP
Христофоров Юрий В этой статье речь пойдет о построении объекта Recordset на основе информации из текстового файла. Сталкиваясь с задачей представления данных из текстовых файлов (с поддержкой сортировок по нескольким полям, разбиением набора данных по страницам) возникает вопрос: как решить данную задачу наиболее просто? Первый вариант решения - использование массивов.
Кратчайший путь передвижения короля по шахматному полю
Разработка приложения в среде Delphi для нахождения кратчайшего пути передвижения короля по заданному полю, соединяющего два заданных поля доски. Разработка и поиск алгоритма решения задачи, спецификация исходных данных и функций, тестирование программы.
Поиск кратчайшего пути в лабиринте
АННОТАЦИЯ Целью представленной работы является разработка программы “Поиск кратчайшего пути”, которая создает лабиринт и находит кратчайший путь его прохождения.
Поиск кратчайшего пути в лабиринте 2
Министерство образования и науки Российской Федерации Агентство по образованию Тихоокеанский государственный экономический университет Экономический институт
Динозавры
В 1843 году в песчаных плитах геологических отложений Коннектикута (штат на востоке США) палеонтологи обнаружили следы каких-то чудовищных птиц. В сравнении с этими метровыми лапищами, оставившими свои отпечатки в каменной летописи Земли, нога слона казалась миниатюрной. Какого же роста «птички» расхаживали по берегу доисторического моря?