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



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


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

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

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

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

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

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

Группа:

Студент:

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

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

По системе двусторонних дорог определить, можно ли, построив какие-нибудь новые три дороги, из заданного города добраться до каждого из остальных городов, проезжая не более 100 км.
2. Анализ задачи

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

n – количество городов,

C – список городов,

– множество уникальных имён городов

– декартовы координаты городов на плоскости

f – исходный город,

m – количество дорог,

G – список дорог,
2.2. Результат:

YES, если, построив какие-нибудь новые три дороги, из заданного города можно добраться до каждого из остальных городов, проезжая не более 100км., NO в противном случае.

2.3. Решение:

Математическая модель системы двусторонних дорог – неориентированный взвешенный помеченный граф с весовой функцией , причём . При этом вершины соответствуют городам (метка вершины – название города), а рёбра – двусторонним дорогам. Вес ребра определяется по формуле .

Для того, чтобы определить, можно ли, построив какие-нибудь новые три дороги, из заданного города можно добраться до каждого из остальных городов, проезжая не более 100км., необходимо, для начала, проверить, что расстояние от заданного города до каждого из остальных не превышает 100, и если это не так, то ответ «НЕТ» (очевидно, что в Евклидовом пространстве невозможно построить путь, короче прямого).
В противном случае необходимо проверить, что в графе от вершины, соответствующей заданному городу, до каждой из остальных существует маршрут, своей длинной не превышающий 100 (для проверки существования такого маршрута хорошим алгоритмом является алгоритм Дейкстры). Если данное условие выполняется, ответ к задаче «ДА», иначе следует, перебирая и добавляя в граф различные неупорядоченные тройки (двойки, единичные рёбра, в случае, если граф, дополнительный к данному, содержит менее трёх рёбер) рёбер, вновь и вновь проверять это условие и при его истинности давать ответ «ДА». В случае, если данное условие не выполняется ни для одной тройки рёбер, ответ «НЕТ».
Формальная постановка задачи
Построить граф заданной системы дорог, проверить расстояние от заданного города до остальных, проверить исходный граф на соответствие условию задачи; добавляя в него неупорядоченные тройки рёбер, проверить выполняемость этого условия хотя бы один раз.

В случае, если входные данные корректны (для всех используемых имён городов заданы координаты), результат всегда определён.

Основные подзадачи:

1) Построение графа

2) Построение дополнительного графа

3) Перебор и добавление рёбер

4) Проверка графа на соответствие условию задачи
3. Структуры данных, используемые для представления исходных данных и результатов задачи

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

Внешнее представление системы двусторонних дорог:

<система-дорог> ::= <количество-городов> <список-городов> <список-дорог>

<количество-городов> ::= <натуральное-число>

<список-городов> ::= <город>|<город> <список-городов>

<город> ::= <название-города> <координата> <координата>

<название-города> ::= <буква>|<название-города> <буква>

<координата> ::= <действительное число>

<список-дорог> ::= <дорога>|<дорога> <список-дорог>

<дорога> ::= <город> <город>

Внутреннее представление системы двусторонних дорог:

Поскольку нам необходимо хранить как заданный граф. так и дополнительный к нему, что в сумме даёт полный, разумно будет представить их одной матрицей смежности, добавляя к характеристике рёбер помимо, собственно, веса, булево значение built, принимающее значение И в случае, если ребро принадлежит основному графу и Л, если дополнительному. Для ускорения перебора создадим отдельный массив рёбер дополнительного графа, его размерность равна , где n – количество вершин основного графа, m – количество его рёбер.

map cities_ids; // Соответствие название города => номер
// Ребро графа

struct Road

{

bool built;

float weight;

};

typedef vector > Graph;

Graph roads(cities_c); // Граф
vector > unbuilt_roads(…); // Массив рёбер дополнительного графа

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

Внешнее представление: текстовое сообщение “YES” или “NO” или сообщение об ошибке.

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

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

4.1.

{

Данные = ЧтениеДанных

Граф = ПостроитьГраф(Данные)

Если (УдовлетворяетУсловию(Граф))

{

Ответ: ДА

}

РёбраДополнительногоГрафа = {}

for (i = 0..N - 1)

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

Если (!Граф[i][j]->естьРебро)

{

РёбраДополнительногоГрафа[] = {i, j}

}

while ({i,j,k} = ТройкаРёбер(РёбраДополнительногоГрафа))

{

Граф->ДобавитьРебро(i);

Граф->ДобавитьРебро(j);

Граф->ДобавитьРебро(k);

Если (УдовлетворяетУсловию(Граф))

{

Ответ: ДА

}

Граф->УбратьРебро(i);

Граф->УбратьРебро(j);

Граф->УбратьРебро(k);
}

Ответ: НЕТ

}

4.2. Алгоритм проверки условия

{

for (каждая вершина v из V)

{

d[v] ← ∞;

Pr[v] ← nil;

}

d[s] ← 0;

Q ← V[G];

while (Q ≠ 0)

{

u ← Extract-Min(Q);

for (каждая вершина v из Adj[u])

if (d[v] > d[u] + w(u, v))

{

d[v] ← d[u] + w(u, v);

Pr[v] ← u;

}

}
for (i = 1..N - 1)

{

if (d[i] > 100)

{

Ответ: НЕТ

}

}

Ответ: ДА

}

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

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

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

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

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

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

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

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

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

Функция satisfy:

Назначение: поиск путей в графе Алгоритмом Дейкстры, проверка, что до каждой вершины из заданной существует маршрут до любой другой, и при этом его длина не преывшает 100

Прототип: bool satisfy(Graph &roads, int from)

Параметры: roads – матрица смежности (матрица весов) графа, from – начальная вершина.

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



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

main.cpp

#include
#include

#include
#include

#include

#include
#include "graph.h"
using namespace std;
int main()

{

cout << "Enter filename: ";

char filename[16]; cin >> filename;

fstream ifile(filename);

if (!ifile.is_open())

{

cerr << "Error opening file" << endl;

exit(EXIT_FAILURE);

}
// Чтение городов

map cities_ids;

int cities_c; ifile >> cities_c;

vector
> cities(cities_c);

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

{

string name; float x, y;

ifile >> name >> x >> y;

if (cities_ids.find(name) != cities_ids.end())

{

cerr << "City " << name << " declared twice" << endl;

exit(EXIT_FAILURE);

}

cities_ids[name] = i;

cities[i] = pair(x, y);

}
// Пункт отправления

int from; string from_str; ifile >> from_str;

if (cities_ids.find(from_str) != cities_ids.end())

{

from = cities_ids[from_str];

} else {

cerr << "City " << from_str << " does not exist" << endl;

exit(EXIT_FAILURE);

}
// Расстояние между городами

Graph roads(cities_c);

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

{

roads[i].resize(cities_c);

}

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

{

roads[i][i] = new Road;

roads[i][i]->built = true;

roads[i][i]->weight = 0.0;

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

{

roads[i][j] = new Road;

roads[i][j]->weight = sqrt(pow(cities[i].first - cities[j].first, 2)

+ pow(cities[i].second - cities[j].second, 2));

roads[i][j]->built = false;

roads[j][i] = roads[i][j];

if ((i == from || j == from) && roads[i][j]->weight >= 100.0)

{

cout << "NO" << endl;

exit(EXIT_SUCCESS);

}

}

}
// Чтение системы дорог

int roads_c; ifile >> roads_c;

int real_roads_c = roads_c;

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

{

string name1, name2;

ifile >> name1 >> name2;

if (cities_ids.find(name1) == cities_ids.end())

{

cerr << "City " << name1 << " does not exist" << endl;

exit(EXIT_FAILURE);

}

if (cities_ids.find(name2) == cities_ids.end())

{

cerr << "City " << name2 << " does not exist" << endl;

exit(EXIT_FAILURE);

}

if (!roads[cities_ids[name1]][cities_ids[name2]]->built)

{

roads[cities_ids[name1]][cities_ids[name2]]->built = true;

} else {

real_roads_c--;

}

}

roads_c = real_roads_c;
// Города, недостижимые из данного

if (satisfy(roads, from))

{

cout << "YES" << endl;

exit(EXIT_SUCCESS);

}
// Непостроенные дороги

int t = 0;

vector
> unbuilt_roads((cities_c * (cities_c - 1)) / 2 - roads_c);

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

{

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

{

if (!roads[i][j]->built)

{

unbuilt_roads[t++] = pair(i ,j);

}

}

}
if (unbuilt_roads.size() > 3)

{

// Перебор неупорядоченных троек непостроенных дорог

for (int i = 0; i < unbuilt_roads.size(); i++)

{

roads[unbuilt_roads[i].first][unbuilt_roads[i].second]->built = true;

for (int j = i + 1; j < unbuilt_roads.size(); j++)

{

roads[unbuilt_roads[j].first][unbuilt_roads[j].second]->built = true;

for (int k = j + 1; k < unbuilt_roads.size(); k++)

{

roads[unbuilt_roads[k].first][unbuilt_roads[k].second]->built = true;
if (satisfy(roads, from))

{

cout << "YES" << endl;

exit(EXIT_SUCCESS);

}
roads[unbuilt_roads[k].first][unbuilt_roads[k].second]->built = false;

}

roads[unbuilt_roads[j].first][unbuilt_roads[j].second]->built = false;

}

roads[unbuilt_roads[i].first][unbuilt_roads[i].second]->built = false;

}

} else {

// Просто добавить все дороги

for (int i = 0; i < unbuilt_roads.size(); i++)

{

roads[unbuilt_roads[i].first][unbuilt_roads[i].second]->built = true;

}
if (satisfy(roads, from))

{

cout << "YES" << endl;

exit(EXIT_SUCCESS);

}

}
cout << "NO" << endl;

exit(EXIT_SUCCESS);

}

graph.h

#include

#include

#include

using namespace std;
struct Road

{

bool built;

float weight;

};
typedef vector > Graph;

bool satisfy(Graph &roads, int from);

graph.cpp

#include "graph.h"
bool satisfy(Graph &roads, int from)

{

vector Q(roads.size());

vector d(roads.size());

for (int i = 0; i < roads.size(); i++)

{

d[i] = numeric_limits::infinity();

Q[i] = i;

}

d[from] = 0;

while (!Q.empty())

{

int min_i = 0;

for (int i = 0; i < Q.size(); i++)

{

if (d[Q[i]] < d[Q[min_i]])

{

min_i = i;

}

}

int u = Q[min_i];

Q.erase(Q.begin() + min_i);
for (int i = 0; i < roads[u].size(); i++)

{

if (roads[u][i]->built && d[i] > d[u] + roads[u][i]->weight)

{

d[i] = d[u] + roads[u][i]->weight;

}

}

}
for (int i = 0; i < d.size(); i++)

{

if (d[i] > 100.0)

{

return false;

}

}
return true;

}


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

Тест 1: Требуется много дорог

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

A 30 30

B 30 70

C 50 60

D 60 40

E 80 70

F 100 40

A

1

C D

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




Тест 2: Можно построить

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

A 30 30

B 30 70

C 50 60

D 60 40

E 80 70

F 100 40

A

2

C D

D F

Выходные данные: YES
Тест 3: Несколько компонент связности

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

A 30 30

B 30 60

C 60 60

D 60 30

E 70 30

F 70 60

G 100 60

H 100 30

I 60 70

J 60 80

K 70 80

L 70 70

A

12

A B

B C

C D

D A

E F

F G

G H

H E

I J

J K

K L

L I

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


Тест 4: Результат зависит и от исходного города

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

A 0 0

B 110 0

C 55 30

C

0

Выходные данные: YES
Тест 4а:

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

A 0 0

B 110 0

C 55 30

A

0

Выходные данные: NO
Тест 5: Дважды определённый город

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

A 0 0

B 110 0

A 20 20

A

0

Выходные данные: City A declared twice
Тест 6: Неопределённый город

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

A 0 0

B 20 0

C 20 20

A

2

A B

A E

Выходные данные: City E does not exist
Тест 7: Дважды указана дорога

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

A 30 30

B 30 70

C 50 60

D 60 40

E 80 70

F 100 40

A

3

C D

D F

C D

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

Тест 8: Отрицательные координаты

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

A 30 30

B 30 70

C 50 60

D 60 40

F -10 40

D

1

C D

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




Тест 9: Два города в системе

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

A 0 0

B 1 1

B

0

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



Похожие:

Курсовая работа по практикуму на эвм: структуры данных и алгоритмы Факультет: прикладной математики и информатики Группа iconКурсовая работа по практикуму на эвм: структуры данных и алгоритмы Факультет: прикладной математики и информатики Группа
Добавить каждое неупорядоченное четырёхэлементное подмножество множества V исходного графа в список полных четырёхэлементных подграфов...
Курсовая работа по практикуму на эвм: структуры данных и алгоритмы Факультет: прикладной математики и информатики Группа iconКурсовая работа по практикуму на эвм: структуры данных и алгоритмы Факультет: прикладной математики и информатики Группа
Проверить, является ли заданный граф транзитивным, т е для любых трёх вершин u, v и w выполняется условие: если u и w, а также v...
Курсовая работа по практикуму на эвм: структуры данных и алгоритмы Факультет: прикладной математики и информатики Группа 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