- •Зміст дисципліни.
- •Найменування тем, їхній зміст, обсяг у годинах лекційних занять
- •Вказівки з використанНя літературних джерел
- •Алгоритми й структури даних
- •Стеки, списки
- •Дерева пошуку Бінарні дерева
- •Двійкові дерева
- •Червоно- чорні дерева
- •Частково впорядковані дерева Статья I.При створенні чуд елементи вводилися в наступному порядку: (13, 6, 15, 5, 10, 6, 3, 13, 5, 6, 35, 8). Пояснити побудова (переформування) дерева.
- •Рекурсія
- •Перебір з поверненням
- •Машина Тьюрінга
- •Приклади Послідовний пошук
- •Структури даних. Масиви Решето Ератосфена
- •Обчислення найближчої точки
- •Структури даних. Списки Приклад циклічного списку (задача Йосипа)
- •Сортування методом вставки в список
- •Звертання порядку проходження елементів списку
- •Структури даних. Рядки Сортування масиву рядків
- •Абстрактні типи даних (атд) Інтерфейс абстрактного типу даних стека
- •Реалізація черги fifo на базі масиву
- •Реалізація черги fifo на базі зв'язного списку
- •Перетворення з інфіксної форми в постфіксну
- •Рекурсія Алгоритм Евклида
- •Рекурсивна програма для оцінки префіксних виразів
- •Розв’язання
- •Приклад 2 Завдання
- •Розв’язання
- •Приклад 3 Завдання
- •Розв’язання
- •Приклад 4 Завдання
- •Розв’язання
- •Приклад 5 Завдання
- •Розв’язання
- •Приклад 6 Завдання
- •Розв’язання
- •Приклад 7 Завдання
- •Розв’язання
- •Алгоритм роботи машини т’юринга
- •Дослідження функції на рекурсивність
- •Нормальні алгоритми Маркова
- •Алгоритм роботи програми.
- •Приклад роботи програми.
- •Варіанти курсових робіт
- •Варіанти виконання Алгоритм виконання курсової роботи:
- •Приклад1.
- •Побудова моделі.
- •Розроблення алгоритму.
- •Правильність алгоритму.
- •Реалізація алгоритму.
- •Перевірка програми.
- •Приклад2
- •Постановка задачі
- •Перший варіант розв’язку
- •Другий варіант розв’язку.
- •Приклад3
- •Опукла оболонка
- •Метод обходу Грехема
- •Метод обходу Джарвіса
- •Алгоритм апроксимації опуклої оболонки
- •Швидкі методи побудови опуклої оболонки
- •Алгоритм типу розділяй та пануй
- •Побудова опуклої оболонки простого многокутника
- •Динамічні алгоритми побудови опуклої оболонки
- •Порівняльний аналіз алгоритмів побудови опуклої оболонки
- •Висновки
Приклади Послідовний пошук
Задана функція перевіряє, чи знаходиться число v серед елементів масиву а[l], а[l+1], ..., а[r] шляхом послідовного порівняння з кожним елементом, починаючи з початку. Якщо по досягненні останнього елемента потрібне значення не знайдене, то функція повертає значення -1. Інакше вона повертає індекс елемента масиву, що містить шукане число.
int search (int a[], int v, int 1, int r)
{
for (int i = 1; i <= r; i++)
if (v == a[i]) return i;
return -1;
}
Лема. Послідовний пошук досліджує N чисел при кожному неуспішному пошуку й в середньому порядку N/2 чисел при кожному успішному пошуку.
Дійсно, якщо кожне число в таблиці з рівною імовірністю може бути об'єктом пошуку, тоді (1 +2 + ... + N)/ N = (N+1)/2 є середньою ціною пошуку.
Структури даних. Масиви Решето Ератосфена
Ціль програми полягає в присвоєнні елементам a[i] значення 1, якщо i просте число, і значення 0 у протилежному випадку. Спочатку значення 1 привласнюється всім елементам масиву. Потім привласнюється значення 0 елементам, індекси яких не є простими числами (являють собою добуток відомих простих чисел). Якщо після цього деякий елемент a[i] зберігає значення 1, його індекс є простим числом.
Оскільки масив складається з елементів найпростішого типу, що приймають значення 0 або 1, для економії простору має сенс явно описати масив біт замість масиву цілих чисел. Крім того, у деяких середовищах програмування потрібно, щоб масив був глобальним, якщо значення N велике, або можна виділяти простір для масиву динамічно.
#include <iostream.h>
static const int N = 1000;
int main()
{int i, a [N];
for (i = 2; i < N; i++) a[i] = 1;
for (i = 2; i < N; i++)
if (a[i])
for (int j = i; j*i < N; j++) a[i*j] = 0;
for (i = 2; i < N; i++)
if (a[i])
cout << " " << i; cout << endl;
Обчислення найближчої точки
Ця програма демонструє використання масиву структур і представляє типовий випадок, коли елементи зберігаються в масиві для наступної обробки в процесі деяких обчислень. Підраховується кількість пар з N згенерованих випадковим образом точок на площині, що з'єднуються прямою, довжина якої менше за d. Час виконання складає O(N2), тому програма не може застосовуватися для великих значень N.
#include <iostream.h>
#include <stdlib.h>
#include "Point.h"
float randFloat()
{ return 1.0*rand()/RAND_MAX; }
int main(int argc, char *argv[])
{ float d = atof(argv[2]);
int i, cnt = 0, N = atoi (argv[l]);
point *a = new point [N];
for (i = 0; i < N; i++)
{
a[i].x = randFloat(); a[i].y = randFloat();
}
for (i = 0; i < N; i++)
for (int j = i+1; j < N; j++)
if (distance (a[i], a[j]) < d) cnt++;
cout << cnt << " pairs within " << d << endl;
}
Структури даних. Списки Приклад циклічного списку (задача Йосипа)
Для представлення людей, розставлених у коло, побудуємо циклічний зв'язний список, де кожен елемент (людина) містить посилання на сусідній елемент проти ходу годинникової стрілки. Ціле число i представляє i-ту людину в колі. Після створення циклічного списку з одного вузла уставляються вузли від 2 до N. У результаті утвориться окружність з вузлами від 1 до N. При цьому змінна х указує на N. Потім пропускаємо М-1 вузлів, починаючи з 1-го, і встановлюємо значення посилання (М-1)-го вузла таким чином, щоб пропустити М-ий вузол. Продовжуємо цю операцію, поки не залишиться один вузол.
#include <iostream.h>
#include <stdlib.h>
struct node
{ int item; node* next;
node(int x, node* t)
{ item = x; next = t;}
typedef node *link;
int main(int argc, char *argv[])
{ int i, N = atoi(argv[l]) , M = atoi(argv[2]);
link t = new node(1, 0); t->next = t;
link x = t;
for (i = 2; i <= N; i++)
x = (x->next = new node(i, t)) ;
while (x != x->next)
{
for (i = 1; i < M; x->next) x = x->next;
x->next = x->next->next;
}
cout << x->item << endl;
