Программа "Обход конем" - Программирование, компьютеры и кибернетика курсовая работа

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


посмотреть текст работы


скачать работу можно здесь


полная информация о работе


весь список подобных работ


Нужна помощь с учёбой? Наши эксперты готовы помочь!
Нажимая на кнопку, вы соглашаетесь с
политикой обработки персональных данных

Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.

1.1 Формулировка проблемной ситуации
1.3 Поиск оптимального варианта решения
2.2.1 Требования к функциональным характеристикам
Приложение 2. Исходный код программы
В данной работе ставится задача разработки программы - обход конем. Имеется шахматная доска размером N*N, где N?50. Можно ли обойти ее конем из начальной позиции (h, v), побывав при этом на каждой клетке в точности один раз. Возможны два случая: а) в конце обхода конь возвращается в исходную позицию. б) конь завершает обход без возврата в исходную позицию. Определить, каким из вариантов можно совершить обход и можно ли вообще. Обязательна визуализация процесса и пошаговая демонстрация. Приложение разрабатывается на языке программирования C++ в интегрированной среде разработки Microsoft Visual Studio 2008.
1.1 Формулировка проблемной ситуации
Разработка программы «обход конем», с оформлением каждого этапа разработки в соответствующем разделе пояснительной записки.
Перед разработчиком определены следующие цели:
Ознакомление с визуализацией программы.
Определение технических требований к программе.
Создание эффективного алгоритма для решения поставленной задачи с последующей его реализацией на языке программирования C++.
1.3 Поиск оптимального варианта решения
Для решения задачи будет использован метод объектно-ориентированного программирования. Данная концепция позволит существенно упростить задачу, используя следующие подходы:
Скрыв большинство членов класса, можно быть уверенным, что состояние объекта не будет испорчено из вызывающей программы.
Данная возможность позволит описывать классы только их основными свойствами и поведением, что позволит сразу проверить главную идею решения поставленной задачи.
1.4 Проверка эффективности решения
Использование объектно-ориентированного подхода к решению задачи позволит упростить процесс написания кода, а также решение ее с минимальным количеством ошибок, а также минимальной затратой времени.
Программа должна удовлетворять всем требованиям, приведенным в этом разделе.
2.2.1 Требования к функциональным характеристикам
Программа должна находить оптимальный путь обхода шахматной доски.
Программа должна генерировать доску размера, задаваемого пользователем.
Программа должна выводить визуализацию пошагового обхода доски.
Программа должна предотвращать ошибочные действия пользователя.
Программа должна контролировать входную информацию.
При построении данной программы, использовалась библиотек GLUT.
1. Инициализация GLUT производится командой: 
void glutInit(int *argcp, char **argv); 
Первый параметр представляет из себя указатель на количество аргументов в командной строке, а второй - указатель на массив аргументов. Обычно эти значения берутся из главной функции программы: int main(int argc, char *argv[]).
2. Установка параметров окна содержит в себе несколько этапов. Прежде всего необходимо указать размеры окна:
void glutInitWindowSize(int width, int height);
Первый параметр width - ширина окна в пикселях, второй height - высота окна в пикселях. Отмечу также, что если эту команду опустить, то GLUT сам установит размеры окна по умолчанию, обычно это 300x300.
Далее можно задать положение создаваемого окна относительно верхнего левого угла экрана. Делается это командой:
void glutInitWindowPosition(int x, int y);
Необходимо также установить для окна режим отображения информации. Т.е. установить для окна такие параметры как: используемая цветовая модель, количество различных буферов, и т.д. Для этого в GLUT существует команда:
void glutInitDisplayMode(unsigned int mode);
У команды имеется единственный параметр, который может быть представлен одной из следующих констант или комбинацией этих констант с помощью побитового ИЛИ.
3. Создание окна. После того как окно установлено необходимо его создать.
int glutCreateWindow(const char *title);
Эта команда создаёт окно с заголовком, который вы укажете в качестве параметра и возвращает HANDLER окна в виде числа int. Этот HANDLER обычно используется для последующих операций над этим окном, таких как изменение параметров окна и закрытие окна.
4. Установка функций, отвечающих за рисование в окне и изменении формы окна.
После того, как окно, в которое будет выводится или как говорят рендерится графическая информация, подготовлено и создано, необходимо связать с ним процедуры, которые будут отвечать за вывод графической информации, следить за размерами окна, следить за нажатиями на клавиши и т.д. Самая первая и самая необходимая функция которую мы рассмотрим, отвечает за рисование. Именно она всегда будет вызываться операционной системой, чтобы нарисовать (перерисовать) содержимое окна. Итак, задаётся эта функция командой:
void glutDisplayFunc(void (*func)(void));
Единственный параметр этой функции - это указатель на функцию, которая будет отвечать за рисование в окне. Например чтобы функция void Draw(void), определенная в вашей программе отвечала за рисование в окне, надо присоединить ее к GLUT следующим образом: glutDisplayFunc(Draw);
И ещё одна функция, которая по моему мнению является важной - это функция, которая отслеживает изменения окна. Как только у окна изменились размеры, необходимо перестроить вывод графической информации уже в новое окно с другими размерами. Если этого не сделать, то например увеличив размеры окна, вывод информации будет производиться в старую область окна, с меньшими размерами. Определить функцию, отвечающую за изменение размеров окна нужно следующей командой:
void glutReshapeFunc(void (*func)(int width, int height));
Единственный параметр - это указатель на функцию, отвечающую за изменение размеров окна, которая как видно должна принимать два параметра width и height, соответственно ширина и высота нового (измененного) окна.
Ну и последнее, что необходимо сделать, чтобы запустить нашу программу - это войти в так называемый главный цикл GLUT. Этот цикл запускает на выполнение так называемое сердце GLUT, которое обеспечивает взаимосвязь между операционной системой и теми функциями, которые отвечают за окно, получают информацию от устройств ввода/вывода. Для того, чтобы перейти в главный цикл GLUT, надо выполнить единственную команду:
Программа состоит из одного окна, включающего:
glutInit(&argc, argv); для визуализации обхода.
Интерфейс программы продемонстрирован на Рисунке 1.
Основным алгоритмом данной программы является правило Варнсдорфа: При обходе доски, конь следует на ту клетку, с которой можно пойти на минимальное число ещё не пройденных клеток. Если таких клеток несколько, то можно пойти на любую из них.
На Рисунке 2 наглядно представлен алгоритм работы программы.
Рассмотрим функцию нахождения пути обхода:
} moves[] =//Массив вариантов хода коня
multimap seq;//Массив, в который заносится пара значений
for (size_t i = 0; i < sizeof(moves) / sizeof(*moves); ++i) //Расчет вариантов ходов с возможных клеток
for (size_t j = 0; j < sizeof(moves) / sizeof(*moves); ++j)
if (x1 >= 0 && x1 < N &&//Проверка на выход за границы доски
!board[x1][y1])//Проверка был ли конь на этой клетке
for (multimap::iterator i = seq.begin(); i != seq.end(); ++i) //Переход на нужную клетку
const int x0 = x + moves[i -> second].dx;
const int y0 = y + moves[i -> second].dy;
if (x0 >= 0 && x0 < N &&//Проверка на выход за границы доски
y0 >= 0 && y0 < N &&//Проверка был ли конь на этой клетке
Рассмотрим функцию построения графического интерфейса:
void display()//Функция построения графического интерфейса
glBegin(GL_QUADS);//Создание квадратов
glBegin(GL_POINTS); //Создание точек (обозначение коня на доске)
glBegin(GL_LINE_STRIP);//Создание линий, связывающих точки
for (vector::iterator i = solution.begin(); i != solution.end(); ++i)
const int x = i -> x * step + step / 2;
const int y = i -> y * step + step / 2;
В данной программе будем проводить тестирование графического интерфейса:
Для начала протестируем построение самой доски.
Рисунок 3. Изображение шахматной доски.
Рисунок 4. Изображение точки на шахматной доске.
Рисунок 5. Изображение линии на шахматной доске.
Набор основных тестов пройден успешно, программа «Обход конем» работоспособна.
http://msdn.microsoft.com/ru-ru/library/60k1461a(v=VS.90).aspx
http://compgraphics.info/OpenGL/template_glut.php
C++ для начинающих. Серия «Шаг за шагом» / Г. Шилдт;
Наименование программы: Обход конем.
Применение: Нахождение оптимального пути обхода шахматной доски шахматным конем.
Задание преподавателя для проведения лабораторных занятий и выполнения курсовой работы.
Программа предназначена для нахождения пути обхода шахматной доски размером N*N от 5*5, до 40*40 шахматным конем.
1.3.1 Требования к функциональным характеристикам
Программа должна находить оптимальный путь обхода шахматной доски.
Программа должна генерировать доску размера N*N от 5*5 до 40*40, задаваемого пользователем.
Программа должна выводить визуализацию пошагового обхода доски.
Некорректные действия пользователя должны пресекаться программой.
1.4 Требования к составу и параметрам технических средств
Программное обеспечение должно работать на IBM-совместимых персональных компьютерах.
Минимальная конфигурация: тип процессора - Pentium III и выше; объем ОЗУ - 512 Мб и выше.
Наличие 10 Мб свободного пространства на диске.
ЭВМ должна работать под управлением операционной системы не ниже, чем Microsoft Windows XP.
1.5 Требования к информационной и программной совместимости
Программа имеет совместимость с любой системой windows выше XP.
Для начала работы необходимо подключить библиотеку GLUT.
1.8 Требования к программной документации
Результаты выполнения курсовой работы оформлены в виде пояснительной записки. Пояснительная записка оформлена в соответствии с требованиями ГОСТ 19.404-79. ЕСПД.
Разработка данной курсовой работы состоит из следующих этапов:
Анализ способов решения поставленной задачи
Выбор рационального способа решения
Тестирование реализованного программного обеспечения и выводы об его универсальности и функциональности
Приложение 2. Исходный код программы
bool board[N][N];//Массив,содержащий булевские знаения( true - конь на доске, и falce - конь отсутствует)
struct Position//Структура с позициями коня на доске
vector solution;//Вектор, содержащий позиции коня
void display()//Функция построения графического интерфейса
glBegin(GL_QUADS);//Создание квадратов
glBegin(GL_POINTS);//Создание точек (обозначение коня на доске)
glBegin(GL_LINE_STRIP);//Создание линий, связывающих точки
for (vector::iterator i = solution.begin(); i != solution.end(); ++i)
const int x = i -> x * step + step / 2;
const int y = i -> y * step + step / 2;
board[x][y] = true;//Помещаем коня на доску
if (solution.size() == N * N)//Если размер массива принимает значение N*N, то решение найдено и доска полностью пройдена конем.
} moves[] =//Массив вариантов хода коня
multimap seq;//Массив, в который заносится пара значений
for (size_t i = 0; i < sizeof(moves) / sizeof(*moves); ++i) //Расчет вариантов ходов с возможных клеток
for (size_t j = 0; j < sizeof(moves) / sizeof(*moves); ++j)
if (x1 >= 0 && x1 < N &&//Проверка на выход за границы доски
!board[x1][y1])//Проверка был ли конь на этой клетке
for (multimap::iterator i = seq.begin(); i != seq.end(); ++i) //Переход на нужную клетку
const int x0 = x + moves[i -> second].dx;
const int y0 = y + moves[i -> second].dy;
if (x0 >= 0 && x0 < N &&//Проверка на выход за границы доски
!board[x0][y0] &&//Проверка был ли конь на этой клетке
int main(int argc, char **argv)//Вывод на экран
glutInitDisplayMode(GLUT_DOUBLE | GLUT_RGB);
glutInitWindowPosition(40, 450 - 450);
Создание программы движения коня по шахматной доске, ее функциональное и эксплуатационное назначение, требования пользователя к программному изделию. Виды скриншотов, информационная совместимость, программные ограничения и требования к документации. курсовая работа [1,4 M], добавлен 17.02.2010
Программные продукты для решения задачи построения оптимального маршрута. Выбор аппаратных и программных средств для построения маршрута обхода пациентов. Математическая модель муравьиного алгоритма: состав, структура, тестирование, отладка, реализация. дипломная работа [1,9 M], добавлен 03.12.2017
Разработка программы для оценки шахматной ситуации на доске с использованием графического интерфейса. Способы вывода результатов. Библиотека визуальных компонентов. Модульная структура приложения, его внешний вид. Последовательность работы с приложением. контрольная работа [132,2 K], добавлен 07.10.2010
Математическая модель алгоритма с модификацией муравьиной колонии. Выбор аппаратных и программных средств для разработки программы. Особенность построения оптимального маршрута обхода пациентов. Характеристика тестирования и отладки данного проекта. дипломная работа [1,9 M], добавлен 17.11.2017
Разработка программы для тестирования студентов в интегрированной среде разработки Lazarus. Создание формы, отображение графического изображения, выхода, ответа, завершения теста. Процесс выбора ответа студентом. Исходный вид программы тестирования. курсовая работа [388,4 K], добавлен 23.12.2014
Описание использованных структур данных и разработка программы, обеспечивающей сжатие данных по алгоритму LZ77 с пошаговой визуализацией. Описание процедур, функций, структуры приложения и интерфейса пользователя. Тест и анализ работы алгоритма LZ77. курсовая работа [537,9 K], добавлен 28.06.2011
Разработка приложения в среде Delphi для нахождения кратчайшего пути передвижения короля по заданному полю, соединяющего два заданных поля доски. Разработка и поиск алгоритма решения задачи, спецификация исходных данных и функций, тестирование программы. курсовая работа [358,5 K], добавлен 19.10.2010
Работы в архивах красиво оформлены согласно требованиям ВУЗов и содержат рисунки, диаграммы, формулы и т.д. PPT, PPTX и PDF-файлы представлены только в архивах. Рекомендуем скачать работу .

© 2000 — 2021



Программа "Обход конем" курсовая работа. Программирование, компьютеры и кибернетика.
Дипломная работа по теме Рынок и структура потребления мыла туалетного
Өлу Мен Өлімнің Этикалық Мәселелері Реферат
Поздравляю С Защитой Диссертации Картинки
Реферат: Louis Armstrong His Childhood And Early Years
Курсовая работа: Кормление поросят-отъемышей. Скачать бесплатно и без регистрации
Реферат: Формирование и учет затрат на производство продукции
Реферат: Нужны ли России специалисты по Public Relations
Курсовая работа по теме Проблемы адаптации детей к школе
Я В Профессии Учитель Эссе
Сочинение Лето 2022 9 Класс
Контрольная работа по теме Функции денег
Реферат по теме Вексель как средство платежа
Экономика: наука об ограниченности и выборе. Проблема выбора и альтернативная стоимость
Реферат: Ethics Or Moral Philosophy Essay Research Paper
Административная ответственность в области дорожного движения
Сочинения 4 Класс На Темы
Россия 21 Века Реферат
Сочинение Чехов Забыл
Реферат по теме Сцинцилляционные счетчики
Контрольная работа: Уголовная ответственность лиц, совершивших преступление вне пределов Российской Федерации
Социокультуроведческий аспект в обучении английскому языку в старших классах школ с углубленным изучением английского языка - Педагогика дипломная работа
Інституціолізація політичних партій - Государство и право доклад
Концепция построения моделей композитного документооборота - Программирование, компьютеры и кибернетика статья