Подякувати Студентському архіву довільною сумою
Admin
26.02.2023 12:38
Дякуємо, що користуєтесь нашим архівом!
Інформація про навчальний заклад
ВУЗ:
Національний університет Львівська політехніка
Інститут:
Інтелектуальні системи прийняття рішень
Факультет:
Комп’ютерні науки
Кафедра:
Не вказано
Інформація про роботу
Рік:
2007
Тип роботи:
Лабораторний практикум
Предмет:
Алгоритми і структури даних
Частина тексту файла (без зображень, графіків і формул):
http://www.magnolia.lviv.ua/?p=950
Міністерство освіти і науки України
Національний університет “Львівська політехніка”
АЛГОРИТМИ І СТРУКТУРИ ДАНИХ
ЛАБОРАТОРНИЙ ПРАКТИКУМ
для студентів базового напрямку “Комп’ютерні науки”
спеціальність – “Інтелектуальні системи прийняття рішень”
Укладачі: Шаховська Наталя Богданівна,
Голощук Роман Олегович
Затверджено на засіданні кафедри “Інформаційні системи та мережі”
Протокол № __ від _____________ року.
Львів – 2007
Шаховська Н.Б., Голощук Р.О. Алгоритми і структури даних: Лабораторний практикум з курсу “Алгоритми і структури даних” для студентів базового напряму “Комп’ютерні науки” / Укл.: Н.Б. Шаховська., Р.О.Голощук – Львів: Видавництво Національного університету “Львівська політехніка”, 2007. – 23 с.
Укладачі: к.т.н., доц. Шаховська Н.Б.
ст.викл. Голощук Р.О.
МЕТА ВИКОНАННЯ ЛАБОРАТОРНИХ РОБІТ
Метою виконання лабораторних робіт є отримання студентами практичних навичок з принципів створення сучасних інформаційних технологій, основ алгоритмізації, процедурного і візуального програмування.
В результатi виконання лабораторних робіт студенти повиннi:
( знати поняття алгоритму, способи подання алгоритму, основні алгоритмічні конструкції, принципу проектування алгоритму "зверху-вниз" та покрокового уточнення алгоритму, типи даних, операції, визначені над даними різних типів.;
( вмiти застосовувати різні форми опису алгоритмів, описувати розв’язки типових навчальних задач мовами програмування, реалізовувати програми на комп’ютері, аналізувати вхідні дані і отримані результати, використовувати навчальні програми для вивчення інформатики та інших предметів.
ПОРЯДОК ВИКОНАННЯ ЛАБОРАТОРНИХ РОБІТ
Для виконання лабораторних робіт необхідно:
Використовуючи літературні джерела, конспект лекцій, методичні розробки з дисципліни, засвоїти теоретичний матеріал, пов’язаний з тематикою лабораторної роботи;
Відповісти керівнику лабораторних занять на поставлені запитання за темою лабораторної роботи;
Отримати індивідуальне завдання, розробити схему алгоритму для його розв’язування та написати відповідну програму на мові Паскаль чи Сі;
Використовуючи засоби iнтегрованого середовища мови Паскаль, Сі або С++ , набрати, відредагувати та відкомпілювати текст програми;
Підготувати вхідні дані для перевірки правильності виконання програми;
Виконати програму та зафіксувати отримані результати;
Перевірити правильність роботи програми; при необхідності внести зміни у програму та виконати її повторний запуск.
Оформити та захистити звіт про виконання лабораторної роботи.
Примітка. Для зменшення часу введення великих об’ємів вхідних даних при відлагодженні програми рекомендується виконати перенаправлення вводу даних з клавіатури на ввід даних з попередньо створеного текстового файлу. Перенаправлення потоків здійснюється у режимі командного рядка, наприклад:
C:\Students\KH-215\Lab10.exe < MyData.txt
В результаті дані з файлу MyData.txt будуть прочитані функціями вводу програми Lab10.exe .
ВИМОГИ ДО ОФОРМЛЕННЯ ЗВІТІВ ПРО ВИКОНАННЯ ЛАБОРАТОРНИХ РОБІТ
Звіти про виконання лабораторних робіт оформляються в окремому зошиті або на зшитих аркушах формату А4. Після завершення семестру звіти здаються для зберігання на кафедру.
Кожен звіт повинен починатись з нової сторінки і містити такі розділи:
Номер та назва роботи;
Мета виконання лабораторної роботи;
Індивідуальне завдання з детальним формулюванням розв’язуваної задачі;
Графічна схема алгоритму розв’язування задачі з поясненням;
Текст програми на мові Паскаль чи С/C++. Програма повинна контролювати правильність вводу вхідних даних та мати коментарі до її основних структурних конструкцій.
Результати комп’ютерної реалізації програми. Вказується формат і значення вхідних даних та отриманих для них результатів;
Висновки. Вказується призначення програми, обмеження на її застосування, можливі варіанти вдосконалення та які знання отримано в ході виконання роботи.
Звіт повинен бути написаний українською мовою, акуратно та грамотно, з дотриманням правил оформлення ділової докумен тації. Назви розділів звіту візуально виділити розміром, жирністю, курсивом шрифта або підкресленням.
ЗАВДАННЯ ДЛЯ ЛАБОРАТОРНИХ РОБІТ
Лабораторна робота №1
Тема: моделювання представлення в памяті векторів і таблиць.
Мета роботи: набуття навичок розміщення в памяті векторів і таблиць
Завдання на роботу
Розробити спосіб економного зберігання в памяті розріджених матриць (таблиць). Розробити процедури і функції для забезпечення доступу (читання-запис) до елемнтів матриці. В контрольному прикладі забезпечити читання і запис всіх елементів матриці. Оцінити час виконання операцій.
Варіанти індивідуальних завдань
№
Завдання
1
всі нульові елементи розміщені в лівій частині матриці
2
всі нульові елементи розміщені в правій частині матриці
3
всі нульові елементи розміщені вище головної діагоналі
4
всі нульові елементи розміщені в верхній частині матриці
5
всі нульові елементи розміщені в нижній частині матриці
6
всі елементи непарних стрічок - нульові
7
всі елементи парних стрічок - нульові
8
всі елементи непарних стовпчиків - нульові
9
всі елементи парних стовпчиків - нульові
10
всі нульові елементи розміщені в шаховому порядку, починаючи з 1-го елементу 1-ї стрічки
11
всі нульові елементи розміщені в шаховому порядку, починаючи з 2-го елементу 1-ї стрічки
12
всі нульові елементи розміщені на місцях з парними індексами стрічок і стовпчиків
13
всі нульові елементи розміщені на місцях з непарними індексами стрічок і стовпчиків
14
всі нульові елементи розміщені вище головної діагоналі на непарних стрічках і нижче головної діагоналі - на парних
15
всі нульові елементи розміщені нижче головної діагоналі на непарних стрічках і вище головної діагоналі - на парних
№
Завдання
16
всі нульові елементи розміщені на головній діагоналі, в перших 3 стрічках вище діагоналі і в останніх 2 стрічках нижче діагоналі
17
всі нульові елементи розміщені на головній діагоналі і в верхній половині області вище діагоналі
18
всі нульові елементи розміщені на головній діагоналі і в нижній половині області нижче діагоналі
19
всі нульові елементи розміщені на стрічках, індекси яких кратні 3
20
матриця розділена діагоналями на 4 трикутника, елементи верхнього і нижнього трикутників нульові
21
нульові елементи розміщені в верхній и нижній четвертях матриці
22
нульові елементи розміщені в лівій и правій четвертях матриці
23
нульові елементи розміщені в лівій и верхній четвертях матриці
24
нульові елементи розміщені на стрічках, індекси яких кратні 3
25
нульові елементи розміщені на стовпчиках, індекси яких кратні 3
26
нульові елементи розміщені в верхній третині стрічок і середній третині стовпчиків
27
нульові елементи розміщені в верхній третині стрічок, першій і третій третині стовпчиків
28
нульові елементи розміщені в верхньому і нижньому трикутнику, за умови розділення матриці діагоналями на 4 трикутника
29
нульові елементи розміщені в лівому і правому трикутнику, за умови розділення матриці діагоналями на 4 трикутника
30
нульові елементи розміщені на головній діагоналі і в нижній половині матриці нижче діагоналі, індекси яких кратні 3
Лабораторна робота №2
Тема: операції над стрічками.
Мета роботи: набуття практичних навичок застосування операцій над стрічками.
Завдання на роботу
Розробити процедури та функції які забезпечують виконання операції вказаних в завданні.
В контрольному прикладі передбачити всі можливі комбінації вхідних пареметрів (нульова довжина, вихід за межі стрічки і т.п.), в тому числі і неправильні.
Варіанти індивідуальних завдань.
№
Завдання
1
Copies(s,s1,n)
копіювання стрічки s в стріку s1 n раз
2
Words(s)
подрахунок кількості слів в стрчці s
3
Parse(s,c)
разбиття стрічки s на дві частини: до першого вхождення символу c і після
4
Center(s1,s2)
центрування - розміщення стрічки s1 в середині стрічки s2
5
Left(s,m)
вирівнювання стрічки s зліва до довжини m
6
Right(s,m)
вирівнювання стрічки s зправа до довжини m
7
Reverse(s)
Реверсування стрічки s
8
LastPos(s,s1)
пошук останньго вхождення підстрічки s1 в стрічку s
9
WordIndex(s,n)
Визначення позиції початку в стрічці s слова з номером n
10
WordLength(s,n)
Визначення довжини слова з номером n
11
WordCmp(s1,s2)
Порівняння стрічок (з ігноруванням множинних пробілів).
12
StrSpn(s,s1)
знахождення довжини тої частини стрічки s, яка містить тільки символи з стрічки s1
13
Overlay(s,s1,n)
перекриття частини стрічки s, починаючи з позиції n стрічкою s1
14
StrLength(s)
визначити кількість символів в стрічці s не враховуючи пробіли
15
StrCChar(s,c1,s2, n)
замінити всі символи с1 в стрічці s починаючи з позиції n на стрічку s2
16
StrLB(s,n)
замінити в стрічці s, починаючи з позиції n, всі малі букви на великі
17
StrDel(s,n,k)
видалити з стрічки s підстрічку, начинаючи з позиції n довжиною к
18
StrAdd(s,s1,n)
вставити в стрічку s підстрічку s1, починаючи з позиції n
19
StrLWord(s,k)
Визначити кількість слів довжиною к символів в стрічці s
20
DelBlank(s)
видалити в стрічці s головні, хвостові і множинні пробіли
21
Split(s,s1,s2, с)
Розбити стрічку s на дві стрічки s1 і s2, в одній всі символи менші с, в іншій відповідно більші
№
Завдання
22
StrBL(s,n)
замінити в стрічці s, починаючи з позиції n, всі великі букви на малі
23
NumCount(s)
Порахувати кількість цифр в стрічці s
24
NumCut(s)
Вирізати всі цифри зі стрічки s
Лабораторна робота №3
Тема: Інтегровані структури даних, запису.
Мета роботи: придбання і закріплення навиків в роботі із записами, в інтеграції даних, в модульному програмуванні.
Завдання на роботу
Для заданої прикладної області розробити опис об'єктів цієї області. Розробити процедури, що реалізують базові операції над цими об'єктами, зокрема:
текстове введення-виведення (консольний і файловий);
присвоювання;
задання константних значень;
порівняння (не менше 2-х типів).
Підготувати файл початкових даних, що містять не менше 10 значень конкретних об'єктів.
Використовуючи процедури і описи модуля типу даних, розробити програму, що забезпечує введення початкових даних з першого файлу даних в пам'ять і зберігання їх в масиві, сортування масиву по алфавітному і по числовому параметру.
Варіанти індивідуальних завдань
Для кожної області перераховані параметри об'єкту. Серед параметрів обов'язково є ключове алфавітне поле (наприклад, прізвище), яке ідентифікує об'єкт, у кожного об'єкту є також одне або декілька числових полів, по яким вірогідні звернення до об'єкту. Набір характеристик може бути розширений і ускладнений по розсуду виконавця.
Nпп
Прикладна область
Атрибути інформації
1
Відділ кадрів
прізвище співробітника, ім'я, по батькові, посада, стаж роботи, оклад
2
Червона книга
вид тварини, рід, сімейство, житло, чисельність популяції
Nпп
Прикладна область
Атрибути інформації
3
Виробництво
позначення виробу, група до якої воно відноситься, рік випуску, об'єм випуску, витрату металу
4
Персональні ЕОМ
фірма-виробник, тип процесора, тактова частота, місткість ОЗП, місткість жорсткого диска
5
Бібліотека
автор книги, назва, рік видання, код УДК, ціна, кількість в бібліотеці
6
Супутники планет
назва, назва планети-господаря, рік відкриття, діаметр, період обігу
7
Радіодеталі
позначення, тип, номінал, кількість на схемі, позначення можливого замінника
8
Текстові редактори
найменування, фірма-виробник, кількість вікон, кількість шрифтів, вартість
9
Телефонна станція
номер абонента, прізвище, адреса, наявність того, що блокує, заборгованість
10
Побут студентів
прізвище студента, ім'я, по батькові, факультет, розмір стипендії, число членів сім'ї
11
Спортивні змагання
прізвище спортсмена, ім'я, команда, вид спорту, заліковий результат, штрафні очки
12
Змагання факультетів по успішності
факультет, кількість студентів, середній бал по факультету, кількість відмінників, кількість двієчників
13
С/г роботи
прізвище студента, ім'я, по батькові, факультет, вид робіт, заробіток
14
Сільське господарство
найменування с/г підприємства, вид власності, кількість тих, що працюють, основний вид продукції, прибуток
15
Відомості про сім'ю
прізвище студента, ім'я, по батькові, факультет, спеціальність батька, спеціальність матері, кількість братів і сестер
16
Скотарство
вид тварин, кількість особин в стаді у віці до 1 року, кількість особин 1 - 3 років, понад 3 роки, смертність в кожній групі, народжуваність
17
Мікросхеми пам'яті
позначення, розрядність, місткість, час доступу, кількість на схемі, вартість
18
Опис зображення
тип фігури (квадрат, коло і т.п.), координати на площини, числові характеристики
Nпп
Прикладна область
Атрибути інформації
19
Лісове господарство
найменування зеленого масиву, площа, основна порода, середній вік, густина дерев на кв.км
20
Міський транспорт
вид транспорту, номер маршруту, початкова зупинка, кінцева зупинка, час в дорозі
Лабораторна робота №4
Тема: Стек і черга. Хеш таблиця.
Мета роботи: набуття навичок моделювання зв’язаних динамічних структур даних та роботи з ними
Завдання на роботу
Розробити підпрограми, які забезпечують запити на запис або читання даних з черги, стека або дека. Для організації вказаних структур використовувати масиви або списки. Перевірити працездатність розроблених підпрограм. Послідовність виконання операцій запису або читання вибираються випадково. Порівняти результати роботи, зробити висновки.
Варіанти індивідуальних завдань.
№
Завдання
1
Розробити підпрограми роботи пріоритетною чергою. Постановка запитів в чергу виконується по пріоритету, зняття - з молодших адрес ( засади черги). Черга організована на масиві із зсувом після кожного читання, і на масиві із зсувом після досягнення межі пам'яті, яка виділена для черги. Пріоритет: мin значення числового параметра, при збігу параметрів - LIFO
2
Розробити підпрограми роботи з Деком. Дек організований на масиві з циклічним заповненням і з використанням двонаправленого списку. Операції виконуються з обох кінців Дека
3
Розробити підпрограми роботи з пріоритетною чергою. Постановка запитів в чергу виконується підряд в кінець черги, зняття - по пріоритету. Черга організована на масиві або списку. Пріоритет: мin значення числового параметра, при збігу параметрів - LIFO
4
Розробити підпрограми роботи із стеком. Стек організований на масиві з використанням двонаправленого списку
№
Завдання
5
Розробити підпрограми роботи з Деком. Дек організований на масиві з циклічним заповненням і з використанням двонаправленого списку. Операції виконуються з різних кінців Дека
6
Розробити підпрограми роботи з пріоритетною чергою. Встановлення запитів в чергу виконується по пріоритету, зняття - з молодших адрес (початок черги). Черга організована на масиві з циклічним заповненням і із зрушенням. Пріоритет: мах значення числового параметра, при збігу параметрів - FIFO
7
Розробити підпрограми роботи з пріоритетною чергою. Встановлення запитів в чергу виконується по пріоритету, зняття - зі старших адрес (кінець черги). Черга організована на масиві або на списку. Пріоритет: мах значення числового параметра, при збігу параметрів - FIFO
8
Розробити підпрограми роботи з деком. Дек організований на масиві з циклічним заповненням і із зрушенням. Операції виконуються з обох кінців Дека.
9
Розробити підпрограми роботи з пріоритетною чергою. Встановлення запитів в чергу виконується по пріоритету, зняття - з молодших адрес (початок черги). Черга організована на масиві з циклічним заповненням і списку. Пріоритет: мах значення числового параметра, при збігу параметрів - FIFO.
10
Розробити підпрограми роботи з деком. Дек організований на масиві з циклічним заповненням і із зрушенням. Операції виконуються з різних кінців Дека
11
Розробити підпрограми роботи з пріоритетною чергою. Встановлення запитів в чергу виконується по пріоритету, зняття - з молодших адрес (початок черги). Черга організована на масиві із зрушенням після кожного читання і на масиві із зрушенням після досягнення межі пам'яті, яка виділена для черги. Пріоритет: мах значення числового параметра, при збігу параметрів - FIFO.
12
Розробити підпрограми роботи з пріоритетною чергою. Встановлення запитів в чергу виконується по пріоритету, зняття - з молодших адрес (початок черги). Черга організована на масиві з циклічним заповненням і із зрушенням. Пріоритет: мin значення числового параметра, при збігу параметрів - LIFO.
13
Розробити підпрограми роботи з пріоритетною чергою. Встановлення запитів в чергу виконується по пріоритету, зняття - зі старших адрес (кінець черги). Черга організована на масиві і на списку. Пріоритет: мin значення числового параметра, при збігу параметрів - LIFO.
14
Розробити підпрограми роботи з пріоритетною чергою. Встановлення запитів в чергу виконується по пріоритету, зняття - з молодших адрес (початок черги). Черга організована на масиві з циклічним заповненням і списку. Пріоритет: мin значення числового параметра, при збігу параметрів - LIFO.
15
Розробити підпрограми роботи з пріоритетною чергою. Встановлення запитів в чергу виконується підряд в кінець черги, зняття - по пріоритету . Черга організована на масиві і списку. Пріоритет: мах значення числового параметра, при збігу параметрів - FIFO
16
Розробити процедуру хешування масива записів, в який передбачається часте додавання даних.
Лабораторна робота №5
Тема: робота з динамічними структурами.
Мета роботи: набуття практичних навичок опрацювання таких динамічних структур як звязні списки і дерева.
Завдання на роботу
Розробити програми які виконують операції вказані в індивідуальному завданні.
Програму для роботи з двонапрваленими звязними списками. Кожен елемент списку містить зсилки на наступний і попередній елемент в списку. Програма повинна забезпечувати ввід і побудову списку.
Програму для роботи для роботи з деревами. Кожен елемент дерева містить зсилку на батьківський елемент і зсилки на елементи-нащадки (необмежена кількість). Програма повинна забезпечувати ввід і побудову дерева.
Кожен елемент списку містить інформаційне поле(атрибут) деякого простого типу: символ, стрічка, число.
Всі операції над динамісними стурктурами повинні супроводжуватись відповідним виводом на екран.
В контрольних прикладах забезпечити опрацювання стурктур з 10-20 елементами.
Варіанти індивідуальних завдань.
№
Двонапаравлений звязний список
Дерево
1
Видалення елемента зі списку за вказаним значенням інформаційного атрибуту.
Знайти значення максимуму і мінімуму арифметичних чисел в дереві кожен елемент якого містить деяке число як значення інформаційного показника.
2
Вставка нового елемента в список після вказаного елемента за значенням інформаційного атрибуту.
Визначення кількості нащадків в кожного елемента дерева.
3
Вставка нового елемента в список перед вказаним елементом за значенням інформаційного атрибуту.
Визначення елемента дерева який має найменшу кількість безпосередніх нащадків.
4
Вставка елемента в список у вказану позицію.
Визначення найкоротшої стрічки в дереві кожен елемент якого містить деяку стрічку як значення інформаційного показника.
5
Видалення зі списку повторень.
Вставка нового елемента в дерево як предок елемента зі вказаним значенням інформаційного атрибуту.
6
Видалення другого і передостаннього елемента списку.
Розбиття дерева на два дерева за вказаним значенням інформаційного атрибуту елемента для розбиття.
7
Видалення елемента зі списку за вказаним порядковим номером.
Видалення елемента з дерева за вказаним значенням інформаційного атрибуту. (Нащадки видаленого елемента стають нащадками батьківського елемента видаленого)
8
Доповнення списку з обох кінців.
Видалення елемента з дерева за вказаним значенням інформаційного атрибуту. (Нащадки видаляються)
9
Розбиття списку на два списки за вказаним порядковим номером елемента для розбиття.
Визначення середнього арифметичного чисел в дереві кожен елемент якого містить деяке число як значення інформаційного показника.
10
Розбиття списку на два списки за вказаним значенням інформаційного атрибуту елемента для розбиття.
Визначення елемента дерева, який розміщений «найдалі» від кореня дерева.
№
Завдання
Завдання
11
Розбиття списку на два списки, один з яких містить всі елемента зі значенням інформаційного атрибуту меншим вказаного значенням інформаційного атрибуту, а інший відповідно зі значеннями більшими вказаного значення.
Визначення елементу дерева який має найбільшу кількість безпосередніх нащадків.
12
Сортування списку методом бульбашки.
Визначення найдовшої стрічки в дереві кожен елемент якого містить деяку стрічку як значення інформаційного показника.
13
Видалення всіх елементів з парним порядковим номером.
Вставка нового елемента в дерево як нащадок елемента зі вказаним значенням інформаційного атрибуту.
14
Видалення всіх елементів з непарним порядковим номером.
Розбиття дерева на два дерева за вказаним значенням інформаційного атрибуту елементу для розбиття.
15
Вставка нових елементів на непарні позиції в списку.
Видалення елемента з дерева за вказаним значенням інформаційного атрибуту. (Нащадки видаленого елемента стають нащадками батьківського елемента видаленого)
16
Вставка нових елементів на прані позиції в списку.
Видалення елемента з дерева за вказаним значенням інформаційного атрибуту. (Нащадки видаляються)
17
Розбиття списку на два списки за вказаним порядковим номером елементу для розбиття.
Вставка нового елемента в дерево як предок елемента зі вказаним значенням інформаційного атрибуту.
18
Розбиття списку на два списки за вказаним значенням інформаційного атрибуту елементу для розбиття.
Розбиття дерева на два дерева за вказаним значенням інформаційного атрибуту елементу для розбиття.
19
Розбиття списку на два списки, один з яких містить всі елементи зі значенням інформаційного атрибуту більшим вказаного значенням інформаційного атрибуту, а інший відповідно зі значеннями меншим вказаного значення.
Видалення елемента з дерева за вказаним значенням інформаційного атрибуту. (Нащадки видаленого елемента стають нащадками батьківського елемента видаленого)
20
Сортування списку методом бульбашки.
Видалення елемента з дерева за вказаним значенням інформаційного атрибуту. (Нащадки видаляються)
21
Видалення всіх елементів з парним порядковим номером.
Визначення середнього арифметичного чисел в дереві кожен елемент якого містить деяке число як значення інформаційного показника.
22
Видалення всіх елементів з непарним порядковим номером.
Визначення елементу дерева який розміщений «найдалі» від кореня дерева.
23
Вставка нових елементів на непарні позиції в списку.
Визначення елементу дерева який має найбільшу кількість безпосередніх нащадків.
24
Вставка нових елементів на прані позиції в списку.
Визначення всіх «листків» дерева.
25
Видалення елемента зі списку за вказаним значенням інформаційного атрибуту.
Вставка нового елемента в дерево як нащадок елемента зі вказаним значенням інформаційного атрибуту.
26
Вставка нового елемента в список після вказаного елемента за значенням інформаційного атрибуту.
Розбиття дерева на два дерева за вказаним значенням інформаційного атрибуту елементу для розбиття.
27
Вставка нового елемента в список перед вказаним елементом за значенням інформаційного атрибуту.
Видалення елемента з дерева за вказаним значенням інформаційного атрибуту. (Нащадки видаленого елемента стають нащадками батьківського елемента видаленого)
28
Вставка елемента в список у вказану позицію.
Видалення елемента з дерева за вказаним значенням інформаційного атрибуту. (Нащадки видаляються)
29
Видалення зі списку повторень.
Визначення всіх «листків» дерева.
Лабораторна робота №6
Тема: Рекурсивні алгоритми обробки структур даних.
Мета роботи: набуття практичних навичок роботи з рекурсивними функціями.
Завдання на роботу
Розробити програмт згідно алгооритму з використарнням рекурсивної функції та без використання рекурсивної функції. Оцінити час виконання та складність алгоритму.
Варіанти індивідуальних завдань.
№
Завдання
№
Завдання
1
16
2
17
3
18
4
19
5
20
6
21
7
22
8
23
9
24
№
Завдання
№
Завдання
10
25
11
26
12
27
13
28
14
29
15
30
Лабораторна робота №7
Тема: Дерева. Бінарні дерева. Пошук.
Мета роботи: набуття навичок програмування дерев.
Завдання на роботу
Розробити засоби динамічного збереження дерев та виконання дій над ними згідно варіанту.
Варіанти індивідуальних завдань.
№
Завдання
Перевірити, чи двійкове дерево є збалансованим.
Знайти вершину в дереві.
Розробити програму для роботи з червоно-чорним деревом та процедуру пошуку в ньому.
Розробити програму побудови бінарного дерева за арифметичним виразом (наприклад, 2+3-5+7)
Знищити заданий елемент в бінароному дереві.
Додати вершину у впорядковане бінарне дерево.
№
Завдання
Додати вершину у невпорядковане дерево.
Здійснити заміну значення заданої вершини.
Вивести на друк листи дерева.
Вивести на друк ліві вершини дерева.
Вивести на друк всі вершини, значення яких більше за корінь на одиницю.
Вивести на друк праві вершини дерева.
Вивести на друк всі вершини, значення яких більше за корінь на задану величину.
Перевірити зи допомогою дерева, чи стрічка є паліндромом
Побудувати дерево синтаксичного розрору речення
Вивести на друк всі ліві вершини збалансованого дерева
Вивести на друк всі червоні вершини червоно-чорного дерева
Вивести на друк всі чорні вершини червоно-чорного дерева
Знайти в бінарному дереві вершину, сума значень прямих нащдків якої є максимальна
Знайти в бінарному дереві вершину, сума значень прямих нащдків якої є максимальна
Лабораторна робота №8
Тема: Графи. Обхід графу. Пошук.
Мета роботи: набуття навичок програмування графів.
Завдання на роботу
Забезпечити зберігання графа у вигляді матриці суміжності.
Варіанти індивідуальних завдань.
№
Завдання
Розробити алгоритм знаходження зв’язних підграфів заданого графа.
Розробити програму обходу графа вшир, поданого матрицею суміжності.
Розробити програму обходу графа вглиб, поданого матрицею суміжності.
№
Завдання
Розробити програму пошуку вершини в графі.
Розробити програму пошуку вершини в графі за її значенням.
Розробити програму, результатом якої є стек, сформований на основі послідовності вершин, отриманих при обході вглиб.
Розробити програму, результатом якої є черга, сформований на основі послідовності вершин, отриманих при обході вшир.
Дерево — це зв'язний ациклічний (що не має циклів) граф. Кожен граф, що не містить циклів, називається лісом. Представити алгоритм, що визначає, чи є граф деревом.
Розробити програму, яка за матрицею суміжності формує множину ребер.
Знайти у графі двонаправлені ребра.
Сформувати множину вершин, з яких виходять ребра заданої вартості.
Сформувати множину ребер, які є ациклічними.
Знайти у графі петлі
Знайти вартість шляху між заданими вершинами. Якщо прямого шляху нема, то вивести повідомлення
Лабораторна робота №9
Тема: алгоритми пошуку та сортування для одновимірних масив.
Мета роботи: набуття практичних навичок застосування алгоритмів пошуку та сортування.
Завдання на роботу
Розробити процедури та функції для пошуку в одновимірних масивах посортованих та непосортованих та для їх сортування. В контрольному прикладі забезпечити пошук потрібних елементів в непосортованих масивах. Здійснити їх сортування. Здійснити пошук в посортованих масивах. Оцінити час виконання операцій.
Варіанти індивідуальних завдань.
Розробити процедури та функції для пошуку в одновимірних масивах посортованих та непосортованих та для їх сортування. В контрольному прикладі забезпечити пошук потрібних елементів в непосортованих масивах. Здійснити їх сортування. Здійснити пошук в посортованих масивах. Оцінити час виконання операцій.
№
Завдання
1
Елементи, які присутні в обох масивах А і В
2
Елементи, які є тільки в масиві А або тільки в масиві В
3
Елементи, котрі присутні в масиві А, але відсутні в масиві В
4
Елементи, котрі присутні в обох масивах А і В в декількох екземплярах
5
Елементи, котрі присутні в декількох екземплярах в масиві А, але відсутні в масиві В
6
Елементи, котрі присутні в декількох екземплярах або тільки в масиві A, або тільки в масиві В
7
Елементи, котрі присутні в декількох екземплярах або в масиві А, або в масиві В (або в обох масивах)
8
Елементи масиву А, які повторюються в масиві В декілька раз
9
Елементи присутні в обох масивах А і В в одному екземплярі
10
Елементи, присутні в одному екземплярі або тільки в масиві А, або тільки в масиві В
11
Елементи масиву А, які повторюються і одночасно є в масиві В
12
Елементи масиву А, які повторюються і одночасно є в масиві В в одному екземплярі
13
Елементи масиву А, які не повторюються і одночасно є в масиві В в декількох екземплярах
14
Елементи масиву А, які повторюються і одночасно відсутні в масиві В
15
Елементи масиву А в одному екземплярі, котрі є в масиві В тільки в одному екземплярі
16
Елементи масиву А в одному екземплярі, котрі є в масиві В тільки в декількох екземплярах
17
Елементи, які присутні в декількох екземплярах або тільки в масиві А, або тільки в масиві В
18
непарні елементи масиву А, котрі парні в масиві В
19
елементи, присутні в обох масивах А і В і більші числа К
20
елементи, котрі є тільки в масиві А або в масиві В
21
парні елементи масиву А, присутні в масиві В
22
неповторювані елементи масиву А, котрих нема масиві В
23
елементи масиву А в одному екземплярі, котрі присутні в масиві B
№
Завдання
24
елементи масиву A, присутні в одному екземплярі в масиві B
25
елементи масиву В, які повторюються в масиві А декілька раз
26
елементи масивів, котрі присутні в масиві В, але відсутні в масиві А
27
елементи масивів, котрі присутні непарну кількість раз в обох масивах А і В
28
елементи масивів, котрі присутні в декількох екземплярах в масиві В, але відсутні в масиві А
29
елементи масивів, котрі присутні в декількох екземплярах або тільки в масиві A, або тільки в масиві В
30
знайти медіани масивів А і В
Алгоритми пошуку:
Лінійний пошук;
Лінійний пошук з бар’єром;
Бінарний пошук;
Пошук Фібоначі;
Пошук з перестановкою в початок;
Пошук с транспозицією;
Алгоритми сортування:
Сортування обміном
Сортування вибором
Бульбашкове сортування
Сортування включениями
Бульбашкове сортування вставками.
Швидке сортування
Сортування Шелла
Пірамідальне сортування
Сортування Хоара.
Лабораторна робота №10
Тема: робота зі структурами і файлами.
Мета роботи: набуття практичних навичок опрацювання структур та роботи з файлами.
Завдання на роботу
Розробити програму яку забезпечує опрацювання структур даних і їх збереження у файлі.
Опис деякого об’єкту здійснюється за допомогою типу даних структура. Необхідно забезпечити опрацювання 3-5 атрибутів об’єкту з використанням різних простих типів даних (стрічки, символи, числа, логічний тип)ю Забезпечити виконання таких операцій:
Ввід даних;
Пошук за значенням атрибуту;
Послідовний перегляд;
Модифікацію значень атрибутів об’єктів (структури що його описує);
Видалення об’єкту (структури що його описує);
Сортування за значеннями атрибутів;
Результати всіх операцій повинні зберігатись у файлі.
В контрольному прикладі продемонструвати виконання основних операцій з файлом який містить 10-20 збережених описів об’єктів.
Варіанти індивідуальних завдань.
Кожен студент обирає довільний об’єкт для опису у вигляді структури.
ЛІТЕРАТУРА ДО ЛАБОРАТОРНИХ ЗАНЯТЬ
Абрамов С.А. и др. Задачи по программированию. — М.: Наука, 1988.
Ван Тассел Д. Стиль, разработка, эффективность, отладка и испытание программ. — М.: Мир, 1981.
Дейкстра Э. Дисциплина программирования. М.: Мир, 1978.
Лэгсам Й, Огенстайн М. Структуры данных для персональных ЭВМ — М: Мир, 1989 -586с.
Турбо Паскаль 7.0 — Киев: BHV,
Ділись своїми роботами та отримуй миттєві бонуси!
0%
Оголошення від адміністратора