Отчет к курсовой работе

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

Федеральное государственное бюджетное образовательное учреждение

Высшего профессионального образования

Уфимский государственный авиационный технический университет

Кафедра ВМиК

Пояснительная записка к курсовой работе

по дисциплине

"Структуры и алгоритмы компьютерной обработки данных"

Выполнила: студ. гр. МО-204

Валиева Э.А.

Проверила:

Верхотурова Г.Н.

Уфа-2014

Постановка задачи:

Задана система односторонних дорог. Найти путь, соединяющий города А и В и не проходящий через заданное множество городов.

Алгоритм нахождения пути:

Данную задачу мы можем решить с помощью алгоритма обхода в глубину.

Удаляем вершины, через которые нельзя проходить.

Запускаем обход, который будет начинаться с начального города А.

Если в результате обхода мы достигли вершины В, то существует путь, иначе пути нет.

1. Вводим с формы строчкой множество запрещенных городов. Строку мы конвертируем в массив. Удаляем запрещенные города из матрицы смежности.

2. Вводим вершину А, которая является начальной вершиной пути и вершину В, которая является конечной вершиной пути.

3. Посещаем вершину А и проверяем была ли она обработана в результирующем списке.

1. Если нет, то нужно провести обработку этой вершины, включив ее в результирующий список, проверяя равна ли она вершине В. Вершину А, делаем в массиве visited пройденной.

1. Получаем первую смежную вершину с А.

2. Рекурсивно запускаем от первой смежной вершины с А функцию обхода в глубину.

3.2. Если да, завершаем процесс

4. Делаем проверку: если вершина В была не посещена, т.е. в массиве visited не пройдена, то «Пути нет». Иначе, выводим путь.

Входные и выходные данные:

dataGridView1-Матрица смежности

Поле textBox1 , в котором задаем множество запрещенных городов

Поле textBox2, в котором задаем начальный город А.

Поле textBox3, в котором задаем конечный город В.

bool[] visited1-Результирующий список

Поле textBox4, в котором мы выводим результат

Реализация:

private void button2_Click(object sender, EventArgs e)

{

int N = dataGridView1.RowCount - 1;

string[] arrstring = textBox1.Text.Split(' ');

int[] mas = new int[arrstring.Length];

for (int i = 0; i < arrstring.Length; i++)

O(N)

{

mas[i] = Convert.ToInt32(arrstring[i]);

}

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

{

for (int j = 0; j < arrstring.Length; j++)

O(N²)

{

dataGridView1.Rows[mas[j] - 1].Cells[i].Value = "";

dataGridView1.Rows[i].Cells[mas[j] - 1].Value = "";

}

}

int finish = Convert.ToInt32(textBox3.Text);

int start = Convert.ToInt32(textBox2.Text);

int p = arrstring.Length;

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

O(N)

{

visited1[i] = false;//Создаем матрицу-флагов

}

DFS1(start-1, finish-1);//Рекурсия

}

void DFS1(int st, int fn)

{

textBox4.Text = textBox4.Text + (st + 1) + " ";

visited1[st] = true;//Помечаем вершину

for (int r = st + 1; r <= fn; r++) //Перебираем вершины

O(N)

{

if (dataGridView1.Rows[st].Cells[r].Value!="" && dataGridView1.Rows[st].Cells[r].Value!=null && !visited1[r]) //Если вершина не помечена и смежна с текущей

DFS1(r, fn);//рекурсивно запускаем от нее DFS

}

O(1)

if (visited1[fn] == false)

{

textBox4.Text = "Нет пути";

}

}

Оценка сложности: O(N²)

Список литературы:

1. Вирт Н. Алгоритмы и структуры данных.1989.

2. Б.С. Хусаинов. Структуры и алгоритмы обработки данных. Москва, «Финансы и статистика», 2004.

3. Р. Седжвик Алгоритмы на C++.2011.