close

Вход

Забыли?

вход по аккаунту

?

Laba 8 otchet

код для вставкиСкачать
 МІНІСТЕРСТВО ОСВІТИ І НАУКИ УКРАЇНИ
НАЦІОНАЛЬНИЙ ТЕХНІЧНИЙ УНІВЕРСИТЕТ
"Харківський політехнічний інститут"
Кафедра "Автоматизовані системи управління"
ЗВІТ
з лабораторної роботи № 8
з курсу "Алгоритми та структури даних "
ВИКОНАВ
Студент групи ІФ32в
Глазков С. О.
ПЕРЕВІРИВ
Асс. Гонтарь Ю.М.
Харків 2013 Лабораторна робота №8
Тема: Математичні основи теорії алгоритмів.
Мета: Навчитися визначати складність алгоритмів.
Завдання: Для кожного реалізованого алгоритму з попередніх робіт визначити складність. Для цього для кожного рядку алгоритму потрібно вказати кількість разів, які він виконується, в залежності від розмірності вхідних даних. Результат записати у вигляді Θ -позначення.
Лабораторна робота №1
Варіант: однобічно зв'язний список.
Програма читає з клавіатури послідовність N цілих чисел, де N<256.
Метод додавання:
Node nd = new Node();
nd.set_data(dt);
nd.set_next(null);
if (head == null)
{
head = nd;
}
else
{
Node current = head;
while (current.get_next() != null)
current = current.get_next();
current.set_next(nd);
}
Цикл while буде виконуватись доти, доки не буде введено число менше 1 або більше 255. Алгоритм буде працювати за час О(n). T(n) = Θ (n).
Лабораторна робота №2
Варіант: хеш-таблиця, мультиплікативне хешування.
Функція додавання:
Pair dt = new Pair(key, data);
array[HashFunc(key)].AddNode(dt); // виклик методу додавання до списку
Моя хеш-таблиця є масивом однобічно зв'язних списків, таким чином вирішується проблема колізій. Так як складність роботи алгоритму додавання до списку дорівняє O(n). T(n) = Θ (n). То і у хеш-таблиці також складність T(n) = Θ (n).
Лабораторна робота №3
Червоно-чорне дерево.
Функція додавання: public void Insert(Node z)
{
y = NIL;
x = root;
while(x!=NIL)
{
y=x;
if (z.key < x.key)
x = x.left;
else
x = x.right;
}
z.p = y;
if (y == NIL)
root = z;
else
{
if (z.key < y.key)
y.left = z;
else
y.right = z;
}
z.left = NIL;
z.right = NIL;
z.color = Color.RED;
Fixup(z);
}
private void Fixup(Node z)
{
y = null;
while(z!=root && z.p.color==Color.RED)
{
if (z.p == z.p.p.left)
{
y = z.p.p.right;
if (y.color == Color.RED)
{
z.p.color = Color.BLACK;
y.color = Color.BLACK;
z.p.p.color = Color.RED;
z = z.p.p;
}
else
{
if (z == z.p.right)
{
z = z.p;
L_rotate(z);
}
z.p.color = Color.BLACK;
z.p.p.color = Color.RED;
R_rotate(z.p.p);
}
}
else
{
y = z.p.p.left;
if (y.color == Color.RED)
{
z.p.color = Color.BLACK;
y.color = Color.BLACK;
z.p.p.color = Color.RED;
z = z.p.p;
}
else
{
if (z == z.p.left)
{
z = z.p;
R_rotate(z);
}
z.p.color = Color.BLACK;
z.p.p.color = Color.RED;
L_rotate(z.p.p);
}
}
}
root.color = Color.BLACK;
}
Спочатку виконується процедура Insert, а потім Fixup. Висота червоно-чорного дерева О(lg n), якщо в дереві n вершин, тому виклик Insert потребує часу О(lg n). Цикл повторюється О(lg n) разів, тому час роботу алгоритму О(lg n). T(n) = Θ (log n ).
Лабораторна робота №4
Варіант: швидке сортування .
public void QuickSort(int beg, int end)
{
int q;
if (beg < end)
{
q = Partition(beg, end);
QuickSort(beg, q - 1);
QuickSort(q + 1, end);
}
}
private int Partition(int beg, int end)
{
double tmp;
int marker = beg;
for (int j = beg; j <= end; j++)
{
if (array[j] <= array[end])
{
tmp = array[marker];
array[marker] = array[j];
array[j] = tmp;
marker += 1;
}
}
return marker - 1;
}
Час роботи алгоритму сортування залежить від того, на які частини розбивається масив. Якщо частини рівні, О(n log n), у гіршому випадку: О(n^2), Тому що в алгоритмі присутній цикл while і з кожним рекурсивним викликом QuickSort він виконує менше операцій, тому T(n) = Θ (n lg n).
Лабораторна робота №5
Варіант: лінійний конгруентний метод.
Згідно з завданням треба було розробити програму, яка читає з клавіатури число N (1 < N < 256) та параметри генератору випадкових чисел та виводить на екран послідовність з N згенерованих чисел.
for (int i = 0; i < Convert.ToInt32(NTB.Text); i++)
{
array[i] = gen.getRand();
resultBox.Text += array[i].ToString();
resultBox.Text += " ";
}
public int getRand()
{
Seed = (A * Seed + C) % M;
return Seed;
}
Складність роботи генератору залежить від того скільки елементів потрібно генерувати, алгоритм генерації чисел виконується n разів, тому час роботу складає О(n). T(n) = Θ (n).
Лабораторна робота №6
Варіант: топологічне сортування та пошук у глибину.
Треба розробити програму, яка читає з клавіатури числа N, M (1 < N, M < 256) - кількість вершин та ребер графу; послідовність M пар цілих чисел - ребра графу. Алгоритм працює таким чином, що спочатку виконується пошук у глибину, як тільки вершину було проаналізовано, вона заноситься до списку.
private void DFS_VISIT(Node u)
{
u.Col = Color.GRAY;
time++;
u.OpenTime = time;
foreach (Node v in u.Neighbors)
if (v.Col == Color.WHITE)
{
v.P = u;
DFS_VISIT(v);
}
u.Col = Color.BLACK;
u.CloseTime = time = time + 1;
sortingList.AddLast(u);
}
public void DFS()
{
foreach (Node u in Nodes)
{
u.Col = Color.WHITE;
u.P = null;
}
time = 0;
foreach (Node u in Nodes)
if (u.Col == Color.WHITE)
DFS_VISIT(u);
}
Складність топологічного сортування дорівнює O(n2), тому що в функції DFS є цикл який виконується n разів і викликається функцію DFS_VISIT, яка в свою чергу також містить цикл який виконує операцій. T(n) = Θ (n2)
Лабораторна робота №7
Варіант: точки є координатами багатокутника в порядку обходу. Потрібно було вивести площину багатокутника та повідомити, по чи проти годинникової стрілки здійснено обхід.
Треба було розробити програму, яка читає з клавіатури число N (1 < N < 256) та N пар дійсних чисел - координати точок на площині. public double Ploshad()
{
double s=0, res=0;
for (int i = 0; i < Points.Length; i++)
{
if (i == 0)
{
s = Points[i].X * (Points[Points.Length - 1].Y - Points[i + 1].Y);
res += s;
}
else
if (i == Points.Length - 1)
{
s = Points[i].X * (Points[i - 1].Y - Points[0].Y); res += s;
}
else
{
s = Points[i].X * (Points[i - 1].Y - Points[i + 1].Y);
res += s;
}
}
return Math.Abs(res / 2);
}
public bool Clock()
{
double x = Points[0].X;
int ind = 0; ;
for (int i = 0; i < Points.Length; i++)
{
if (Points[i].X < x)
{
x = Points[i].X;
ind = i;
}
}
if (ind == 0)
{
if (((Points[Points.Length - 1].X - Points[ind].X) * (Points[ind + 1].Y - Points[ind].Y)) - ((Points[Points.Length - 1].Y - Points[ind].Y) * (Points[ind + 1].X - Points[ind].X)) > 0)
return true;
else
return false;
}
if (ind == Points.Length - 1)
{
if (((Points[ind - 1].X - Points[ind].X) * (Points[0].Y - Points[ind].Y)) - ((Points[ind - 1].Y - Points[ind].Y) * (Points[0].X - Points[ind].X)) > 0)
return true;
else
return false;
}
if (((Points[ind - 1].X - Points[ind].X) * (Points[ind + 1].Y - Points[ind].Y)) - ((Points[ind - 1].Y - Points[ind].Y) * (Points[ind + 1].X - Points[ind].X)) > 0)
return true;
else return false;
}
Функція Ploshad виконується за час О(n). Один цикл, який виконується т разів. Отже T(n) = Θ (n).
Функція Clock також виконується за час O(n), так як містить один цикл, який виконується n разів. Отже складність алгоритму складає T(n) = Θ (n).
Висновок: на цій лабораторній роботі, я навчився визначати складність роботи.
Аналізуючи складність алгоритмів, які використовуються у однобічно зв'язних списках, я роблю висновок, що ця структура даних не є оптимальною, так як складність роботи О(n). Більш оптимальна структура - це масив, так як він працює за О(n).
Аналізуючи складність алгоритму, який використовуються у графу, я роблю висновок, що мій алгоритм (пошук у глибину) не є оптимальнім, так як його складність О (n2). Більш оптимальний алгоритм - це алгоритм Крускала, так як він працює за О(n lg n).
Документ
Категория
Рефераты
Просмотров
124
Размер файла
31 Кб
Теги
laba, otchet
1/--страниц
Пожаловаться на содержимое документа