Курсовая работа по практикуму на эвм: структуры данных и алгоритмы Факультет: прикладной математики и информатики Группа



Скачать 60.95 Kb.
Дата21.12.2012
Размер60.95 Kb.
ТипКурсовая


Министерство образования и науки Российской Федерации

Новосибирский Государственный Технический Университет

Кафедра прикладной математики

Курсовая работа по практикуму на ЭВМ:

структуры данных и алгоритмы

Факультет: прикладной математики и информатики

Группа:

Студент:

Преподаватель:

Новосибирск 2009
1. Условие

Проверить, является ли заданный граф транзитивным, т.е. для любых трёх вершин u, v и w выполняется условие: если u и w, а также v и w смежны, то вершины u и v также смежны.
2. Анализ задачи

2.1. Исходные данные задачи:

n – количество вершин в графе,

m – количество рёбер в графе,

E – множество рёбер графа,

2.2. Результат:

– если граф транзитивен, то result = 1, иначе 0

2.3. Решение:

Неориентированный граф является транзитивным, если . Иными словами, если в графе существуют ребро и вершина v (не совпадающая с u и w), то рёбра и должны существовать или не существовать одновременно. Таким образом, чтобы проверить, является ли неориентированный граф транзитивным, достаточно для каждого его ребра и вершины v, не совпадающей с u и w, проверить, что значение переключательной функции существования ребра равно значению переключательной функции существования ребра .
Формальная постановка задачи

Для каждого ребра и вершины v данного графа, не совпадающей с u и w, проверить, что значение переключательной функции существования ребра gif" name="object14" align=absmiddle width=44 height=19> равно значению переключательной функции существования ребра . При первом же найденном неравенстве ответ будет «граф не является транзитивным», в случае, если неравенств не обнаружено, ответ будет «граф является транзитивным».
3. Структуры данных, используемые для представления исходных данных и результатов задачи

3.1. Входные данные

Внешнее представление неориентированного графа:

<ребро-графа> ::= <вершина-графа> пробел <вершина-графа>

<вершина-графа> ::= число

Внутреннее представление неориентированного графа: матрица смежности (такое представление позволяет быстро определить наличие/отсутствие ребра в графе)

int graph[n][n];

3.2. Выходные данные

Внешнее представление: текстовое сообщение «Graph is transitive» (граф транзитивен) или «Graph is not transitive» (граф не транзитивен)

Внутреннее представление:

bool is_transitive; // Транзитивен ли граф
4. Укрупнённый алгоритм решения задачи

4.1.

{

Граф = ВводГрафа

ПроверкаНаТранзитивность(Граф)

}

4.2. Алгоритм проверки на транзитивность

{

for (i = 0.. N - 1)

{

for (j = i + 1..N - 1)

{

Если (есть ребро {i, j})

{

for (k = 0..N – 1)

{

Если (i <> k И j <> k)

{

Если (СуществованиеРебра({i, k}) <> СуществованиеРебра({k, j}))

{

ОТВЕТ: Граф не транзитивен

}

}

}

}

}

}

ОТВЕТ: Граф транзитивен

}

5. Структура программы

Текст программы разбит на два модуля.

Модуль 1 содержит основную подпрограмму, осуществляющую ввод графа, проверку его на транзитивность и вывод текстового результата.

Модуль 2 содержит подпрограмму проверки графа на транзитивность.

5.1. Состав модуля 1:

Главная функция main:

Назначение: ввод графа, вызов функции проверки, вывод результата

Прототип: int main()

5.2. Состав модуля 2:

Функция is_transitive:

Назначение: проверка графа на транзитивность. Возвращает true в случае, если граф транзитивен и false в случае, если граф не транзитивен.

Прототип: bool is_transitive(int **G, int N)

Параметры: G – матрица смежности графа, N – количество вершин графа.

5.3. Структура программы по управлению:



6. Текст программы на языке C++

main.cpp

#include

#include

#include "transitive.h"
int main()

{

char filename[16];

printf("Filename: "); gets(filename);

FILE *fh = fopen(filename, "r");

if (!fh)

{

perror("Error opening file");

exit(EXIT_FAILURE);

}
int N, M;

fscanf(fh, "%d", &N);

fscanf(fh, "%d", &M);

int **graph = new int *[N];

for (int i = 0; i < N; i++)

{

graph[i] = new int[N];

for (int j = 0; j < N; j++)

{

graph[i][j] = 0;

}

}

for (int i = 0; i < M; i++)

{

int a, b;

fscanf(fh, "%d", &a); a--;

fscanf(fh, "%d", &b); b--;

graph[a][b] = graph[b][a] = 1;

}
if (is_transitive(graph, N))

{

printf("Graph is transitive\n");

} else {

printf("Graph is not transitive\n");

}

exit(EXIT_SUCCESS);

}}

transitive.h

bool is_transitive(int **G, int N);

transitive.cpp

#include
bool is_transitive(int **G, int N)

{

for (int i = 0; i < N; i++)

{

for (int j = i + 1; j < N; j++)

{

if (G[i][j])

{

for (int k = 0; k < N; k++)

{

if (i != k && j != k)

{

if ((bool)G[i][k] != (bool)G[k][j])

{

return false;

}

}

}

}

}

}
return true;

}
7. Набор тестов

Тест 1: Пустой граф

Входные данные: 5

0

Выходные данные: Graph is transitive
Тест 2: Граф из двух вершин

Входные данные: 2

1

1 2

Выходные данные: Graph is transitive
Тест 3: Изолированные вершины

Входные данные: 5

3

2 3

3 4

4 2

Выходные данные: Graph is transitive

Тест 4: Полный граф

Входные данные: 7

21

1 2

1 3

1 4

1 5

1 6

1 7

2 3

2 4

2 5

2 6

2 7

3 4

3 5

3 6

3 7

4 5

4 6

4 7

5 6

5 7

6 7

Выходные данные: Graph is transitive
Тест 5: Полный граф из теста 4 без одного ребра

Входные данные: 7

20

1 2

1 3

1 4

1 5

1 6

1 7

2 3

2 4

2 5

2 6

2 7

3 4

3 5

3 6

3 7

4 5

4 6

4 7

5 7

6 7

Выходные данные: Graph is not transitive

Тест 6: Несколько компонент связности

Входные данные: 6

6

1 3

1 6

3 6

2 4

4 5

5 2

Выходные данные: Graph is transitive
Тест 7: Добавили ребро к тесту 6

Входные данные: 6

7

1 3

1 6

3 6

2 4

4 5

5 2

2 6

Выходные данные: Graph is not transitive


Похожие:

Курсовая работа по практикуму на эвм: структуры данных и алгоритмы Факультет: прикладной математики и информатики Группа iconКурсовая работа по практикуму на эвм: структуры данных и алгоритмы Факультет: прикладной математики и информатики Группа
Добавить каждое неупорядоченное четырёхэлементное подмножество множества V исходного графа в список полных четырёхэлементных подграфов...
Курсовая работа по практикуму на эвм: структуры данных и алгоритмы Факультет: прикладной математики и информатики Группа iconКурсовая работа по практикуму на эвм: структуры данных и алгоритмы Факультет: прикладной математики и информатики Группа
По системе двусторонних дорог определить, можно ли, построив какие-нибудь новые три дороги, из заданного города добраться до каждого...
Курсовая работа по практикуму на эвм: структуры данных и алгоритмы Факультет: прикладной математики и информатики Группа iconКурсовая работа по практикуму на эвм: структуры данных и алгоритмы Факультет: прикладной математики и информатики Группа
В системе двусторонних дорог за проезд каждой дороги взимается некоторая пошлина. Найти путь из города a в город b с минимальной...
Курсовая работа по практикуму на эвм: структуры данных и алгоритмы Факультет: прикладной математики и информатики Группа iconКурсовая работа "Структуры и алгоритмы обработки данных" вариант 11 студент группы п 64 Ивантеева А. В
Хранящуюся в файле базу данных загрузить в оперативную память компьютера и построить индексный массив, упорядочивающий данные по...
Курсовая работа по практикуму на эвм: структуры данных и алгоритмы Факультет: прикладной математики и информатики Группа iconРабочая программа «техно kids2 (Развивающая информатика, логика и математика)»
Автор: Ибрагимова А. С., к ф м н., доцент кафедры математики и прикладной информатики, Шмидт Н. М, к п н., доцент кафедры математики...
Курсовая работа по практикуму на эвм: структуры данных и алгоритмы Факультет: прикладной математики и информатики Группа iconИстория и методология прикладной математики и информатики
Изучение истории развития прикладной математики, электронно-вычислительной техники и программирования
Курсовая работа по практикуму на эвм: структуры данных и алгоритмы Факультет: прикладной математики и информатики Группа iconУчебное пособие по дисциплине «Структуры и алгоритмы обработки данных» для специальностей «Программное обеспечение информационных технологий»
Структуры и алгоритмы обработки данных: Учеб пособие. – Мн: бнту, 2010. – 151 с.: ил
Курсовая работа по практикуму на эвм: структуры данных и алгоритмы Факультет: прикладной математики и информатики Группа iconКраткое содержание курса Форматы данных, структура данных Структура программы Подпрограммы, рекурсия
Цели и задачи курса: структуры данных, алгоритмы обработки данных, работа с динамическими структурами, графами
Курсовая работа по практикуму на эвм: структуры данных и алгоритмы Факультет: прикладной математики и информатики Группа iconСтруктуры и алгоритмы обработки данных
Структура данных работа с элементами которой организована по принципу fifo (первый пришел первый ушел) это
Курсовая работа по практикуму на эвм: структуры данных и алгоритмы Факультет: прикладной математики и информатики Группа iconУчебно-методический комплекс «Высокоуровневые методы информатики и программирования»
Автор: Рязанова О. В., ст преподаватель кафедры математики и прикладной информатики
Разместите кнопку на своём сайте:
ru.convdocs.org


База данных защищена авторским правом ©ru.convdocs.org 2016
обратиться к администрации
ru.convdocs.org