Поиск кратчайшего пути в лабиринте
Программа состоит из следующих функций:
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);