Xreferat.com » Рефераты по информатике и программированию » Поиск кратчайшего пути в лабиринте

Поиск кратчайшего пути в лабиринте

с именем 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) “Требования к информационной и программной совместимости”.


Требования к программной документации


На испытание должен быть предъявлен следующий состав программной документации:

текст программы;

программа и методика испытаний;

описание программы;

описание применения;

Средства и порядок испытаний


Испытания будут проводиться в несколько этапов. Первый этап – проверка правильности работы отдельных модулей программы. Второй этап – проверка работы всех модулей вместе.

Испытания должны проходить при следующих технических и программных средствах:

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

ввести клавишу’х’

(ребро)

на карте поля

отобразилось значение ‘1’

полное

соответствие

6

ввести клавишу’с’

(вершину)

на карте поля

отобразилось значение ‘2’

полное

соответствие

7

навести курсор на

значение‘1’или‘2’ и

ввести клавишу’z’

(т.е.удалить)

на карте поля

отобразилось значение ‘0’

вместо значения‘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("Кратчайший путь найден");

}

В модуль должна передаваться карта поля и координаты двух вершин х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);

Если Вам нужна помощь с академической работой (курсовая, контрольная, диплом, реферат и т.д.), обратитесь к нашим специалистам. Более 90000 специалистов готовы Вам помочь.
Бесплатные корректировки и доработки. Бесплатная оценка стоимости работы.

Поможем написать работу на аналогичную тему

Получить выполненную работу или консультацию специалиста по вашему учебному проекту
Нужна помощь в написании работы?
Мы - биржа профессиональных авторов (преподавателей и доцентов вузов). Пишем статьи РИНЦ, ВАК, Scopus. Помогаем в публикации. Правки вносим бесплатно.

Похожие рефераты: