Подякувати Студентському архіву довільною сумою
Admin
26.02.2023 12:38
Дякуємо, що користуєтесь нашим архівом!
Інформація про навчальний заклад
ВУЗ:
Національний університет Львівська політехніка
Інститут:
Не вказано
Факультет:
Комп'ютерна інженерія
Кафедра:
Кафедра ЕОМ
Інформація про роботу
Рік:
2007
Тип роботи:
Методичні вказівки
Предмет:
Структури даних та алгоритми
Частина тексту файла (без зображень, графіків і формул):
МІНІСТЕРСТВО ОСВІТИ І НАУКИ УКРАЇНИ
НАЦІОНАЛЬНИЙ УНІВЕРСИТЕТ “ЛЬВІВСЬКА ПОЛІТЕХНІКА”
Кафедра ЕОМ
Структури даних та алгоритми
Методичні вказівки і завдання
до курсової роботи
з дисципліни "ПРОГРАМУВАННЯ"
для студентів базового напрямку 6.0915
“Комп’ютерна інженерія”
Львів – 2007
Методичні вказівки і завдання до курсової роботи ”Структури даних та алгоритми” з курсу ”Програмування ” для студентів базового напрямку 6.0915 ”Комп’ютерна інженерія” / Укл. Лисак Т.А. – Львів: НУ”ЛП”, 2007. – 29 c.
Укладач Лисак Т.А., ст. викладач
Рецензенти Березко Л.О., канд.техн.наук, доц.
Мархивка В.С., ст. викладач
Відповідальний за випуск Мельник А.О., д-р техн.наук, проф.
ЗМІСТ
ВСТУП 4
1. ВИМОГИ ДО ПОРЯДКУ ВИКОНАННЯ ТА ОФОРМЛЕННЯ
КУРСОВОЇ РОБОТИ 5
1.1. Вимоги до розробки програмних продуктів 5
1.2. Вимоги до оформлення пояснювальної записки 5
2. ВАРІАНТИ ЗАВДАНЬ 7
2.1. Завдання 1 7
2.2. Завдання 2 8
2.3. Завдання 3 9
СПИСОК ЛІТЕРАТУРИ 22
ВСТУП
Комп’ютер – це машина, що обробляє інформацію. Вивчення засобів програмування передбачає вивчення того, яким чином ця інформація організована всередині ЕОМ, як вона обробляється і як може бути використана. Тому, для вивчення дисципліни студенту особливо важливо зрозуміти концепцію організації даних і роботи з ними.
Програма представляє собою в кінцевому рахунку конкретні формулювання абстрактних алгоритмів, що базуються на конкретних представленнях і структурах даних. Зрозуміло, що рішення про структури даних які необхідно застосувати неможливо прийняти без знання алгоритмів, що застусовуються до цих даних, і навпаки, вибір алгоритмів суттєво залежить від вибраних структур даних. Отже, структури програм і структури даних нерозривно пов’язані.
В курсовій роботі спочатку розглядаються фундаментальні структури які складаються з простих даних. Вони представляють собою компоненти, з яких складаються більш складні структури. Змінні фундаментальної структури можуть змінювати тільки своє значення, зберігаючи незмінною свою форму. Таким чином, розмір пам’яті яку вони займають залишається постійним. Навпаки, ускладнені структури характеризуються зміною не тільки значення, але й форми під час виконання програми. Тому для йх реалізації необхідно застусовувати більш складні прийоми. Послідовний файл займає проміжне значення, поскільки хоча його довжина й змінюється, але ця зміна форми є тривіальною. Поскільки послідовний файл грає важливу роль практично у всіх обчислювальних системах, він буде розглядатись разом з фундаментальними структурами.
В першому завданні курсової роботи досліджується представлення в пам’яті комп’ютера даних статичної структури. Розглядаються прості (цілі, дійсні, символьні, логічні, перелічувані, обмежені) і складові або фундаментальні (масиви, множини, записи, рядки символів, файли) структури даних.
В другому завданні будується одна з більш складних динамічних структур даних (стеки, черги, списки, дерева, графи), розробляються алгоритми і програмні реалізації роботи з нею і за їх допомогою розв’язується прикладна задача.
В другому завданні будується один з методів сортування або пошуку. Досліджуються основні характеристики цього метода і проводиться порівняння ефективностей даного метода і класичних методів. Алгоритмам сортування і пошуку приділяється стільки уваги у зв’язку з тим, щоза їх допомогою можна проилюструвати багато принципів програмування і ситуацій, що виникають і в інших задачах.
Велике значення в курсовій роботі приділяється методиці розробки програмних продуктів і стилю програмування.
Метою курсової роботи є:
- систематизувати, закріпити і розширити теоретичні і практичні знання з програмування, навчитися застосовувати різноманітні структури даних та алгоритми при розв'язанні конкретних прикладних задач;
отримати навики розробки більш складних програмних продуктів і оформлення програмної документації.
1. ВИМОГИ ДО ПОРЯДКУ ВИКОНАННЯ ТА ОФОРМЛЕННЯ
КУРСОВОЇ РОБОТИ
Завдання на курсову роботу видаються студенту керівником курсової роботи індивідуально. Можливі їх корегування керівником під час виконання роботи.
Виконуючи курсову роботу студент повинен розробити, відлагодити та протестувати програму на мові Си (або іншій, узгодивши із керівником курсової роботи) і оформити пояснювальну записку.
1.1. Вимоги до розробки програмних продуктів.
Програма має складатися із двох частин:
- модулів, що містять підпрограми, які реалізують суть кожного завдання;
- тестуючої програми, яка демонструє працездатність основних підпрограм.
Результати тестування мають видаватися у зручному для сприйтяття вигляді (текстовому, табличному, графічному). Текстові значення мають виводитися як на екран відеомонітора, так і в файл (при потребі). Вивід таблиць і графіків теж можна оформити як окремі підпрограми. Таблиці і графіки повинні мати заголовки та зручний для читання вигляд. Як підпрограму доцільно оформити і дії пов'язані із вводом даних необхідних для тестування.
Тестуюча програма повинна мати зручний користувацький інтерфейс, наприклад, вона повинна мати меню. Меню може бути декількаступеневим - після вибору пункту меню вищого рівня, з'являється меню наступного (підпорядкованого) рівня.
Для кожного завдання треба передбачити як ввід довільних вхідних даних, так і можливість використання деяких тестуючих значень по замовчуванню. Всі результати, що вводяться або виводяться мають обов’язково супроводжуватись повідомленнями.
Розроблена в курсовій роботі програма повинна легко читатися, відповідати вимогам структурного програмування, всі імена повинні нести змістовне навантаження, коментарів у програмі повинно бути стільки, щоб програма була самодокументованою.
1.2. Вимоги до оформлення пояснювальної записки
Пояснювальна записка повинна бути переплетена у тверду обкладинку.
Пояснювальна записка має бути написана українською мовою. Вона може бути надрукована або написана від руки. В обох випадках текст має розміщуватись на одному боці аркуша паперу формату А4. Рекомендується розміщувати до 30 рядків на сторінці.
Обсяг пояснювальної записки повинен становити 20 - 25 сторінок друкованого тексту або 25 – 30 сторінок рукописного тексту.
На аркушах необхідно залишити поля з усіх чотирьох боків. Розмір лівого поля - 25 мм, правого - не менше 10 мм, верхнього і нижнього - не менше 20 мм.
На аркушах, де починаються розділи, зміст, анотація, вступ, висновки, список літератури рекомендується збільшувати розмір верхнього поля до 40 мм.
Чорнило, яким виконується робота, має бути чорним, фіолетовим чи синім .
Пояснювальна записка має бути стислою, чіткою, лаконічною і містити лише інформацію, яка має пряме відношення до теми курсової роботи.
Рекомендується наступний склад розділів пояснювальної записки:
Титульна сторінка
Завдання на курсову роботу
Анотація
Зміст
Вступ
1. Завдання 1
1.1. Теоретична частина
1.2. Опис алгоритму
1.3. Система тестів
1.4. Текст програми
1.5. Результати виконання програми
2. Завдання 2
2.1. Теоретична частина
2.2. Опис алгоритму
2.3. Система тестів
2.4. Текст програми
2.5. Результати виконання програми
2.6. Дослідження методу
3. Завдання 3
3.1. Теоретична частина
3.2. Опис алгоритму
3.3. Система тестів
3.4. Текст програми
3.5. Результати виконання програми
Висновки
Список літератури
Додатки
В анотації викладаються короткі відомості про курсову ро боту. У вступі має приводитися коротка характеристика задач, їх місце і значення в тих галузях, до яких вони мають відношення. В тео ретичній частині мають приводитися всі теоретичні дані, які не обхідні для розробки алгоритму. Опис алгоритму містить текстові пояснення і блок-схеми алгоритму, які мають виконува тися згідно із стандартами [1]. В тексті програми описується зміст всіх програм і підпрограм, а самі тексти програм поміщаються в додатках.
Текст розділів може розділятися на підрозділи, пункти і підпункти. Розділи повинні нумеруватися арабськими цифрами в межах всієї записки. Вступ, висновки, список літератури і додатки не нумеруються.
Підрозділи необхідно нумерувати арабськими цифрами в межах кожного розділу. Номер підрозділу складається з номера розділу і номера підрозділу, розділених крапкою. Наприклад: "3.1." (перший параграф третього розділу). Пункти (якщо вони використовуються) нуме-руються аналогічно. Наприклад: "3.1.2." (другий пункт першого параграфу третього розділу).
Нумерація сторінок має бути наскрізною: першою сторінкою є титульна сторінка, другою - завдання, третьою - анотація і т.д. Номер сторінки проставляється у верхньому правому куті. На сторінках 1 (титульна сторінка), 2 (завдання), 3 (анотація) і 4 (перша сторінка змісту) номер сторінки не пишеться.
2. ВАРІАНТИ ЗАВДАНЬ
2.1. Завдання 1
Дослідити представлення в пам’яті комп’ютера даних статичної структури. Розглянути основні прості (цілі, дійсні, символьні, логічні) і складові або фундаментальні (масиви, структури, рядки символів) структури даних:
bool b1;
int i1;
short int i2 ;
unsigned short int i3 ;
long int i4;
unsigned long int i5 ;
float r1;
double r2;
long double r3;
char ch ;
char sl[15];
char m[2][5];
struct
{
char a1[10],a2[10];
char b1,b2,b3;
int c1,c2;
} str;
Тестування провести для наступних значень змінних:
true, якщо день народження парне число;
b1 =
false, якщо день народження непарне число;
i1 – день народження;
i2 = -i1;
i3 = i1*125;
i4 = -i3;
i5 = i3;
r1 – дробове число: ціла частина – місяць народження, дробова частина - рік народження;
r2 = r1*125;
r3 = -r2;
( Наприклад, якщо дата народження 21.10.1982, то:
i1 = 21; i2 = -21; i3 = 2625; i4 = -2625; i5 = 2625;
r1 = 10.1982; r2 = 1274.775; r3 = -1274.775; )
ch – перша літера Прізвища (велика українська літера);
sl – Прізвище ( українські літери, перша - велика, решта - малі);
m[i,j] – символ, який дорівнює відповідній цифрі номера мобільного телефону;
( Наприклад, якщо номер мобільного телефону є 0671234567 , то:
m[0,0]:=’0’; m[0,1]:=’6’; m[0,2]:=’7’; m[0,3]:=’1’; m[0,4]:=’2’;
m[1,0]:=’3’; m[1,1]:=’4’; m[1,2]:=’5’; m[1,3]:=’6’; m[1,4]:=’7’; )
str.a1 – назва міста в адресі прописки ( українські літери, перша - велика, решта - малі);
str.a2 – назва вулиці в адресі прописки ( українські літери, перша - велика, решта - малі);
str.с1 – номер будинку в адресі прописки;
str.с2 – номер квартири в адресі прописки;
str.b1 = ’,’ ;
str.b2 = ’,’ ;
str.b3 = ’/’ ;
2.2. Завдання 2
Реалізувати один із вказаних нижче методів сортування послідовності або пошуку в послідовності, яка представлена у вигляді лінійного однозв’язаного списку, елементи якого містять по декілька інформаційних полів (в загальному випадку – велики об’єми інформації), одне з яких є ключовим, і всі зміни положення елементів в послідовності виконуються не перестановкою самих елементів, а перестановкою їх зв’язків.
Намалювати схему алгоритму для конкретного прикладу послідовності з десяти цілих чисел зі знаком.
Дослідити метод на стійкіть (тільки для методів сортування).
Дослідити ефективність метода. Для цього визначити середні значення кількості порівнянь, кількості перестановок і часу виконання. Порівняти отримані характеристики з аналогічними даними для відповідних основних простих внутрішніх методів сортування (вставки, вибору, обміну), або зовнішніх методів сортування (простим злиттям, природнім злиттям), або методів пошуку ( послідовного, бінарного ), зробити висновки про ефективність метода, що досліджується.
Дослідити метод на економність використання пам’яті.
Дослідити метод на можливу специфіку вхідної послідовності (чи може послідовність містити елементи з одинаковими ключами, чи має бути вхідна послідовність частково відсортована, чи мають елементи послідовності знаходитись у певному діапазоні і т.п.).
Внутрішні методи cортування :
Сортування методом підрахунку порівнянь [6, 94-97 c.].
Сортування методом підрахунку розпреділення [6, 97-98 c.].
Сортування методом вставки у список [6, 116-117 c.].
Сортування з обчисленням адреси [6, 118-121 c.], [8, 469-472 c.].
Обмінне сортування зі злиттям [6, 131-133 c.].
Обмінне порозрядне сортування [6, 144-150 c.].
Сортування методом двохшляхового злиття [6, 181-182 c.].
Сортування методом природнього двохшляхового злиття [6, 183-185 c.].
Сортування методом простого двохшляхового злиття [6, 186-187 c.].
Сортування методом злиття списків [6, 187-189 c.].
Порозрядне сортування списку [6, 195-200 с.]
Сортування за допомогою вставок і злиття [6, 208-210 c.].
Сортування методом квадратичного вибору [11, 71-72 c.].
Швидке сортування [11, 72-73 c.].
Розподільне сортування [11, 73-75 c.].
Бітове сортування [11, 75 c.].
Бінарне сортування [11, 75-76 c.].
Сортування злиттям списків [11, 76 c.].
Сортування злиттям [11, 76-78 c.].
Сортування вставками, що використовує бінарний пошук [8, 473 c., 495-497 с.].
Сортування Шелла, що використовує кроки 3, 2 і 1 [8, 466-469 c.].
Сортування Шелла, що використовує кроки 8, 4, 2 і 1 [8, 466-469 c.].
Сортування Шелла, що використовує кроки 7, 5, 3 і 1 [8, 466-469 c.].
Сортування Шелла, що використовує кроки 13, 4 і 1 [8, 466-469 c.].
Сортування двохшляховими вставками [8, 472-473 c.].
Сортування злиттям вставок [8, 473 c.].
Сортування за допомогою комбінування методів швидкого сортування і сортування простимі вставками [8, 473 c. (3.)].
Сортування простим злиттям [8, 474-477 c.].
Порозрядне обмінне сортування [8, 477-478 c.].
Порозрядне сортування [8, 478-481 c.].
Сортування бінарним злиттям [8, 482 c.].
Зовнішні методи cортування :
Швидке сортування рядків [11, 167-170 c.].
Сортування методом збалансованого багатошляхового злиття [3, 122-128 c.].
Багатофазне сортування [3, 128-141 c.], [6, 294-300 c.].
Осцилююче сортування [6, 340-3345 c.].
Сортування методом розпреділення початкових серій [3, 141-147 c.].
Сортування методом каскадного злиття [3, 148-149 c.] , [6, 315-325 c.].
Сортування методом вибору з заміщенням [6, 284-285 c.].
Методи пошуку :
m-Блочний пошук [11, 113 c.].
Пошук медіани [3, 103-105 c.].
Індексно-послідовний пошук [8, 493-495 c.].
Пошук методом обчислення адрес (розв’язок колізій при хешуванні методом відкритої адресації ) [8, 530-534 c.], [6, 562-568 c.].
Пошук методом обчислення адрес (розв’язок колізій при хешуванні методом ланцюжків) [8, 534-536 c.], [6, 557-562 c.].
Пошук найменьшого елемента за допомогою метода швидкого сортування [6, 131 c.].
Швидкий послідовний пошук [6, 430-431 c.].
Зчеплений пошук [6, 440-441 c.].
Однорідний бінарний пошук [6, 447-449 c.].
Пошук Фібоначчі [6, 450-452 c.].
Променевий пошук [6, 527-531 c.].
Цифровий пошук зі вставкою по дереву [6, 532-534 c.].
2. 3. Завдання 3
Побудувати базову структуру даних і набір операцій для роботи з нею. Застосувати їх для розв’язання однієї з наступних задач згідно з варіантом. Під час виконання програми обов’язково відображати на екрані монітора всі зміни, що будуть відбуватись у вибраній структурі даних.
Використання для розв’язання задач методів сортування та пошуку даних :
1. У масиві A1, ... , AN знайти M найменших елементів масиву (M<N).
2. Знайти кількість різних чисел серед елементів даного масиву.
3. Дано n відрізків [aі , bі] на прямій (і=1..n). Знайти максимальне k, для якого існує точка прямої, покрита k відрізками ("максимальне число шарів").
4. Дано n точок на площині. Знайти незамкнуту ламану, що проходить через усі ці точки і жодного разу не перетинається. (Сусіднім відрізкам ламаної дозволяється лежати на одній прямій.)
5. Написати програму сортування структури, що складається з прізвища студента і одержуваної ним оцінки. При цьому спочатку йде сортування по оцінці, а усередині сортування по оцінці сортування студентів за алфавітом.
6. Нехай задано деякий словник. Знайти в ньому всі анаграми (слова, що складені з однакових літер).
7. Нехай є N камінців вагою А1, А2, ..., АN. Необхідно розкласти їх на дві купи таким чином, щоб ваги куп відрізнялися не більше, ніж у 2 рази. Якщо цього зробити не можна, то повідомити про це.
8. Нехай задано числа А1, А2, ..., АN та B1, B2, ..., BN. Скласти з них N пар (Аi , Bj ) таким чином, щоб сума добутків пар була максимальною (мінімальною). Кожне Ai та Bj у парах зустрічаються рівно один раз.
9. У музеї протягом дня відбувається реєстрація заходу та виходу кожного відвідувача. Таким чином, за день отримані N пар значень, де перше значення в парі показує час заходу відвідувача в музей, а друге значення - час його виходу. Знайти проміжок часу, на протязі якого в музеї одночасно знаходилося максимальне (мінімальне) число відвідувачів.
10. На сільській вулиці живуть Іванови і Петрови. Необхідно, використовуючи мінімальне число обмінів, розселити їх так, щоб Іванови жили з одного кінця вулиці, а Петрови - з іншого.
Використання для розв’язання задач динамічної структури даних ”Список” :
11. Група людей стоїть у колі і кожний вибирає ціле додатнє число. Вибирається одне з їх імен і додатнє число n. Відлік починається за годинниковою стрілкою, починаючи з людини з вибраним ім’ям. При цьому n-та людина виключається з кола. Вибране цією людиною додатнє число використовується для продовження рахунку. Кожен раз при вилученні наступної людини вибране нею число використовується для визначення наступної людини, що буде вилучена. Наприклад, будемо вважати, що маємо 5 людей – А,В,С,D і Е і вони вибрали числа 3,4,6,2 і 7 відповідно. Також спочатку було вибрано число 2 і людина А. Тоді, якщо рахунок був початий з А, порядок виключення людей з кола буде В,А,Е,С. Останнім у колі залишиться D. Визначити:
a) людину, що залишилася;
b) людину, з якої починався рахунок, якщо відома людина, що залишилася.
12. Змоделювати фабрику, що виробляє вироби з менших вузлiв. Назвемо елементарною деталлю такий вузол, що не складається з дрiбнiших вузлiв. Написати програму, що зчитує набiр рядків, якi мiстять чотирьохсимвольнi номери деталей. Перший такий номер у рядку означає неелементарну деталь, а решта чисел означають деталi, з яких складається ця неелементарна деталь. Цi складовi деталi можуть бути елементарними, а можуть складатись з iнших частин (у такому випадку їх номери з'являються першим номером у якомусь іншому рядку). Програма складає список з елементом заголовку для кожної неелементарної деталi. Заголовок мiстить назву неелементарної деталi i вказiвник на список елементiв, що описують її складовi частини. Вказiвники на заголовки спискiв послiдовно записуються в список. Для описаного представлення написати програму:
a) роздруку всiх неелементарних деталей.
б) виведення для кожної неелементарної деталi списку всiх елементарних деталей, з яких вона складається.
13. Перевірка орфографії. Написати програму, яка б перевіряла правильність введених слів, використовуючи запропонований словник. Словник зчитується з текстового файлу. Для організації словника використовувати хеш - таблицю. Вирішення колізій виконувати методом ланцюжків. Слова для перевірки вводити з клавіатури. Якщо слово, що перевіряється, правильне (тобто воно є в словнику), то виводиться відповідне повідомлення. Якщо слово неправильне, то виводяться всі можливі варіанти його заміни. Для варіантів заміни використовувати список, що адресується відповідним рядком хеш-таблиці. Якщо заміни немає, то нічого не виводиться.
14. В текстовому файлі задані послідовності трійок ( Xi , Yi , Pi ), де Xi – англійське слово, Yi – його український переклад, Pi – частота використання (в %) слова Xi в англійській мові. Послідовності пар ( Xi , Yi ) інтерпретуються як лінійні зв’язані списки. Слова, що мають однакову першу букву англійського алфавіту, розміщуються в один зв’язаний список і впорядковуються за спаданням частоти використання. Всі ці списки об’єднуються в список перших букв англійських слів. Написати програму формування такої структури даних та здійснення послідовного перекладу довільного англійського речення. За відсутності перекладу конкретного англійського слова залишити його неперекладеним.
15. Многочлен виду , де представити у вигляді зв’язаного списку в якому кожний елемент має три поля: одне – для коефіцієнта Сi , друге – для показника степеня ni , третє – для вказівника на наступний елемент списку. Для описаного представлення многочленів програмно реалізувати такі операції:
а) додавання двох многочленів;
б) множення многочлена на одночлен;
в) множення двох многочленів;
г) ділення двох многочленів з часткою і остачею у вигляді многочленів;
д) диференціювання многочлена;
16. Поліном від трьох змінних ( X , Y , Z ) представити у вигляді циклічного списку, в якому кожний елемент має п’ять полів: одне – для коефіцієнта члена поліному , друге – для показника степеня змінної X , третє – для показника степеня змінної Y, четверте – для показника степеня змінної Z, п’яте – для вказівника на наступний елемент списку. Елементи списку мають бути впорядковані спочатку по зменшенню степеня Х, пізніше по зменшенню степеня Y, а після цього по зменшенню степеня Z. Структура збереження поліномів повинна забезпечувати ефективне виконання таких операцій над ними:
а) додавання двох поліномів;
б) множення двох поліномів;
в) знаходження часткової похідної полінома по довільній змінній;
г) обчислення полінома по заданим значенням X , Y , Z ;
д) ділення двох поліномів з часткою і остачею від ділення;
е) інтегрування полінома по одній з його змінних;
ж) для чотирьох заданих поліномів F(X,Y,Z) , G(X,Y,Z) , H(X,Y,Z) , Q(X,Y,Z) обчислити поліном F( G(X,Y,Z) , H(X,Y,Z) , Q(X,Y,Z) ).
Приклад: Нехай задано два поліноми: P1(x,y,z)=x7y2z+3x2z-6y2-3z9 і P2(x,y,z)=-7x2z+6y2+5. В результаті виконання операції додавання буде отримано поліном: P3(x,y,z)=x7y2z-4x2z-3z9+5.
17. Написати програму для роботи з розрідженими матрицями, представленими у вигляді зв’язаних списків:
а) конвертація розрідженої матриці з нормальної форми у форму списків;
б) конвертація розрідженої матриці, представленої у формі списків у нормальну форму;
в) транспонування розрідженої матриці, заданої у формі списків;
г) додавання двох матриць, заданих у формі списків;
д) множення двох матриць, заданих у формі списків.
18. Написати програму роботи з довгими числами (довгі числа – це числа, що виходять за діапазон допустимих значень будь-якого стандартного цілого або дійсного типу). Структура збереження довгих чисел повинна забезпечувати ефективну роботу з такими типами:
1) довгими невід’ємними цілими числами;
2) довільними (додатними і від’ємними) довгими цілими числами ;
3) довільними (додатними і від’ємними) довгими дійсними числами;
Реалізувати набір операцій для роботи з довгими числами:
а) додавання двох довгих чисел;
б) віднімання двох довгих чисел;
в) множення двох довгих чисел;
г) знаходження частки і остачі від ділення двох довгих чисел;
д) переведення довгого числа з представлення в 10 системі числення в системи числення з основами 2, 8, 16;
е) реалізація операцій порівняння (дорівнює, не дорівнює, більше або дорівнює, менше або дорівнює, більше, менше).
Знайти точні значення арифметичних виразів, що представляються довгими числами:
є) обчислення n!, де n > 12;
ж) обчислення nn, де n > 10;
з) обчислення (n!)! , де n > 3;
и) обчислення суми 1! + 2! + 3! + ... + n! , де n > 10;
i) обчислення суми 12 + 22 + 32 + … + n2 , де n > 20000;
ї) обчислення суми 1n + 2n + 3n + ... + nn , де n > 10;
й) обчислення суми дробів для n > 10 :
,
відповідь представити у вигляді нескорочуваного дробу , де P,Q-натуральні числа.
19. Задано деякий додатній правильний періодичний дріб Q і натуральне число N. Числа Q і N такі, що кількість цифр, що використовується для їхнього запису, не перевершує 100. При зображенні дробу Q періодична частина поміщається в круглі дужки. Написати програму, що визначає результат множення Q на N, тобто неперіодичну частину і мінімальний період числа Q*N. У випадку одержання результату множення у вигляді кінцевого дробу дужки опускаються.
Приклад роботи правильної програми:
Введіть періодичний дріб: 0.1(6)
Введіть натуральне число: 2
Відповідь: 0.(3)
20. Ввести послідовність, що складається з N пара символів (ai,bi). Кожна пара визначає порядок слідування символів, наприклад, пара (b,с) означає, що символ "b" передує символу "с". З порядку (b,с) і (с,a) випливає порядок (b,a).
Визначити, чи є введена послідовність:
а) повною, тобто всі використані для формування пар символи (викинувши ті, що повторюються) можна розмістити у вигляді ланцюжка (A1,A2,...,As) у порядку слідування;
б) суперечливою, тобто для деяких символів x і y можна одержати одночасно порядок як (x,y), так і (y,x);
Використання для розв’язання задач динамічної структури даних ”Стек” :
21. Написати програму роботи з інфіксною, префіксною і постфіксною формами запису арифметичних виразів:
а) перетворення виразу із інфіксної формі запису в префіксну форму;
а) перетворення виразу із інфіксної формі запису в постфіксну форму;
б) перетворення виразу із префіксної формі запису в інфіксну з необхідними дужками;
в) перетворення виразу із префіксної формі запису в постфіксну форму;
г) перетворення виразу із постфіксної формі запису в інфіксну з необхідними дужками;
д) перетворення виразу із постфіксної формі запису в префіксну форму;
е) перетворення виразу із інфіксної формі запису в інфіксну форму з вилученням всіх необов’язкових дужок;
є) обчислення виразу, представленого в інфіксній формі запису;
ж) обчислення виразу, представленого в префіксній формі запису;
з) обчислення виразу, представленого в постфіксній формі запису.
22. Написати програму синтаксичного аналізу відповідностей відкриваючих і закриваючих дужок в арифметичному виразі, що має три набори дужок "(" i ")", "<" i ">", "[" i "]". Роздрукувати таблицю відповідностей дужок, причому в таблиці повинно бути зазначено, для яких дужок відсутні парні їм дужки. Для ідентифікації дужок використати їх порядкові номери у виразі.
Приклад: Для арифметичного виразу:
1 2 3 4 5 6
(a+b1)/2+6.5]*{4.8+sin(x)
має бути виведена таблиця виду:
Дужки
відкриваюча закриваюча
1 2
- 3
5 6
4 -
Прочерки в таблиці означають відсутність відповідної дужки.
23. Написати програму, що визначає, чи має символьний рядок, що вводиться, правильну форму виду a D b D c D ... D z , де кожний рядок a, b, c, ..., z має форму рядка виду x C y, де x - рядок, що складається з літер A і B, а y - рядок, обернений до рядка x (наприклад, якщо x = ABABBA, то y повинен дорiвнювати ABBABA). Отже, рядок має правильну форму, якщо він складається з будь-якої кiлькостi подiбних рядків, що роздiленi символом "D". Визначити чи введений рядок правильний.
24. Ця задача відома під назвою "Ханойська вежа" і своїм походженням зобов'язана індуській легенді, яка розповідає, що Принц Шак'я-Муні, якого ще називали Буддою, що означає "просвітлений", під час одної з своїх подорожей заснував у Ханої (В'єтнам) монастир. У головному храмі монастиря Бенареса бронзова плита підтримує три алмазних стержні, на один з яких він нанизав 64 золотих диска. З тих пір день і ніч ченці, змінюючи один одного, щосекунди перекладають по одному диску відповідно до описаних нижче правил. Кінець світу наступить тоді, коли всі 64 диска будуть переміщені. Визначити коли це станеться, якщо Будда заснував монастир у 565 році до Р.Хр.? Як слід перекладати диски?
У загальному вигляді постановка задачі полягає в наступному:
Пірамідка (вежа) складається з N дисків, покладених один на одний так, що чим вище знаходиться диск, тим менший його діаметр. Потрібно перемістити цю вежу, дотримуючи таких правил:
- за один раз можна перекладати тільки один диск;
- не можна класти диск на диск меншого розміру;
- можна користуватись тільки одною резервною площадкою.
Виконання програми доповнити засобами візуалізації на екрані дисплея процесу переміщення дисків.
25. Мажоруючим елементом в послідовності A[1..N] називається елемент, що зустрічається в послідовності більш N/2 разів. В послідовності може бути не більше одного мажоруючого елемента. Визначити, чи є в послідовності мажоруючий елемент, і якщо є, то який.
Приклад: Послідовність 3, 3, 4, 2, 4, 4, 2, 4, 4 має мажоруючий елемент 4, тоді як в послідовності 3, 3, 4, 2, 4, 4, 2, 4 мажоруючого елемента немає.
26. Задано n однакових на вигляд каменів, деякі з яких насправді різні по вазі. Є прилад, що дозволяє по двох каменях визначити, однакові вони чи різні (але не показує, який тяжчий). Відомо, що серед цих каменів більшість (більше n/2) однакових. Зробивши не більше n зважувань, знайти хоча б один камінь з цієї більшості.
27. Написати нерекурсивний варіант програми швидкого сортування.
28. Матриця розміру N*M визначає деякий лабіринт. B матриці елемент 1 означає стіну, а 0 означає вільне місце. В першому рядку матриці визначаються входи x(і), а в останньому виходи y(і), і=1,..,k, що повинні бути нульовими елементами. Рух у лабіринті здійснюється тільки по вертикалі або горизонталі.
Визначити, чи можна :
а) провести людину через лабіринт від заданого входу в лабіринт до заданого виходу;
б) провести k людина від входу x(і) до виходу y(і) відповідно, і=1,..,k, таким чином, щоб кожне вільне місце відвідувалось не більше одного разу;
в) те ж, але людину можна виводити через кожний з виходів.
29. Вводиться два рядки символів x=(a1,a2,...,am) і y=(b1,b2,...,bn). Функція d(x,y) визначається як мінімальне число вставок, вилучень і замін символів, яке необхідно виконати для перетворення рядка x в рядок y. Написати нерекурсивний варіант програми, яка для заданих x і y знаходить d(x,y).
Приклад: d ( ptslddf , tsgldds ) = 3
вилучення p вставка g заміна f
ptslddf---------->tslddf--------->tsglddf-------->tsgldds
30. Фермер хоче побудувати на своїй землі найбільший по площаді сарай. Але на його ділянці є дерева і господарські будівлі, які він не хоче нікуди переносити. Для простоти представимо ферму сіткою розміру M*N. Кожне з дерев і будівель розміщається в одному або декількох вузлах сітки. Знайти максимально можливу площу сараю і де він має розташовуватись.
У загальному вигляді постановка задачі формулюється так:
Вводиться матриця А(m,n) з 0 і 1. Знайти в ній прямокутну підматрицю з одних одиниць максимального розміру (тобто з максимальним добутком висоти на довжину).
Використання для розв’язання задач динамічних структур даних ”Черга” і ”Дек” :
31. У магазині стоїть черга з m покупців. Час обслуговування покупця з черги – це випадкове ціле число в діапазоні від 1 до t1. Час додавання нового покупця до черги - це випадкове ціле число в діапазоні від 1 до t2.
Промоделювати стан черги:
а) вивести повідомлення про час виникнення подій ( обслуговування та додавання покупця ) за період часу T (T >> t1, T >> t2);
б) показати залишок черги;
в) розв’язати задачу, передбачивши, що через випадковий час від 1 до t3 до початку черги додається „пільговий” покупець, який обслуговується першим, а через випадковий час від 1 до t4 не витримує та йде з черги останній покупець.
32. Автостоянка має одну полосу, на якій може бути розмiщено до 10 автомобiлiв. Машини в'їжджають з пiвденного кiнця стоянки i від'їжджають з пiвнiчного. Якщо автомобiль власника, що прийшов на стоянку забрати його, не розташований пiвнiчнiше за всі решту, то всi автомобiлi, що стоять пiвнiчнiше його, виїжджають iз зупинки, потiм виїжджає його машина і всі машини повертаються в початковому порядку. Якщо машина залишає гараж, то всi машини розташованi пiвденнiше, перемiщаються вперед на стiльки позицій, скiльки є вiльних мiсць в пiвнiчнiй частинi. Написати програму зчитування групи рядків, кожний з яких мiстить літеру "A" для прибуття i літеру "D" для вiдправлення, а також номер машини. Машини прибувають i вiдправляються в порядку, що задає цей список рядків. Програма має видавати повiдомлення при кожному прибутті або вiдправленні машини. При прибутті машини в ньому повинно говоритись, чи є на стоянці вiльне мiсце. Якщо вiльне мiсце вiдсутнє, машина чекає до тих пiр, поки воно не звiльниться, або до моменту зчитування рядка, що повідомляє про вiдправлення цього автомобiля. Якщо з'являється вiльне мiсце, повинно видаватись iнше повiдомлення. При вiдправленнi автомобiля повiдомлення повинно мiстити в собi кiлькiсть перемiщень машини в серединi стоянки (включаючи її вiдправлення, але не прибуття; це число рiвне 0, якщо машина була вiдправлена під час очiкування вільного місця).
33. Написати програму, що моделює обчислювальну систему з кiлькома користувачами. Кожен користувач має свiй унiкальний iдетифiкацiйний номер ID i бажає виконати на ЕОМ ряд операцiй. У будь-який момент часу ЕОМ може виконувати одночасно тiльки одну операцiю. Кожний вхiдний рядок вiдповiдає одному користувачу i мiстить його ID, за яким йде початок роботи, а за ним - набiр цiлих чисел, кожне з яких представляє тривалість кожної з виконуваних користувачем операцiй. Вхiднi данi впорядкованi по зростанню часу початку роботи. Весь час задається в секундах. Вважається, що користувач не видає запрос на проведення наступної операцiї до тих пiр, поки не закiнчилось виконання попередньої, а ЕОМ виконує операцiї за принципом "перший, що поступив, обслуговується першим". Програма повинна iмiтувати роботу системи i виводити повiдомлення, що мiстять ID користувача i час початку i закiнчення проведення операцiї. В кiнцi процесу моделювання вивести середній час очiкування для кожної операцiї. Час очiкування - це рiзниця мiж тим часом, коли був виданий запрос на виконання операцiї, i початком її виконання.
34. Фiрма KRESS по зберiганню i збуту побутової техніки отримує вантажi з товарами по рiзним цiнам. Пізніше фiрма продає ці товари з 20-% надбавкою, причому товари, що отриманi раніше, продаються у першу чергу (стратегiя "перший отриманий - продається першим"). Товари з першої партії грузів продаються по ціні, на 20% вищій ніж закупочна. Після того як вся перша партія повністю розпродана, приступають до продажі другої партії, також по збільшеній на 20% цені, і т.д.
Написати програму, яка зчитує з текстового файлу записи про торговi операцiї двох типiв: операцiї по закупцi i операцiї по продажу. Запис про продажу мiстить префiкс "Р", після якого йде кiлькiсть товару, що продається. Запис про закупку мiстить префiкс "Z" , кiлькiсть товару і вартiсть всієї партiї. Пiсля зчитування запису про закупку товару виводити повідомлення про кiлькiсть товару, вартiсть одиниці товару i загальну вартiсть всiєї партiї. Пiсля зчитування запису про операцiю продажу товару виводити повідомлення про кiлькiсть товару, продану з кожної партії, цiну, по якiй був проданий кожний товар, суму, на яку були продані товари з кожної партії, а також загальну суму проданого товару, середню ціну одиниці товару і суму отриманого прибутку. Якщо кiлькiсть товару що є на складi недостатня для виконання замовлення на продаж товару, то продати всi товари зі складу і вивести повідомлення: "ХХХ одиниць товару немає на складi".
Приклад: Якщо фiрма продала 200 одиниць товару, в які входили 70 одиниць з закупочною цiною 125 грн., 100 одиниць з закупочною цiною 110 грн. i 30 одиниць з закупочною цiною 100 грн., то надрукувати (згадайте про 20-% надбавку) таку послідовність повідомлень:
Фiрма KRESS продала 200 виробiв:
70 штук по ціні 150 грн. на суму 10500 грн.
100 штук по ціні 132 грн. на суму 13200 грн.
30 штук по ціні 180 грн. на суму 5400 грн.
Всього продано товарів на суму 29100 грн. за ціною 145,5 грн. кожний.
Отримано прибутку на суму 6350 грн.
35. У місті розташовано n автобусних зупинок, позначених числами з N={1,2,....,n}. В текстовому файлі записано k автобусних маршрутів, заданих послідовностями сусідніх зупинок при русі автобуса в одному напрямку:
М1={P11,P12,...,P1m1},
М2={P21,P22,...,P2m2},
.....
Mk={Pk1,Pk2,...,Pkmk}, де Pij натуральне число з N.
Написати програму, що по заданих номерах зупинок I і J визначає найбільш швидкий шлях переміщення пасажира з зупинки I у зупинку J з використанням наявних маршрутів автобусів при умові, що час руху між сусідніми зупинками у всіх маршрутах однаковий і у 3 рази менший за час зміни маршруту. Автобуси можуть рухатись в обох напрямках.
36. Надрукувати в порядку зростання перші n натуральних чисел, у розклад яких на прості множники входять тільки числа 2, 3, 5.
Використання для розв’язання задач динамічної структури даних ”Дерево” :
37. Операційні системи типу UNIX, PC-DOS (старші версії) підтримують деревоподібну структуру збереження даних на диску. При цьому мінімальна іменована одиниця інформації називається файлом. Файли об'єднуються в каталоги, кожний з яких теж має ім'я. Множина каталогів і окремих файлів можуть у свою чергу також утворити каталог більш високого рівня. Каталог найвищого рівня називається кореневим. Кількість рівнів вкладеності не обмежена. Розглядати тільки випадки без порожніх каталогів (тобто каталогів, що не мають файлів).
Скласти програму для виводу на екран по рівнях:
а) списку всіх елементів даних, "вкладених" у довільний каталог на всіх рівнях;
б) списку всіх каталогів, "вкладених" у довільний каталог;
в) списку всіх файлів, "вкладених" у довільний каталог;
г) списку всіх елементів даних кореневого каталогу, виведених в алфавітному порядку.
Приклад:
На заданій схемі елемент 0 є кореневим каталогом диску;
елементи 2,3,6,10 - каталогами; елементи 1,4,7,9,8,5 - файлами.
Для каталогу 2 перше завдання має виводити таку послідовність:
2
6
4
7
9
Примітка: для всіх завдань замість номерів використовувати імена (текстові значення).
38. Глосарій або предметний покажчик підручника складається з впорядкованих по алфавіту основних термінів, кожен з яких супроводжується впорядкованою за зростанням послідовністю номерів сторінок, де він зустрічається, і множиною підтермінів. Підтерміни виводяться на наступних за основним терміном рядках, вони дещо зсунуті вправо відносно основного терміна і впорядковані по алфавіту всередині основного терміна. Кожен підтермін супроводжується впорядкованою за зростанням послідовністю номерів сторінок, де він зустрічається.
Розробити структуру даних для представлення такого предметного покажчика і написати програму для зображення предметного покажчика по вхідних даних, що зберігаються у текстовому файлі.
Кожний вхідний рядок починається або з символу М (основний термін), або з символу S (підтермін). Рядок з символом М містить основний термін, за котрим слідують номери сторінок, на котрих зустрічається основний термін. Рядок з символом S будується аналогічно, за винятком того, що він містить не основний термін, а підтермін. Вхідні рядки з’являються у будь-якому порядку. Єдина умова: кожен підтермін вважається підтерміном найближчого попереднього основного терміна. Для одного основного терміна або підтерміна може бути декілька вхідних рядків (всі номери сторінок, що з’являються для конкретного терміна у будь-якому рядку, повинні бути надруковані разом з цим терміном).
39. В зовнішньому текстовому файлі записано програму на мові Паскаль. Відомо, що в цій програмі є ідентифікатори, кожний з яких містить не більше 9 латинських літер і/або цифр. Надрукувати в алфавітному порядку всі різні ідентифікатори цієї програми, вказавши для кожного з них число його входжень в текст програми (врахувати, що великі і малі букви ототожнюються, текст в середині коментарів не враховується, в записі дійсних чисел може зустрічатися літера Е або е ).
40. У деякій країні поліція виявила розгалужену мережу опозиційної партії. Партія сильно законспірована і складається з рядових членів і керівників різних рівнів. На чолі партії стоїть один головний керівник - лідер партії. Всі члени партії пронумеровані від 1 до N. Кожний член партії знає тільки свого безпосереднього керівника (рівно одного) і своїх безпосередніх підлеглих (керівник не знає підлеглих свого підлеглого і навпаки). До початку арештів наказ лідера може бути до...
Ділись своїми роботами та отримуй миттєві бонуси!
0%
Оголошення від адміністратора