Загрузка...
Учебная работа. Курсовая работа: Поиск кратчайшего пути в лабиринте
Целью представленной работы является разработка программки “Поиск кратчайшего пути”, которая делает лабиринт и находит кратчайший путь его прохождения.
программка создана для использования в учебных заведениях, в познавательных целях. Также может быть внедрение в целях самопроверки.
В данной работе приводятся диаграммы потоков данных, диаграммы состояния, диаграммы взаимодействия модулей. Легкодоступным языком описывается методология сотворения программки.
Разработана спецификация функций программки, описано текст программки и результаты тестирования программки.
1 Техническое задание
Введение
Полное заглавие разработки ”Поиск кратчайшего пути”. Данная разработка создана для использования в учебных заведениях. Она делает нахождение кратчайшего пути меж входом в лабиринт и его выходом. Также может быть внедрение для самопроверки решения, принятого человеком.
1.1 Основания для разработки
Данный проект разрабатывается на основании задания на курсовую работу, выданного педагогом Сусловым С.В. студенту 4152 группы Заволоке А.А.
Наименование темы разработки “Поиск кратчайшего пути”.
1.2 Предназначение разработки
программка “Поиск кратчайшего пути” предназначается для нахождения кратчайшего пути меж входом в лабиринт и его выходом.
1.3 Требования к программке
1.3.1 Требования к многофункциональным чертам
Для контакта юзера с программкой нужно выполнение ряда функций:
создание сетки лабиринта;
добавление комнат в лабиринте;
удаление комнат в лабиринте;
добавление дверей в лабиринте ;
удаление дверей в лабиринте ;
ввод входа и выхода, меж которыми нужно отыскать кратчайший путь;
отображение решения;
сохранение лабиринта;
— загрузка сохраненного лабиринта
Входными данными являются комнаты и двери лабиринта, которые вводятся юзером с клавиатуры с помощью движущегося курсора и нажатия определённой клавиши для комнат и для дверей.
Выходными данными является отображение на дисплее в графическом режиме лабиринта и кратчайшего пути.
1.3.2 Требования к надёжности
Программное изделие обязано быть защищено от необмысленных действий юзера. должен быть предусмотрен очень вероятный анализ входной инфы, вводимой юзером. В случае ввода неправильных данных игнорировать попытку ввода.
1.3.3 Условия эксплуатации
программка стабильно и корректно работает при обычных критериях эксплуатации ПЭВМ. Доп критерий эксплуатации не просит.
1.3.4 Требования к составу и характеристикам технических средств
Нужны последующие технические средства:
1) ПЭВМ с тактовой частотой микропроцессора 100 Mhz и выше.
монитор, поддерживающий режим VGA;
8 Мбайт ОЗУ и выше;
клавиатура.
1.3.5 Требования к информационной и программной сопоставимости
Программка обязана корректно работать в ОС Windows’9x.
1.3.6 Требования к маркировке и упаковке
Готовое программное изделие предоставляется (хранится) на дискете 3.5 Дюйма. Требований к маркировке не предъявляется.
1.3.7 Требования к транспортировке и хранению
Хранить программный продукт необходимо при обычных критериях на дискете 3.5 дюйма, другими словами дискета обязана храниться в герметичной, сухой, не гнущейся коробке вдалеке от источников тепла, воды и от магнита.
1.4 Требования к программной документации
Программная документация обязана состоять из:
отлично прокомментированного текста программки;
общего многофункционального описания;
лаконичного описания составляющих программку функций;
схем, иллюстрирующих проект и словесного их описания;
5) управления юзера.
1.5 Технико-экономические характеристики
Создание бесплатной кандидатуры имеющимся на сей день программкам подобного профиля;
Быстрота вычислений.
1.6 Стадии и этапы разработки
Техническое задание
Плановые сроки начала и окончания работы:
Начало: 15.02.07
Окончание: 01.03.07
Эскизный проект
Плановые сроки начала и окончания работы:
Начало: 01.03.07
Окончание: 22.03.07
Технический проект
Плановые сроки начала и окончания работы:
Начало: 22.03.07
Окончание: 12.04.07
Рабочий проект
Плановые сроки начала и окончания работы:
Начало: 12.04.07
Окончание: 17.05.07
Ввод в эксплуатацию
Плановые сроки начала и окончания работы:
Начало: 17.05.07
Окончание: 24.05.07
1.7 Порядок контроля и приёмки
Испытание обязано проводиться совмесно с заказчиком и разрабом в согласовании с “Программкой и методикой испытаний “.
2. Эскизный проект
2.1 Контекстная диаграмма
Входными данными должны быть координаты вершин многоугольника. Координаты рациональней не вводить, поэтому что это будет весьма долгий процесс, а смоделировать программку так чтоб юзер мог перемещать курсор по сетке лабиринта и нажатием кнопок расставлять комнаты либо двери. Выходными данными являются изображение лабиринта и итог поиска пути. Потоки входных и выходных данных можно узреть на контекстной диаграмме .
При работе с данной программкой нужно наличие трёх основных компонент : юзер, комп и программка (рис.2.1).
лабиринт
— юзер
Жёсткий диск
Набросок 2.1 — Контекстная диаграмма
юзер получает от программки итог – кратчайший путь в лабиринте, который вышел опосля обработки введённых данных – координат дверей и комнат. Итог программки по мере необходимости быть может сохранён.
2.2 Словарь данных
Лабиринт – огромное количество комнат, соединённых меж собой дверьми.
Комната – символически изображенный квадрат, данный в лабиринте.
дверь –устройство, соединяющее комнаты.
Данные редактирования – изменение лабиринта, т.е. ввод комнат и дверей, также их удаление.
Итог – Кратчайший путь в лабиринте.
2.3 Диаграмма состояний
Набросок 2.3 – Диаграмма состояний
состояние 0 – загрузка программки – изначальное состояние, в каком находится программка опосля загрузки. В этом состоянии юзер может ознакомиться с управлением либо выйти из программки.
состояние 1 – создание лабиринта – состояние, в каком формируется лабиринт.
состояние 2 – ввод комнаты – в этом состоянии юзер может ввести комнату.
Состояние 3 – ввод двери – в этом состоянии юзер может ввести дверь.
Состояние 4 – удаление комнаты – в этом состоянии юзер (по мере необходимости) может удалить существующую комнату.
Состояние 5 – удаление двери – в этом состоянии юзер (по мере необходимости) может удалить существующую дверь.
Состояние 6 – сохранение лабиринта – юзеру предоставляется возможность сохранить лабиринт.
состояние 7 – загрузка лабиринта – юзеру предоставляется возможность загрузить, ранее сохраненный, лабиринт.
2.4 Построение модели пользовательского интерфейса
Для удобства ввода, редактирования и удаления частей лабиринта, нужно сделать удачный, дружеский интерфейс.
При запуске программки на дисплее возникает сетка, в какой будет вводиться лабиринт. В каждой клетке может находиться комната либо дверь. По сетке передвигается курсор, который управляется при помощи кнопок <
> — ввысь, <
> — вниз, <
> — на Право, <
> — на лево он описывает положение комнаты либо двери. На дисплее повсевременно находится меню подсказки, которое помогает юзеру ориентироваться. В нём указывается клавиши, при помощи которых юзер может задать лабиринт. К примеру, с помощью клавиши <к> происходит ввод комнаты, при всем этом комната отображается в виде точки зелёного цвета, с помощью клавиши <д> происходит ввод двери, которая не рисуется а просто соединяет комнаты и представляет собой две перекрещивающиеся полосы, т.е. можно соединять сходу несколько дверей в комнатах и отрисовывать лабиринт в трёх либо в четырёх направлениях. С помощью клавиши <я> можно редактировать лабиринт т. е. удалять верхушки либо рёбра.
Опосля ввода лабиринта в левом верхнем углу экрана выдаётся приглашение: “Введите вход в лабиринт ” опосля чего же ожидается выбор одной из комнат в лабиринте, при помощи кнопок управления курсром и клавиши <Enter>, при всем этом выдаётся пиглашение: “Введите выход из лабиринта”. Опосля выбора выхода программка выдаёт сообщение: “Кратчайший путь найден ” — в том случае, если он найден либо “пути нет ” — если пути не существует. Если кратчайший путь найден, то он будет показан на графе в виде подсветки красноватым цветом. Дальше предлагается выйти из программки путём нажатия клавиши <Esc> либо начать ввод новейшего лабиринта нажав при всем этом всякую кнопку. При всем этом существует кнопка <c> и <з> соответственно для сохранения лабиринта либо загрузки уже имеющегося.
3 технический проект
3.1 Диаграмма потоков данных
Программка имеет 4 главных процесса, отражающие главные функции программки:
Набросок 3.1 – Диаграмма 1-го уровня
Набросок 3.2 – Детализация процесса “Ввод лабиринта и его редактирование”
3.2 Словарь данных
Лабиринт – огромное количество комнат, соединённых меж собой дверьми.
Комната – символически изображенный квадрат, данный в лабиринте.
дверь –устройство, соединяющее комнаты.
Команда – в процессе диалоговой работы юзера с программкой, нажатие юзером многофункциональной клавиши, за которой закреплено определенное действие. Существует 5 видов: ввод комнаты, ввод двери, удаление (комнаты либо двери), сохранение и выход.
Команда ввод комнаты – нажатие юзером клавиши <к>.
Команда ввод двери — нажатие юзером клавиши <д>.
Команда удаление — нажатие юзером клавиши <я>.
Команда сохранение — нажатие юзером клавиши <с>.
Команда выход — нажатие юзером клавиши <esc>.
Координаты – численное
карта поля – двумерный массив, который содержит координаты всех комнат и дверей.
карта прохождения — двумерный массив, который содержит координаты комнат и дверей, через которые проходит кратчайший путь.
3.3 Спецификация действий
процесс 1 Ввод лабиринта и его редактирование.
Данный процесс служит для формирования лабиринта и его редактирования
Вход: координаты комнат и дверей
Выход: лабиринт
Деяния: Формирование лабиринта методом наполнения его структуры координатами комнат и дверей.
процесс 1.1 Ввод комнаты
До этого чем передать процессу 1 координаты комнат либо дверей, нужно конвертировать команды юзера по расстановке комнат и дверей, в надлежащие координаты для каждой комнаты и двери. Процессы 1.1-1.3 считывают код клавиши, нажатой юзером, и в согласовании с кодом клавиши и местоположением курсора сформировывают код и координаты.
Вход: ввод комнаты
Выход: код и координаты комнаты
процесс 1.2 Ввод двери
Вход: ввод двери
выход:код и координаты двери
процесс 1.3 Удаление комнаты либо двери
Процесс удаления записывает в структуру лабиринта код 0, по данным координатам, что обозначает пустое пространство, т.е. комната либо дверь была удалена из лабиринта.
Вход:удаление
Выход:код и координаты
процесс 2 Поиск пути
Процесс поиск пути получает структуру лабиринта, и в согласовании с ней отыскивает вероятные пути прохождения лабиринта, и методом сопоставления выбирает самый маленький.
Вход: структура лабиринта
Выход: кратчайший путь в лабиринте.
процесс 4 Отображение лабиринта
При вводе комнат либо дверей нужно чтоб юзер лицезрел отображение введенной инфы на дисплее монитора. Данный процесс должен визуализировать лабиринт и отысканный путь на дисплее.
Вход: координаты комнат и дверей
Выход: изображение лабиринта
процесс 3 Сохранение введенных данных в файле
Для того чтоб координаты комнат либо дверей не вводить поновой при любом запуске программки, нужно сохранять их в файл.
Вход: структура лабиринта
Выход: файл с сохраненной структурой лабиринта
процесс 3 Считывание данных из файла
Для того чтоб координаты комнат либо дверей не вводить поновой при любом запуске программки, нужно сохранять их в файл.
Вход: файл с сохраненной структурой лабиринта
Выход: структура лабиринта
3.4 Определение формы представления входных и выходных данных
Входные данные:
Это последовательность знаков, вводимая юзером с клавиатуры.
Выходные данные:
Отображение лабиринта и пути его прохождения на дисплее монитора, также файл с сохраненным лабиринтом.
Команды:
загрузка лабиринта
сохранение лабиринта
создание комнаты
создание двери
удаление комнаты либо двери
выход
3.5 Разработка структуры программки
Исходя из требований к программке, рациональней всего поделить ее на модули, взаимодействие которых показано на рисунке 3.5.1
3.6 Спецификация модулей
Модуль сотворения и прорисовки сетки лабиринта
Входные данные: отсутствуют
Выходные данные: карта поля
Функции: создание карты поля
Модуль ввода и корректировки данных
Входные данные: команды
Выходные данные: карта поля
Функции — ввод данных и предоставление юзеру способности их редактирования.
Модуль считывания и сохранения структуры лабиринта
Входные данные: команды, карта поля
Выходные данные: карта поля , файл
Наружные эффекты: загрузка сохраненного лабиринта, также модуль сохраняет файл на диске.
Функции — считывание и сохранения структуры лабиринта.
Модуль визуализации
Входные данные: координаты комнат и дверей
Выходные данные: отсутствуют
Наружные эффекты: на дисплее монитора возникает лабиринт и путь прохождения.
Функции – вывод на экран монитора инфы.
Модуль расчета кратчайшего пути лабиринта
Входные данные: карта поля
Выходные данные: карта прохождения
Функции – нахождение путей прохождения и поиск кратчайшего.
3.7 Переход к тексту программки
Используя материал разработки программки, диаграмму потоков данных, диаграмму состояний перейдем к реализации программки.
Написание программного кода будет проводиться с внедрением среды программирования Borland C++.
Реализация функций программки зависит стопроцентно от программера.
4 Рабочий проект
4.1 Программирование и отладка программки
Исходя из требований к программному обеспечению, программка кодировалась в среде программирования Borland C++ для функционирования в операционной системе Windows 9x. (Смотрите приложение В)
4.2 Тестирование программки
Тестирование программки заключается в проверке работы главных функций. Была разработана и проведена серия тестовых примеров для программки. программка и методика испытаний приведены в приложении В. Результаты тестирования проявили работоспособность программки и его соответствие предъявляемым требованиям.
Предложенное ПО тестировалось как во время разработки, так и опосля её окончания.
Для тестирования делались пробы ввода недействительных данных и пробы выполнить недопустимые деяния как при программировании, так и в режиме взаимодействия с пользователями. Предложенное ПО правильно реагировало на такие деяния.
Заключение
В данной документации была разработана программка “Поиск кратчайшего пути”, которая делает лабиринт и находит кратчайший путь прохождения.
Описана область внедрения программного продукта. Приводятся диаграммы потоков данных, диаграммы состояния, диаграммы взаимодействия модулей. Легкодоступным языком описывается методология сотворения программки.
Разработана спецификация функций программки, описано приложение А
(непременное)
Описание программки
Общие сведения
Наименование программки: “Поиск кратчайшего пути”
Для функционирования программки нужна Операционная Система Windows 9x.
Шифровка выполнялась в среде программирования Borland C++.
Функциональное предназначение
Классы задач, которые решаются при помощи программки: программка находит кратчайший путь в лабиринте.
Описание логической структуры
программка имеет главную функцию main, которая описана в файле sapr_kyrsovik.cpp, с которой начинается выполнение программки. Также программка имеет библиотечные функции, которые описаны в заголовочном файле head.h. Заголовочный файл содержит все другие функции, применяемые в пограмме. программка имеет структуру с именованием Lab, которая содержит двухмерный массив карты лабиринта (Мар[MY][MX]) и двухмерный массив карты прохождения (Put[MY][MX]). В эту структуру делается запись координат комнат и дверей лабиринта.
программка состоит из последующих функций:
int Grin(struct Lab *P)
Она делает:
инициализацию графики: очищается экран, врубается графический режим
отрисовывают сетку лабиринта
инициализацию масивов структуры P
void Rasstan(struct Lab *P) – функция расставляет комнаты и двери на карте поля, также удаляет их, это реализуется при помощи кнопок управления курсором (<
> — ввысь, <
> — вниз, <
> — на Право, <
> — на лево) и кнопок специального предназначения (к примеру, с помощью клавиши <к> происходит ввод комнаты, с помощью клавиши <д> происходит ввод двери, с помощью клавиши <я> можно удалять комнаты либо двери). Эта функция вызывает доп две функции:
void vyvod(int x, int y) – функция отрисовывают рамочку белоснежного цвета, служащую курсором для расстановки и удаления комнат и дверей также служащую для ввода входа и выхода в лабиринте.
void maska (int x, int y) – функция прячет(закрашивает) курсор.
void Vvod(struct Lab *P, int *x1, int *y1, int *x2,int *y2) – функция запрашивает ввести вход в лабиринт, опосля чего же при помощи кнопок управления курсором и клавиши Enter функция считывает вход, дальше функция запрашивает ввести выход.
int Find(struct Lab *P, int x1, int y1, int x2,int y2) – делает поиск пути.
void Puty(struct Lab *P, int x1, int y1, int x2,int y2) – функция прорисовывает путь.
Применяемые технические средства
Нужны последующие технические средства:
486 DX-4 100 MHz машина — комплекс технических средств, предназначенных для автоматической обработки информации в процессе решения вычислительных и информационных задач) (либо вычислительной системы) которое делает арифметические и логические операции данные программкой преобразования инфы управляет вычислительным действием и коор и выше;
8 Мб ОЗУ и выше;
монитор, мышь и клавиатура.
Вызов и загрузка
Вызов программки осуществляется средством пуска файла sapr_kyrsovik.exe. программка занимает 40 б.
Входные данные
Входными данными являются комнаты и двери, которые вводятся путём нажатия кнопок специального предназначения:
чтоб ввести комнату нужно надавить кнопку <к>;
чтоб ввести дверь нужно надавить кнопку <д>;
чтоб удалить комнату либо дверь нужно надавить кнопку <я>.
Выходные данные
Выходными данными является отображение введённого лабиринта, т. е. отображение комнат и дверей, также отображение отысканного кратчайшего пути в лабиринте, и в случае сохранения — файл.
ПРИЛОЖЕНИЕ Б
(справочное)
Описание внедрения
Предназначение программки
программка “Поиск кратчайшего пути” находит кратчайший путь в лабиринте.
Условия внедрения
Нужны последующие технические средства:
1) 486 DX4 100 микропроцессор и выше;
8 Мбайта ОЗУ и выше;
монитор, Клавиатура.
Программка создана для работы в ОС Windows 9x.
Описание задачки
Программка “Поиск кратчайшего пути” находит кратчайший путь в лабиринте.
Входные и выходные данные
Входные данные:
Входными данными являются комнаты и двери, которые вводятся путём нажатия кнопок специального предназначения:
чтоб ввести комнату нужно надавить кнопку <к>;
чтоб ввести дверь нужно надавить кнопку <д>;
чтоб удалить комнату либо дверь нужно надавить кнопку <я>.
Выходные данные:
Выходными данными является отображение введённого лабиринта, т. е. отображение комнат и дверей, также отображение отысканного кратчайшего пути в лабиринте, и в случае сохранения — файл.
Приложение В.
(непременное)
Программка и методика испытаний
Объект испытаний
Объектом испытаний является программка “Поиск кратчайшего пути”, которая создана для нахождения кратчайшего пути в лабиринте.
Цель испытаний
Целью проведения испытаний является проверка работоспособности разработанных функций программного обеспечения, также проверка соответствия задач, реализованных в программке с теми, которые были поставлены заказчиком.
Требования к программке
Во время испытаний нужно проверить соответствие требований на программку, обозначенных в “Техническом задании”, а конкретно:
1)
“Требования к многофункциональным чертам”;
2) “Требования к надёжности”;
3) “Требования к составу и характеристикам технических средств”;
4) “Требования к информационной и программной сопоставимости”.
Требования к программной документации
На испытание должен быть предъявлен последующий состав программной документации:
текст программки;
программка и методика испытаний;
описание программки;
описание внедрения;
средства и порядок испытаний
Тесты будут проводиться в несколько шагов. 1-ый шаг – проверка корректности работы отдельных модулей программки. 2-ой шаг – проверка работы всех модулей совместно.
Тесты должны проходить при последующих технических и программных средствах:
486 DX4 100 машина — комплекс технических средств, предназначенных для автоматической обработки информации в процессе решения вычислительных и информационных задач) (либо вычислительной системы) которое делает арифметические и логические операции данные программкой преобразования инфы управляет вычислительным действием и коор и выше;
8 Мбайта ОЗУ и выше;
монитор, клавиатура.
Программное обеспечение: оболочка Borland C 3.1.
Способы испытаний
При испытании программки будет употребляться стратегия “чёрного ящика” а именно последующие способы:
эквивалентное разбиение;
предположение о ошибке;
Эквивалентное разбиение
:
1) Для неверного класса эквивалентности нужно проверить последующие испытания:
ввести клавиши ‘g’, ’d’, ‘v’,…1, 2, 3, ….
Итог: программка не риагирует на введённые клавиши.
2) Для правильного класса эквивалентности нужно проверить последующие испытания:
ввести клавиши ‘к’, ’д’
Итог: на мониторе показываются комнаты и двери.
Предположение о ошибке
Для функции «Rasstan», испытание нужно проводить по способу «Предположение о ошибке». Для тесты данной функции нужно выполнить последующие деяния:
Проверка №1:
Надавить кнопку <к>;
Итог:На дисплее возникла точка, которая обозначает комнату.
Проверка №2:
Надавить кнопку <д>;
Итог:На дисплее возник отрезок, обозначающий дверь.
Проверка №3:
Надавить кнопку <я>, на комнате;
Итог:Изображение комнаты пропало, а на его месте будет пусто.
Для функции «Vvod», испытание нужно проводить по способу «Предположение о ошибке». Для тесты данной функции нужно выполнить последующие деяния:
Проверка №1:
При запросе входа в лабиринт надавить кнопку <enter> на пустом месте;
Итог:Ничего не произойдет
Проверка №2:
При запросе выхода из лабиринта надавить кнопку <enter> на двери;
Итог:ничего не произойдет
Проверка №3:
При запросе входа в лабиринт надавить кнопку <enter> на комнате;
Итог:программка попросит ввести выход.
Испытания для программки:
1) ввести раздельно стоящие, не связанные комнаты и ввести вход и выход. программка выдаёт итог
Итог: Путь не найден.
2) ввести верный лабиринти отыскать путь меж входом и выходом. программка выдаёт итог
Итог: Кратчайший путь найден.
Тесты по способу “белоснежного ящика”:
Для тестирования принято решение применить пошаговое тестирование сверху вниз (нисходящее), при котором тестирование начинается с верхнего, головного модуля программки, причём модули будут тестироваться не изолированно друг от друга, а подключаться поочерёдно для выполнения теста к набору уже ранее оттестированных модулей.
Тестируемый
модуль
:
void Rasstan(struct Lab* P)
{
int x=1 , y=1;
char a;
do{
a=getch();
if(!a) a=getch();
switch (a)
{
case 80 :if (y<MY) ++y ;break;
case 72 :if (y>1 ) —y ;break;
case 75 :if (x>1 ) —x ;break;
case 77 :if (x<MX) ++x ;break;
case ‘z’ :P->Map[y][x]=0 ;
break;
case ‘x’ :P->Map[y][x]=1 ;
break;
case ‘c’ :P->Map[y][x]=2 ;
break;
case 27 : exit(0);
}
}while(a!=13);
}
Этот модуль должен получать карту поля из структуры лабиринта, сделаем её .
— Для этого модуля имеем последующие испытания (Таблица 1):
Таблица 1 – Испытания для модуля Rasstan
№
теста
действие
Событие
Соответствие
—
— Аспект тестирования: покрытие решений
1
Надавить кнопку <↑>
(ввысь)
курсор переместился
ввысь
полное
соответствие
2
Надавить кнопку<↓>
(вниз)
курсор переместился вниз
полное
соответствие
3
Надавить кнопку<←>
(на лево)
курсор переместился на лево
полное
соответствие
4
Надавить кнопку<→>
(на Право)
курсор переместился
на право
полное
соответствие
5
ввести кнопку’х’
(ребро)
на карте поля
отобразилось
полное
соответствие
6
ввести кнопку’с’
(верхушку)
на карте поля
отобразилось
полное
соответствие
7
навести курсор на
ввести кнопку’z’
(т.е.удалить)
на карте поля
отобразилось
заместо значения‘2’либо‘1’
полное
соответствие
8
Надавить кнопку‘Esc’
выход из программки
полное
соответствие
Аспект тестирования: покрытие критерий
9
Надавить кнопку <↑>
(ввысь) и передвигать
курсор до того времени,
пока не достигнет
границы
— Курсор не выходит
за границы поля
полное
соответствие
10
Надавить кнопку<↓>
(вниз) и передвигать
курсор до того времени,
пока не достигнет
границы
— Курсор не выходит
за границы поля
полное
соответствие
11
Надавить кнопку<←>
(на лево) и передвигать
курсор до того времени,
пока не достигнет
границы
— Курсор не выходит
за границы поля
полное
соответствие
12
Надавить кнопку<→>
(на Право) и передвигать
курсор до того времени,
пока не достигнет
границы
— Курсор не выходит
за границы поля
полное
соответствие
Тестируемый модуль:
void Vvod(struct Lab* P, int* x1, int* y1, int* x2, int* y2)
{
gotoxy(3,2);printf(«Введите вход в лабиринт»);
int x=1,y=1;
char a;
do{
a=getch();
if(!a) a=getch();
CursorHide(x,y);
switch(a){
case 80 :if (y<MY) ++y ;break;
case 72 :if (y>1 ) —y ;break;
case 75 :if (x>1 ) —x ;break;
case 77 :if (x<MX) ++x ;break
case 27 :exit(0);
}
if ((a==13) && (P->Map[y][x]==2)) break;
}while(1);
*x1=x;*y1=y;
gotoxy(3,4);printf(«Введите выход из лабиринта»);
do{0
a=getch();
if(!a) a=getch();
switch(a){
case 80 :if (y<MY) ++y ;break;
case 72 :if (y>1 ) —y ;break;
case 75 :if (x>1 ) —x ;break;
case 77 :if (x<MX) ++x ;break;
case 27 :exit(0);
}
if ((a==13) && (P->Map[y][x]==2)) break;
}while(1);
*x2=x;*y2=y;
gotoxy(3,5); printf(«x2=%3i y2=%3i «,x,y);
}
—
— Для этого модуля имеем последующие испытания (Таблица 2):
Таблица 2 – Испытания для модуля Vvod
№
теста
действие
Предполагаемое поведение
Функции
Соответствие
—
— Аспект тестирования: покрытие решений
1
Надавить кнопку <↑>
(ввысь)
курсор должен
переместиться ввысь
полное
соответствие
2
Надавить кнопку<↓>
(вниз)
курсор должен
переместиться вниз
полное
соответствие
3
Надавить кнопку<←>
(на лево)
курсор должен
переместиться на лево
полное
соответствие
4
Надавить кнопку<→>
(на Право)
курсор должен
переместиться на право
полное
соответствие
5
Надавить кнопку‘Esc’
выход из программки
полное
соответствие
Аспект тестирования: покрытие критерий
6
Надавить кнопку <↑>
(ввысь) и передвигать
курсор до того времени,
пока не достигнет
границы
— Курсор не должен выходить
за границы поля
полное
соответствие
7
Надавить кнопку<↓>
(вниз) и передвигать
курсор до того времени,
пока не достигнет
границы
— Курсор не должен выходить
за границы поля
полное
соответствие
8
Надавить кнопку<←>
(на лево) и передвигать
курсор до того времени,
пока не достигнет
границы
— Курсор не должен выходить
за границы поля
полное
соответствие
9
Надавить кнопку<→>
(на Право) и передвигать
курсор до того времени,
пока не достигнет
границы
— Курсор не должен выходить
— за границы поля
полное
соответствие
10
навести курсор на
дверь и надавить
Enter
— Функция не будет реаги-
— ровать на ввод
полное
соответствие
11
навести курсор на
комнату и надавить
Enter
Функция обязана попроси
ть ввести выход из лаби
ринта.
полное
соответствие
Тестируемый модуль:
int Find(struct Lab *P,int x1,int y1,int x2, int y2)
{
int x,y,k=1,F=1;
P->Put[y2][x2]=k;
while(F)
{
F=0;
for(x=1;x<=MX;x++)
{
for(y=1;y<=MY;y++)
{
if (P->Put[y][x]==k)
{
if (P->Map[y+1][x]!=0 && P->Put[y+1][x]==0)
{ P->Put[y+1][x]=k+1;F=1;}
if (P->Map[y-1][x]!=0 && P->Put[y-1][x]==0)
{ P->Put[y-1][x]=k+1;F=1;}
if (P->Map[y][x+1]!=0 && P->Put[y][x+1]==0)
{ P->Put[y][x+1]=k+1;F=1;}
if (P->Map[y][x-1]!=0 && P->Put[y][x-1]==0)
{ P->Put[y][x-1]=k+1;F=1;}
}
}
}
k++;
}
if (P->Put[y1][x1]==0)
{
gotoxy(3,7);printf(«Путь не найден»);
}
else
{
gotoxy(3,7);printf(«Кратчайший путь найден»);
}
В модуль обязана передаваться карта поля и координаты 2-ух вершин х1,y1
и х2,y2 полученые от функции Vvod, меж которыми нужно отыскать
кратчайший путь.
— Для этого модуля имеем последующие испытания (Таблица 3):
Таблица 3 – Испытания для модуля Find
№
теста
действие
Предполагаемое поведе-
ние функции
Соответствие
—
— Аспект тестирования: покрытие решений/критерий
1
нужно сформи-
ровать лабиринт и
ввести две верхушки,
меж которыми
нужно отыскать
кратчайший путь
функция обязана отыскать путь
и выдать соответственное
сообщение
полное
соответствие
2
нужно сформи-
ровать несвязаный
лабиринт и ввести 2
верхушки, меж
которыми необходи-
мо отыскать путь
функция не обязана отыскать
путь и выдать соответст-
вующее сообщение
полное
соответствие
текст программки
#include<d:4termbcbinsuslovhead.h>
void main()
{
static struct Lab P;
int X1,X2,Y1,Y2;
char a;
do{
Grin(&P);
// q(&P);
Rasstan(&P);
Vvod(&P,&X1,&Y1,&X2,&Y2);
if(!Find(&P,X1,Y1,X2,Y2))
{
gotoxy(3,7);printf(«Путь не найден»);
}
else
{
gotoxy(3,7);printf(«Кратчайший путь:»);
Puty(&P,X1,Y1,X2,Y2);
}
// q(&P);
gotoxy(3,8); printf(«Press Esc to exit or any key to continue»);
a=getch();
}while(a!=27);
closegraph();
}
Заголовочный файл:
#include<conio.h>
#include<stdio.h>
#include<stdlib.h>
#include<graphics.h>
#include<dos.h>
const
SX=10, //координаты начала
SY=130,//
MX=30, // колво клеток по осям
MY=17,
R =20,
SetkaColor =DARKGRAY ,
RebroColor =GREEN,
UzelColor =GREEN,
CursorColor=15,
PutColor =RED ;
struct Lab
{
int Map[MY+2][MX+2];
// карта лаб 0-непроходимо 1-дверь 2-комната
int Put[MY+2][MX+2];
// карта прохождения 1-непроходит
};
int Grin(struct Lab* P)
{
int gdriver = DETECT,gmode, errorcode;
initgraph(&gdriver, &gmode,»»);
errorcode = graphresult();
if (errorcode != grOk)
{
printf(«Graphics error: %sn», grapherrormsg(errorcode));
printf(«Graphics error:Press any key:»);
getch();
exit(1);
};
int x, y;
for(y=0;y<MY+2;y++)
for(x=0;x<MX+2;x++)
{
P->Map[y][x]=0; /*Инициализирует массивы*/
P->Put[y][x]=0;
}
for(y=0;y<MY+2;y++)
{
P->Put[y][0 ]=-1;
P->Put[y][MX+1]=-1;
}
for(x=0;x<MX+2;x++)
{
P->Put[0 ][x]=-1;
P->Put[MY+1][x]=-1;
}
//Setka
setcolor(SetkaColor);
for(y=0;y<=MY;y++)
for(x=0;x<=MX;x++)
{
line(SX+x*R,SY ,SX+x*R ,SY+R*MY);
line(SX ,SY+y*R,SX+MX*R,SY+y*R);
}
return 0;
}
void maska(int x,int y)
{
setcolor(0);
rectangle(SX+(x-1)*R+1,SY+(y-1)*R+1,SX+x*R-1,SY+y*R-1);
}
void vyvod(int x,int y)
{
setcolor(CursorColor);
rectangle(SX+(x-1)*R+1,SY+(y-1)*R+1,SX+x*R-1,SY+y*R-1);
}
void Rasstan(struct Lab* P)
{
int x=1 , y=1; //Коорты курсора
gotoxy(55,4); printf(«Управление:»);
gotoxy(55,5); printf(» я — удалить»);
gotoxy(55,6); printf(» д — дверь«);
gotoxy(55,7); printf(» к — комната»);
gotoxy(55,8); printf(» Enter — ввести»);
vyvod(x,y);
char a;
do{
a=getch();
if(!a) a=getch();
maska(x,y);
switch (a)
{
case 80 :if (y<MY) ++y ;break; /* вниз */
case 72 :if (y>1 ) —y ;break; /* ввысь */
case 75 :if (x>1 ) —x ;break; /* на лево */
case 77 :if (x<MX) ++x ;break; /* на Право*/
case ‘z’ :P->Map[y][x]=0 ;
setcolor(0);setfillstyle(1,0);
bar(SX+(x-1)*R+1,SY+(y-1)*R+1,SX+x*R-1,SY+y*R-1);
break;
//раставляем ком и дв
case ‘l’ :P->Map[y][x]=1 ;
setcolor(RebroColor);
line(SX+x*R-R/2,SY+(y-1)*R+1,SX+x*R-R/2,SY+y*R-1);
line(SX+(x-1)*R+1,SY+y*R-R/2,SX+x*R-1,SY+y*R-R/2);
break;
case ‘r’ :P->Map[y][x]=2 ;
setcolor(UzelColor);setfillstyle(1,UzelColor);
fillellipse(SX+x*R-R/2,SY+y*R-R/2,R/2-1,R/2-1);
break;
case 27 : exit(0);//vixod iz programmi
}
vyvod(x,y);
}while(a!=13);
maska(x,y);
}
void Vvod(struct Lab* P, int* x1, int* y1, int* x2, int* y2)
{
gotoxy(3,2);printf(«Введите вход в лабиринт»);
int x=1,y=1;
char a;
vyvod(x,y);
do{
a=getch();
if(!a) a=getch();
maska(x,y);
switch(a){
case 80 :if (y<MY) ++y ;break; /* вниз */
case 72 :if (y>1 ) —y ;break; /* ввысь */
case 75 :if (x>1 ) —x ;break; /* на лево */
case 77 :if (x<MX) ++x ;break; /* на Право*/
case 27 :exit(0);
}
vyvod(x,y);
if ((a==13) && (P->Map[y][x]==2)) break;
}while(1);
maska(x,y);
*x1=x;*y1=y;
gotoxy(3,3); printf(«x1=%3i y1=%3i «,x,y);
gotoxy(3,4);printf(«Введите выход»);
vyvod(x,y);
do{
a=getch();
if(!a) a=getch();
maska(x,y);
switch(a){
case 80 :if (y<MY) ++y ;break; /* вниз */
case 72 :if (y>1 ) —y ;break; /* ввысь */
case 75 :if (x>1 ) —x ;break; /* на лево */
case 77 :if (x<MX) ++x ;break; /* на Право*/
case 27 :exit(0);
}
vyvod(x,y);
if ((a==13) && (P->Map[y][x]==2)) break;
}while(1);
maska(x,y);
*x2=x;*y2=y;
gotoxy(3,5); printf(«x2=%3i y2=%3i «,x,y);
}
int Find(struct Lab *P,int x1,int y1,int x2, int y2)
{
int x,y,k=1,F=1;
P->Put[y2][x2]=k;
while(F)
{
F=0;
for(x=1;x<=MX;x++)
{
for(y=1;y<=MY;y++)
{
if (P->Put[y][x]==k)
{
if (P->Map[y+1][x]!=0 && P->Put[y+1][x]==0)
{ P->Put[y+1][x]=k+1;F=1;}
if (P->Map[y-1][x]!=0 && P->Put[y-1][x]==0)
{ P->Put[y-1][x]=k+1;F=1;}
if (P->Map[y][x+1]!=0 && P->Put[y][x+1]==0)
{ P->Put[y][x+1]=k+1;F=1;}
if (P->Map[y][x-1]!=0 && P->Put[y][x-1]==0)
{ P->Put[y][x-1]=k+1;F=1;}
}
}
}
k++;
}
if (P->Put[y1][x1]==0) return 0; else return 1;
}
void Puty(struct Lab* P,int x1, int y1, int x2, int y2)
{
int x=x1,y=y1;
int k;
setcolor(PutColor);
setfillstyle(1,PutColor);
while(!(x==x2 && y==y2))
{
fillellipse(SX+x*R-R/2,SY+y*R-R/2,R/4,R/4);
k=P->Put[y][x]-1;
if(P->Put[y+1][x ]==k){y++;continue;}
if(P->Put[y-1][x ]==k){y—;continue;}
if(P->Put[y ][x+1]==k){x++;continue;}
if(P->Put[y ][x-1]==k){x—;continue;}
}
fillellipse(SX+x*R-R/2,SY+y*R-R/2,R/4,R/4);
}
приложение Г
— Управление юзера
П.1. Предназначение программки
программка “Поиск кратчайшего пути” создана для нахождения кратчайшего пути в лабиринте. программка создана для использования в учебных заведениях, в познавательных целях. Также может быть внедрение в целях самопроверки.
П.2. Условия эксплуатации программки
Для того, чтоб работать с данной программкой для вас нужно иметь индивидуальный комп (минимум 486) с 8 МБ ОЗУ и естественно операционную систему Windows 9x.
П.3. Выполнение программки
порядок действий, обеспечивающий пуск программки :
— загрузить операционную систему Microsoft Windows9x
— если Для вас не удалось загрузить операционную систему Microsoft
Windows 9x либо у Вас нет операционной системы Microsoft Windows 9x,
то обратитесь в отдел технической поддержки компании Microsoft для
получения соответственных инструкций. (электрический адресок отдела
технической поддержки:
)
— запустить на выполнение файл sapr_kyrsovik.exe из директории, в какой он размещен.
— Опосля пуска программки на дисплее монитора можно ознакомиться с управлением программки.
— Кнопками управления следует расставить двери и комнаты в лабиринте, опосля чего же ввести вход и выход из лабиринта.
— подождать пока программка выдаст итог и выйти из программки либо начать создание новейшего лабиринта.
— Для того, чтоб окончить работу с программкой нужно надавить <esc> в хоть какой момент выполнения программки.
]]>