Автор работы: Пользователь скрыл имя, 16 Февраля 2013 в 14:40, курсовая работа
Цель: Найти медиану графа, т.е. такую его вершину, что сумма его расстояний от неё до остальных минимальна.
Данная цель достигается решением следующих задач:
выбор алгоритма
выбор метода решения
разработка на языке программирования С
проектирование тестов
ВВЕДЕНИЕ 3
ВЫБОР АЛГОРИТМА 4
РАЗРАБОТКА ПРОГРАММЫ НА ЯЗЫКЕ ПРОГРАММИРОВАНИЯ C 8
ОТЛАДКА ПРОГРАММЫ 15
ПРОЕКТИРОВАНИЕ ТЕСТОВ 16
ЗАКЛЮЧЕНИЕ 20
ЛИТЕРАТУРА 21
Для создания перечисленных тестовых ситуаций разработаны тесты, представленные в табл. 3. Входные и выходные данные тестов по возможности выбирались ближе к границам классов эквивалентности.
Таблица 3
Тесты черного ящика для отладки программы
№ |
Вход |
Выход |
Основные ситуации |
1 |
n =0 |
Сообщения: 1, 2, 3, 7 |
2, 10, 11, 14, 17, 20, 23 |
2 |
n =NMAX+1 |
Сообщения: 1, 2, 3, 7 |
3, 10, 11, 14, 17, 20, 23 |
3 |
n =5 Ребра: 0-1 1-0 0-2 0-3 1-3 1-4 2-3 3-4 |
Медиана-3, расстояние - 4 Сообщения: 1, 2, 6, 8, 9 |
1, 4, 7, 10, 11, 12, 18, 13, 20, 22 |
4 |
n =5 Ребра: -0 0-2 0- 0-3 |
Сообщения: 1, 2, 6, 5, 7 |
5, 10, 11, 12, 16, 17, 20, 23 |
5 |
n =5 Ребра: -0 0-3-1 0-4 |
Сообщения: 1, 2, 6, 5,7 |
5, 6, 10, 11, 12, 16, 17, 20, 23 |
6 |
n =5 Ребра: <Ctrl+Z> |
Сообщения: 1, 2, 6, 10, 7 |
10, 11, 12, 19, 17, 20, 23 |
7 |
n =5 Ребра: 1-6 2-3 4-4 |
Сообщения: 1, 2, 6, 4, 7 |
9, 10, 11,12, 15, 17, 20, 23 |
8 |
n =5 Ребра: (-1)-3 1-3 3-2 0-2 2-4 |
Сообщения: 1, 2, 6, 4, 7 |
8, 10, 11, 12, 15, 17, 20, 23 |
9 |
n =5 Ребра: (-1)-3 7-(-2) 3-2 3-4 3-5 |
Сообщения: 1, 2, 6, 4, 7 |
8, 9, 10, 11, 12, 15, 17, 20, 23 |
10 |
n =5 Ребра: 0-1-2 0-2 2-1 2-3 |
Сообщения: 1, 2, 6, 5, 7 |
6, 10, 11, 12, 16, 17, 20, 23 |
11 |
n =5 Ребра: 0-1 0-2 0-3 1-3 1-4 2-3 3-4 |
Медиана-3, расстояние - 4 Сообщения: 1, 2, 6, 9 |
1, 4, 7, 10, 11, 12, 18, 13, 20, 22 |
12 |
n =5 Ребра: 0-1 0-2 0-3 1-3 1-4 2-3 |
Медиана-3, расстояние - 4 Сообщения: 1, 2, 6, 9 |
1, 4, 7, 10, 11, 12, 18, 13, 20, 22 |
В ребрах вершины обозначаются через тире для наглядности.
Тесты белого ящика.
Тесты белого ящика — тестирование кода на предмет логики работы программы и корректности её работы с точки зрения компилятора того языка на котором она писалась.
Техника тестирования по принципу Белого ящика, позволяет проверить внутреннюю структуру программы. Исходя из этой стратегии тестировщик получает тестовые данные путем анализа логики работы программы.
Таблица 4
Комбинаторное покрытие условий тестами черного ящика
Модуль |
Элементарное условие |
Номера тестов | |
Истина |
Ложь | ||
main |
n<1 |
1 |
2, 3, 4 и др. |
main |
n>NMAX |
2 |
1, 3, 4 и др. |
main |
kz>1 |
4, 5, 7, 8, 9, 10 |
3, 11, 12 |
main |
kz == 4 |
7, 8, 9 |
3, 11, 12 |
main |
kz == 5 |
4, 5, 6, 10 |
3, 7, 8, 9 |
main |
kz== 1 |
3 |
11 |
main |
i< n |
3, 7, 8, 9, 11, 12 |
9 |
main |
j < n |
3, 4, 5, 8, 11, 12 |
7, 9 |
main |
dl < mdl |
3, 7, 11, 12 |
1, 2, 4 и др. |
vv_m_sm |
i<n |
3, 7, 8, 9, 11, 12 |
9 |
vv_m_sm |
j<n |
3, 4, 5, 8, 11, 12 |
7, 9 |
vv_m_sm |
i ==j |
7 |
3, 4, 5 и др. |
vv_m_sm |
while(scanf(“%d%d”,&i,&j)==2) |
3, 11, 12 |
4, 5, 6 и др. |
vv_m_sm |
i< 0 |
8, 9 |
3, 7, 11 и др. |
vv_m_sm |
i>= n |
9 |
3, 4, 5 и др. |
vv_m_sm |
j < 0 |
9 |
3, 4, 5 и др. |
vv_m_sm |
j >= n |
7, 9 |
3, 4, 5 и др. |
vv_m_sm |
g[i][j] ==1 |
3 |
4, 5, 6 и др. |
vv_m_sm |
pp<= 0 |
6 |
3, 4, 5 и др. |
vv_m_sm |
p == 1 |
4, 5 |
3, 6, 7 и др. |
vv_m_sm |
p > 2 |
10 |
3, 4, 5 и др. |
obrab |
i< n |
3, 7, 8, 9, 11, 12 |
9 |
obrab |
j < n |
3, 4, 5, 8, 11, 12 |
7, 9 |
Obrab |
k < n |
3, 4, 5, 7, 8, 9, 11, 12 |
7, 9 |
Obrab |
d[i][k] != 0 |
3, 11 |
12 |
Obrab |
d[i][k]+d[k][j] < d[i][j] |
3, 11 |
3, 11, 12 |
ЗАКЛЮЧЕНИЕ
В ходе курсовой работы была написана программа на языке программирования C, которая находит медиану графа, то есть такую его вершину, что сумма его расстояний от нее до остальных минимальна.
В программе используются следующие определения как граф, путь, длина пути, расстояние, медиана графа.
У графа длина (вес) пути определяется как сумма длин его ребер. Расстояние D[i][j] между вершинами i и j – длина кратчайшего пути между ними. Считается, что расстояние от вершины до нее самой равно нулю: D[i][i] = 0. У не взвешенного графа вес ребра равен 1; длина пути и расстояние измеряются числом ребер.
Кратчайший путь в графе от заданной вершины до одной или до всех вершин можно найти методом обхода в ширину. Кратчайшие пути и расстояния между всеми вершинами быстрее определяются через матрицу расстояний или алгоритм Флойда. В данной курсовой работе при нахождении медианы графа используется алгоритм Флойда. Который формулируется так: пусть в элементе матрицы A[i, j] хранится длина кратчайший пути из вершины i в вершину j, который проходит через некоторые вершины с номерами, не превосходящими k – 1. Если же длины пути из вершины i в вершину k и пути из вершины k в вершину j таковы, что их сумма меньше, чем значение данного элемента матрицы, то его следует переопределить.
Программа состоит из трех функционально-прочных модулей: glav – главная программа, vv_m_sm – ввод графа, obrab – вывод матрицы расстояний.
Все данные между модулями передаются только в виде параметров, глобальных переменных в программе нет. Модуль main сцеплен с модулями vv_m_sm и obrab по формату.
Курсовая работа выполнена в соответствии с требованиями в полном объёме.
ПРИЛОЖЕНИЕ 1
Системные файлы проекта
Main.c
Vv_m_sm.c
Obrab.c
/* graf.h */
/* Определения для функции обработки графов */
#ifndef _GRAFH
#define _GRAFH
#ifndefNMAX
#defineNMAX20 /*максимальное количество вершин графа*/
ПРИЛОЖЕНИЕ 2
Текст программы модуля glav
#include <stdio.h> #include "graf.h"
void main()
{int g[NMAX][NMAX] ={0}; /* matrica smezhnosti grafa */
int d[NMAX][NMAX]; /* matrica rasstoyanii*/
int n,i,j; /* kol-vovershin, nomera vershin*/
int dl=0, z=0; /* min. dlina, vichislaemaya vershina*/
int mdl=99, kz; /*priznak ne svyaznosti, kod zavershenia podprogrammi*/
int status;
clrscr();
puts ("\n Zadacha: naiti mediany grafa, t.e. takyu ego vershiny, chto summa ego rasstoyanii ot nee do ostalnix minimalna \n"); /* vivod zadania*/
puts ("\n Vvedite graf (kol-vo vershin ot 0 do 20): \n"); /* vvedite kol-vo vershin*/
scanf("%d",&n);
if(n>NMAX || n < 1)
{puts ("\n Oshibka: kol-vovershin ot 1 do:\n");
printf("%d",NMAX); /* Oshibka: kol-vo vershin ot 1 do: NMAX */
puts ("\n Reshenie precrasheno\n");
getch();
exit(status-'0'); /*Reshenie precrasheno */
}
else
kz=vv_m_sm(n,g); /* vvod grafa */
if(kz>1)
{if(kz==4)
puts ("\n Oshibka: nomer vershini dolzhen bit ot 0 do : \n");
printf(" %d",n-1); /*Oshibka: nedopustimii nomer */
if(kz==5)
puts ("\n Oshibka: rebro dolzhno soderzhat dve vershini \n") /* Oshibka:kol-vo vershin>2 ili<2*/
puts ("\n Reshenie precrasheno\n");
}
else
{ if(kz==1) /* dublirovanie reber */
puts ("\n Preduprezhdenie: bilo dublirovanie reber \n");
obrab(n,g,d); /* vizov funkcii obrab */
for(i = 0; i< n; i++)
{dl=0;
for(j = 0; j < n; j++) /* vichislenie */
{ if(d[i][j]!=0)
dl = dl + d[i][j]; /* vershini s */
}
if(dl > mdl) /* minimalnim */
{mdl = dl;
z = i;} /* rasstoyaniem */
}
printf("\n Mediana : %d , Rasstoyanie : %d\n",z,mdl); /*vivod minimalnogo rasstoyania*/
}
getch();
}
ПРИЛОЖЕНИЕ 3
Тест программы модуля vv_m_sm.
#include<stdio.h>
#include "graf.h"
vv_m_sm (int n, int g[][NMAX])
{int i, j; /* nomera strok i stolbcov matrici cmezhnosti */
int pr=0; /* priznak dublirovania reber */
int p, pp; /* proverka kol-va versin, ....*/
int status;
puts ("\n Vvedite posledovatelnoct grafa, v konce<Ctrl+Z>\n"); /* vvod reber grafa */
for(i=0; i<n; i++)
for(j=0; j<n; j++)
g[i][j]=0; /* obnulenie grafa */
while((p=scanf("%d%d",&i,&j))=
{if(p<2)
{printf("p1=%d",p);
return 5;}
pp++;
if(i<0 || i>=n || j<0 || j>=n) return 4; /* nedopustimii №*/
{ if(g[i][j]=g[j][i]) pr=1 /*dublirovanie reber*/
g[i][j]=1;
g[j][i]=1; }
return pr;
if(pp<=0)
{puts ("\n Oshibka: net vxodnix dannix\n");
puts ("\n Reshenie prekrasheno\n");
getch();
exit(status-'0'); }
return pr;
ПРИЛОЖЕНИЕ 4
Текст программы модуля obrab
#include "graf.h"
void obrab (int n, int g[][NMAX], int d[][NMAX])
{int i, j; /* nomer vershin, nachalnoi i konecnoi*/
int k; /*nomer vershini is mnozhestva k */
for(i = 0; i < n; i++)
for(j = 0; j < n; j++)
d[i][j] = g[i][j]; /*prisvaivanie matr. passtoyanii mart. vesov*/
for(i = 0; i < n; i++)
d[i][i] = 0; /*passtoanie ot versh. do nee camoi = 0 */
for(k = 0; k < n; k++)
for(i = 0; i < n; i++)
if(d[i][k]!=0)
for(j=0;j<n; j++)
{if(d[i][k]+d[k][j]<d[i][j]) /
d[i][j]=(d[i][j],d[i][k]+d[k][
}
puts ("\n Matrica rasstoyanii\n"); /* vivod matr. rasstoyanii*/
for(i=0;i<n; i++)
printf(" %d",i);
printf( "\n ");
for(i=0;i<7;i++)
printf("");
for(j=0;j<n; j++)
{printf("\n%d:і",j);
for(i=0;i<n; i++)
printf("%d ",d[i][j]);
}
}
ПРИЛОЖЕНИЕ 5
Результаты тестирования программы
Тестирование всей программы с файлом проекта zulka.prj на "правильных" тестах.
Тест 1
Задача: Найти медиану графа, т.е., такую его вершину, что сумма его расстояний от нее до остальных вершин минимальна
Введите граф (количество вершин от 1 до 20):
0
Ошибка: количество вершин должно быть от 1 до: 20
Решение прекращено
Тест 2
Задача: Найти медиану графа, т.е., такую его вершину, что сумма его расстояний от нее до остальных вершин минимальна
Введите граф (количество вершин от 1 до 20):
21
Ошибка: количество вершин должно быть от 1 до: 20
Решение прекращено
Тест 3
Задача: Найти медиану графа, т.е., такую его вершину, что сумма его расстояний от нее до остальных вершин минимальна
Введите граф (количество вершин от 1 до 20):
4
Введите последовательность графа, в конце <Ctrl+Z>:
0 1
0 2
0 3
1 3^ Z
Матрица расстояний:
0 |
1 |
2 |
3 | |
0 |
0 |
1 |
1 |
1 |
1 |
1 |
0 |
0 |
1 |
2 |
1 |
0 |
0 |
1 |
3 |
1 |
1 |
1 |
0 |
Медиана – 0, расстояние – 3
Тест 4
Задача: Найти медиану графа, т.е., такую его вершину, что сумма его расстояний от нее до остальных вершин минимальна
Введите граф (количество вершин от 1 до 20):
5
Введите последовательность графа, в конце <Ctrl+Z>:
0
0 2
0
0-3 ^ Z
Ошибка: ребро должно содержать две вершины
Решение прекращено
Тест 5
Задача: Найти медиану графа, т.е., такую его вершину, что сумма его расстояний от нее до остальных вершин минимальна
Введите граф (количество вершин от 1 до 20):
5
Введите последовательность графа, в конце <Ctrl+Z>:
0
0-3-1
0 4 ^ Z
Ошибка: ребро должно содержать две вершины
Решение прекращено
Тест 6
Задача: Найти медиану графа, т.е., такую его вершину, что сумма его расстояний от нее до остальных вершин минимальна
Введите граф (количество вершин от 1 до 20):
5
Введите последовательность графа, в конце <Ctrl+Z>:
<Ctrl+Z>
Ошибка: нет входных данных
Решение прекращено
Тест 7
Задача: Найти медиану графа, т.е., такую его вершину, что сумма его расстояний от нее до остальных вершин минимальна
Введите граф (количество вершин от 1 до 20):
5
Введите последовательность графа, в конце <Ctrl+Z>:
1 6
2-3
4-4 ^ Z
Ошибка: номер вершины должен быть от 0 до: 4
Решение прекращено
Тест 8
Задача: Найти медиану графа, т.е., такую его вершину, что сумма его расстояний от нее до остальных вершин минимальна
Введите граф (количество вершин от 1 до 20):
5
Введите последовательность графа, в конце <Ctrl+Z>:
-1 3
1 3
3 2
0 2
2 4 ^ Z
Ошибка: номер вершины должен быть от 0 до: 4
Решение прекращено
Тест 9
Задача: Найти медиану графа, т.е., такую его вершину, что сумма его расстояний от нее до остальных вершин минимальна
Введите граф (количество вершин от 1 до 20):
5
Введите последовательность графа, в конце <Ctrl+Z>:
-1 3
7 (-2)
3 2
3 4
3 5 ^ Z
Ошибка: номер вершины должен быть от 0 до: 4
Решение прекращено
Тест 10
Задача: Найти медиану графа, т.е., такую его вершину, что сумма его расстояний от нее до остальных вершин минимальна
Введите граф (количество вершин от 1 до 20):
5
Введите последовательность графа, в конце <Ctrl+Z>:
012
0 2
2 1
2 3 ^ Z
Ошибка: номер вершины должен быть от 0 до: 4
Решение прекращено
Тест 11
Задача: Найти медиану графа, т.е., такую его вершину, что сумма его расстояний от нее до остальных вершин минимальна
Введите граф (количество вершин от 1 до 20):
7
Введите последовательность графа, в конце <Ctrl+Z>:
0 1
0 6
1 6
2 6
2 3
2 4
6 3
3 4
6 4
4 5
6 5
^Z
Матрица расстояний:
0 |
1 |
2 |
3 |
4 |
5 |
6 | |
0 |
0 |
1 |
0 |
0 |
0 |
0 |
1 |
1 |
1 |
0 |
0 |
0 |
0 |
0 |
1 |
2 |
0 |
0 |
0 |
1 |
1 |
0 |
1 |
3 |
0 |
0 |
1 |
0 |
1 |
0 |
1 |
4 |
0 |
0 |
1 |
1 |
0 |
1 |
1 |
5 |
0 |
0 |
0 |
0 |
1 |
0 |
1 |
6 |
1 |
1 |
1 |
1 |
1 |
1 |
0 |
Медиана – 6, расстояние – 6
Тест 12
Задача: Найти медиану графа, т.е., такую его вершину, что сумма его расстояний от нее до остальных вершин минимальна