Дослідження алгоритмів з використанням різних структур даних: черг та графів

Поняття черги в програмуванні, основні операції з чергою і їх реалізація. Опис алгоритму й специфікація програми. Розробка додатку з використанням задачі Ларсона по опису зв'язного неорієнтованого графа. Алгоритм розв’язку і результати виконання програми.
Краткое сожержание материала:

Размещено на

Зміст

черга граф програмування

Вступ

1. Завдання 1

1.1 Теоретична частина

1.2 Алгоритм розв'язку

1.3 Система тестів

1.4 Специфікація програми

1.5 Результати виконання програми

2. Завдання 2

2.1 Теоретична частина

2.2 Алгоритм розв'язку

2.3 Система тестів

2.4 Специфікація програми

2.5 Результати виконання програми

Висновки

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

Додаток

Вступ

Структура даних - програмна одиниця, що дозволяє зберігати і обробляти безліч однотипних і / або логічно пов'язаних даних в обчислювальній техніці. Для додавання, пошуку, зміни та видалення даних структура даних надає деякий набір функцій, складових її інтерфейс. Структура даних часто є реалізацією будь-якого абстрактного типу даних.

При розробці програмного забезпечення велику роль грає проектування сховища даних і представлення всіх даних у вигляді безлічі пов'язаних структур даних.

Добре спроектоване сховище даних оптимізує використання ресурсів (таких як час виконання операцій, на обсяг оперативної пам'яті, число звернень до дискових накопичувачів), необхідних для виконання найбільш критичних операцій.

Структури даних формуються за допомогою типів даних, посилань і операцій над ними в обраному мовою програмування.

Різні види структур даних підходять для різних додатків; деякі з них мають вузьку спеціалізацію для певних завдань. Наприклад, B-дерева зазвичай підходять для створення баз даних, в той час як хеш-таблиці використовуються повсюдно для створення різного роду словників, наприклад, для відображення доменних імен в інтернет-адреси комп'ютерів.

При розробці програмного забезпечення складність реалізації і якість роботи програм істотно залежить від правильного вибору структур даних. Це розуміння дало початок формальним методам розробки та мов програмування, в яких саме структури даних, а не алгоритми, є наріжним архітектури програмного засобу. Велика частина таких мов володіє певним типом модульності, що дозволяє структурам даних безпечно використовуватися в різних додатках. Об'єктно-орієнтовані мови, такі як Java, C # і C + +, є прикладами такого підходу.

Багато класичних структур даних представлені в стандартних бібліотеках мов програмування або безпосередньо вбудовані в мови програмування. Наприклад, структура даних хеш-таблиця вбудована в мови програмування Lua, Perl, Python, Ruby, Tcl і ін. Широко використовується стандартна бібліотека шаблонів STL мови C + +.

1. Завдання 1

1.1 Теоретична частина

Черга в програмуванні -- динамічна структура даних, що працює за принципом "перший прийшов - перший пішов" (англ. FIFO -- first in, first out). У черги є голова (англ. head) та хвіст (англ. tail). Елемент, що додається до черги, опиняється в її хвості. Елемент, що видаляється з черги, знаходиться в її голові.

Така черга повністю аналогічна звичній "базарній" черзі, в якій хто перший встав в неї, той першим буде обслуженим (але, на відміну від реальної черги, імовірність пройти поза чергою виключена)

Основні операції з чергою

англ. enqueue -- "поставити в чергу". Операція додавання елемента в "хвіст" черги. При цьому довжина черги збільшується на одиницю. Якщо відбувається намагання додати елемент у вже заповнену чергу, відбувається її переповнення (англ. queue overflow).

англ. dequeue -- "отримання з черги". Операція, яка повертає елемент з голови та видаляє його з черги, таким чином встановлюючи голову на наступний за видаленим елемент та зменшуючи довжину на одиницю. При намаганні видалити елемент з пустої черги, виникає ситуація "незаповнення" (англ. queue underflow).

Реалізація на мовах програмування

Черга може бути реалізована за допомогою масива Q[1...n], в якому зберігаються дані та двох додаткових змінних head[Q] та tail[Q], в яких зберігаються індекси відповідно "голови" та "хвоста" черги, lenght[Q] -- довжина черги.

1.2 Алгоритм розв'язку

Рис.1.2.1. Блок-схема алгоритму роботи програми 1

1.3 Система тестів

У випадку коли T < t1 або T < t2 або будь-яка змінна з вхідних даних = 0 вхідні дані задані невірно. У інших випадках йде обрахунок і виводиться на екран результат у вигляді списку, в якому вказаний час та подія яка в цей час відбулася.

Результати виконання показано в відповідному розділі.

У випадку введення невірних даних програма видає відповідне повідомлення про помилку.

1.4 Специфікація програми

В клас стандартного діалогового вікна було додано такі елементи:

Edit1- поле для вводу кількості покупців m

Edit2- поле для вводу t1

Edit3- поле для вводу t2

Edit4- поле для вводу t3

Edit5- поле для вводу t4

Edit6- поле для вводу t5

Edit7- поле для вводу періоду часу на якому проводиться дослідження T

StaticText1- текстове поле, в якому виводиться стан черги після виконання програми

Button1 - кнопка за допомогою якої відкривається вікно з детальною умовою поставленої задачі

Button2 - кнопка за допомогою якої формується черга та виводиться результат роботи програми на екран

StaticText - текстові поля які виводять допоміжні повідомлення

В клас стандартного діалогового вікна було додано такі функції:

afx_msg void OnBnClickedButton1() - функція для керування кнопкою 1

afx_msg void OnBnClickedButton2() - функція для керування кнопкою 2

void dodavsja() - функція, що додає до черги покупця

void obslygily() - функція, що вилучає з черги покупця

void pilgoviy() - функція, що додає до черги пільгового покупця

void zvaluv() - функція, що вилучає з черги покупця, який не витримав очікування в черзі

В клас стандартного діалогового вікна було додано такі змінні:

int now_get1 - Змінна для запам'ятовування покупця, який зараз додається до черги

int now_get2 - Змінна для запам'ятовування покупця, який зараз вилучається з черги

int now_time - Змінна, в якій задається текучий час

int real1 - Змінна, в яку записується випадкове значення, з діапазону 1..t1

int real2 - Змінна, в яку записується випадкове значення, з діапазону 1..t2

int real3 - Змінна, в яку записується випадкове значення, з діапазону 1..t3

int real4 - Змінна, в яку записується випадкове значення, з діапазону 1..t4

CString zalushok - рядок для виводу залишку черги

CString str1 - рядок для виводу процесу додавання та обслуговування покупців.

1.5 Результати виконання програми

Рис 1.5.1. Результат виконання програми з вхідними даними 1

Рис 1.5.2. Результат виконання програми з вхідними даними 2

2. Завдання 2

2.1 Теоретична частина

Граф -- це сукупність об'єктів із зв'язками між ними.

Об'єкти розглядаються як вершини, або вузли графу, а зв'язки -- як дуги, або ребра. Для різних областей використання види графів можуть відрізнятися орієнтовністю, обмеженнями на кількість зв'язків і додатковими даними про вершини або ребра.

Велика кількість структур, які мають практичну цінність в математиці та інформатиці, можуть бути представлені графами. Наприклад, будову Вікіпедії можна змоделювати за допомогою орієнтованого графу, в якому вершини -- це статті, а дуги (орієнтовані ребра) -- посилання на інші статті.

Першою працею з теорії графів як математичної дисципліни вважають статтю Леонарда Ейлера (1736), у якій розглядалася задача проКенігсбергські мости. Наступний імпульс теорія графів отримала близько 100 років потому з розвитком досліджень по електричним мережам, кристалографії, органічній хімії та іншим наукам.

Теорія графів не має стійкої термінології. В різних статтях під одними й тими ж термінами розуміють різні поняття. Наведені нижче визначення є одними з найбільш розповсюджених.

Граф або неорієнтований граф G -- це впорядкована пара G: = (V,E), для якої виконуються наступні умови:

V -- множина вершин або вузлів,

E -- множина пар (у випадку неорієнтованого графу -- невпорядкованих) вершин, які називають ребрами.

V (і так само E) зазвичай вважаються скінченними множинами. Велика кількість результатів, отриманих для скінченних графів, невірна (або інша) для нескінченних графів. Це пов'язано з тим, що певний набір ідей стає хибним у випадку...