Подякувати Студентському архіву довільною сумою
Admin
26.02.2023 12:38
Дякуємо, що користуєтесь нашим архівом!
Динамічні структури даних
Інформація про навчальний заклад
ВУЗ:
Національний університет Львівська політехніка
Інститут:
Не вказано
Факультет:
Комп'ютерна інженерія
Кафедра:
Кафедра ЕОМ
Інформація про роботу
Рік:
2012
Тип роботи:
Методичні вказівки до курсової роботи
Предмет:
Програмування
Частина тексту файла (без зображень, графіків і формул):
МІНІСТЕРСТВО ОСВІТИ І НАУКИ УКРАЇНИ
НАЦІОНАЛЬНИЙ УНІВЕРСИТЕТ “ЛЬВІВСЬКА ПОЛІТЕХНІКА”
Кафедра ЕОМ
МЕТОДИЧНІ ВКАЗІВКИ
до курсової роботи (частина 2)
на тему
"Динамічні структури даних"
з дисципліни
"Програмування"
для студентів напряму
6.050102 “Комп’ютерна інженерія”
Львів – 2012
Методичні вказівки до курсової роботи на тему "Програмування" з дисципліни “Програмування" для підготовки студентів напряму 6.050102 “Комп’ютерна інженерія” / Укл. Т.А. Матвейчук – Львів: Видавництво НУ “Львівська політехніка”, 2012 – 14 с.
Укладач: Матвейчук Т.А., ст. викладач каф.ЕОМ
Відповідальний
за випуск: Мельник А.О., д-р техн. наук, проф.
Рецензенти: Мороз І.В., ст. викладач каф.ЕОМ
Юрчак І.Ю., доцент кафедри САПР, к.т.н.
1. МЕТА РОБОТИ
Вивчити побудову та застосування до розв’язання прикладних задач динамічних структур даних.
2. ВИМОГИ ДО ПОРЯДКУ ВИКОНАННЯ ТА ОФОРМЛЕННЯ
КУРСОВОЇ РОБОТИ
Індивідуальні завдання на курсову роботу вибираються студентом самостійно згідно з його анкетними даними. Можливі їх корегування керівником під час виконання роботи.
Виконуючи курсову роботу студент повинен розробити, відлагодити та протестувати програму на мові С++ (або іншій, узгодивши із керівником курсової роботи) та оформити звіт.
2.1. Вимоги до оформлення програмного продукта
Роздруківки програм з необхідними коментарями виносяться в додатки. При цьому назви програмних блоків у тексті записки й відповідних фрагментів програм у додатках повинні бути однаковими.
Для оформлення роздруківки тексту програми рекомендується використовувати шрифт гарнітури Courier розміром 10 або 12. Допустиме шрифтове виділення службових слів і синтаксичних конструкцій мови програмування. Текст програми оформляється відповідно до загальноприйнятих норм оформления:
Кількість операторів в рядку повинна дорівнювати 1.
Всі оператори, що входять у складений оператор, повинні бути зміщені вправо на однакову кількість позицій, "Драбинка" повинна відображати структурну вкладеність мовних конструкцій. Рекомендується відступ не менше 2-х і не більше 8-і пробілів. Прийнятого відступу потрібно дотримуватись у всьому тексті програми.
Операторні дужки (тобто те, що обмежує складений оператор), що відносяться до одного блоку, повинні розташовуватися в такий спосіб: відкриваюча дужка повинна знаходитись на тому ж рядку, що й оператор, який відкриває блок, а закриваюча повинна знаходитись в тому ж стовпчику, з якого починається оператор, що відкриває блок. Допускається розташовувати відкриваючу дужку на рядку, що іде за оператором, що відкриває блок, у тому ж стовпчику, з якого починається цей оператор.
Рядок вихідного тексту програми повинен цілком розташовуватись в одному типографському рядку (до 80 символів залежно від шрифту). Недотримання цього правила говорить про занадто велику вкладеність блоків, що означає невдалий алгоритм або структуру програми. У такому випадку рекомендується переосмислити структуру програми, ввести додаткові функції, замінивши якісь більші частини коду їхніми викликами, переробити алгоритм і т.п.
Якщо синтаксис мови дозволяє, бажано відокремлювати знаки операцій пробілами від операндів. Як і у звичайному тексті, після ком повинен випливати пробіл.
Визначення функцій або логічні частини програми варто відокремлювати одна від одної порожніми рядками.
Ідентифікатори (назви змінних, типів, підпрограм) повинні бути значимими настільки, щоб читаючий текст програми міг розуміти їхній зміст без присутності поруч автора. При необхідності оголошення змінної або типу може супроводжуватися коментарем. Ідентифікатори рекомендується підбирати зі слів англійської мови.
Текст програми повинен містити коментарі, що відображають функціональне призначення того або іншого блоку програми, структуру програми. Коментарі варто писати українською мовою й по суті так, щоб програміст, що не брав участь у розробці програми (але має досвід роботи мовою С++), міг без особливих проблем розібратися в логіці програми.
Для кожної користувацької функції повинна бути описана у вигляді коментаря специфікація, що містить наступну інформацію:
призначення функції;
опис семантики параметрів, переданих у функцію, якщо вона неочевидна;
опис семантики значення, що повертається, якщо воно неочевидно.
2.2. Вимоги до оформлення звіту
Пояснювальна записка має бути написана українською мовою. Вона може бути надрукована або написана від руки. В обох випадках текст має розміщуватись на одному боці аркуша паперу формату А4. Рекомендується розміщувати до 30 рядків на сторінці, використовувати шрифт гарнітури Times New Roman розміром 12.
На аркушах необхідно залишити поля з усіх чотирьох боків. Розмір лівого поля - 25 мм, правого - не менше 10 мм, верхнього і нижнього - не менше 20 мм.
На аркушах, де починаються розділи, зміст, вступ, висновки, список літератури (всі ці пункти мають починатись з нової сторінки) рекомендується збільшувати розмір верхнього поля до 40 мм.
Чорнило, яким виконується робота, має бути чорним, фіолетовим чи синім .
Звіт має бути стислим, чітким, лаконічним і містити лише інформацію, яка має пряме відношення до курсової роботи.
2.3. Зміст звіту
I. Оформити титульну сторінку звіту стандартного зразка, на якій обов’язково показати процес знаходження номерів варіантів індивідуальних завдань.
II. В звіті мають бути відображені наступні пункти:
ЗАВДАННЯ НА КУРСОВУ РОБОТУ
ЗМІСТ
1. ТЕОРЕТИЧНА ЧАСТИНА
2. ЗАВДАННЯ 3. ПОБУДОВА АТД
2.1. Постановка задачі
2.2. Динаміка вмісту
2.3. Результати виконання програми
3. ЗАВДАННЯ 4. ЗАСТОСУВАННЯ АТД
3.1. Постановка задачі
3.2. Алгоритм розв’язання задачі
3.2.1. Словесний опис алгоритму
3.2.2. Граф-схема алгоритму
3.3. Результати виконання програми
ВИСНОВКИ
СПИСОК ЛІТЕРАТУРИ
ДОДАТОК А. ТЕКСТ ПРОГРАМИ ДО ЗАВДАННЯ 3
ДОДАТОК Б. ТЕКСТ ПРОГРАМИ ДО ЗАВДАННЯ 4
IIІ. Змістовне наповнення пунктів.
Завдання на курсову роботу має містити індивідуальні завдання зі своїми конкретними значеннями (без знаходження номерів варіантів індивідуальних завдань).
Зміст має містити розгорнутий перелік всіх розділів, які знаходяться в роботі після змісту, з обов’язковою вказівкою номерів сторінок, де вони розташовані в роботі. Нумерація сторінок має бути наскрізною: першою сторінкою є титульна сторінка, другою – завдання і т.д. Номер сторінки проставляється у верхньому правому куті. На сторінках 1 (титульна сторінка), 2 (завдання) номер сторінки не пишеться. Список літератури та додатки потрібно включати у загальну нумерацію.
В теоретичній частині (обсягом 4 – 6 сторінок) мають наводитись основні теоретичні відомості, які необхідні для розробки алгоритму.
Постановка задачі має містити повне завдання, тобто спільне завдання для всіх варіантів і індивідуальне завдання для свого вибраного варіанту.
В пункті динаміка вмісту АТД схематичне зображення АТД має відповідати умові індивідуального завдання.
В пункті алгоритм розв’язання задачі (обсягом 2 – 4 сторінки) надається словесний опис основних прийомів, що використовуються для знаходження алгоритму і написання програми, та граф-схема алгоритму.
В пункті результати виконання програми показуються роздруковані копії екранів з результатами, які відображають всі зміни, що відбуваються в АТД та містять всю необхідну інформацію в такому вигляді, щоб для перевірки правильності виконання програми не виникало необхідності додатково переглядати тексти програм. Обов’язково показати всі можливі варіанти розгалуження алгоритму.
Висновки розміщують у звіті починаючи з нового аркуша. У висновках наводяться найважливіші теоретичні та практичні результати, які отримані в роботі.
Список літератури розміщують у звіті, починаючи з аркуша, наступного після закінчення висновків.
В додатках розміщуються тексти програм з коментарями. Кожен додаток повинен починатися з нової сторінки. Додаток повинен мати заголовок, надрукований вгорі малими літерами з першої великої симетрично відносно тексту сторінки. Посередині рядка над заголовком малими літерами з першої великої друкується слово "Додаток" та велика літера, що позначає додаток. Додатки слід позначати послідовно великими літерами української абетки, за винятком літер Г, Є, І, Ї, Й, О, Ч, Ь, наприклад, "Додаток А", "Додаток Б" і т.д. Один додаток позначається як "Додаток А". Текст кожного додатка за необхідності може бути поділений на розділи й підрозділи, які нумерують у межах кожного додатка. У цьому разі перед кожним номером ставлять позначення додатка (літеру) і крапку, наприклад. А.2 - другий розділ додатка А; В.3.1 – перший підрозділ третього розділу додатка В.
3. ВАРІАНТИ ЗАВДАНЬ
3.1. Завдання 3. Побудова АТД
Змоделювати абстрактний тип даних (АТД) , який використати в Завданні 4. Оформити АТД у вигляді класа. Переписати основні операції роботи з АТД і продемонструвати їх застосування при додаванні та вилученні елементів з АТД.
3.2. Завдання 4. Застосування АТД
3.2.1. Застосування АТД "СТЕК" до розв’язання прикладних задач
1. Перетворити вираз з інфіксної форми запису в префіксну.
Вказівки до розв’язання задачі: При перетворенні інфіксний рядок зчитуйте справа наліво і префіксний рядок створюйте також справа наліво. В стеку зберігати операції з однаковим пріоритетом.
2. Перетворити вираз з інфіксної форми запису без дужок в постфіксну форму.
3. Перетворити вираз з інфіксної форми запису з дужками в постфіксну форму.
4. Обчислити вираз, представлений в інфіксній формі запису.
Вказівки до розв’язання задачі: При обчисленні виразу, представленого в інфіксній формі застусовуйте два стеки – один для операндів, другий для операторів.
5. Обчислити вираз, представлений в постфіксній формі запису.
6. Перевірити баланс дужок в арифметичному виразі, який містить тільки один тип дужок – круглі.
7. Написати програму синтаксичного аналізу відповідностей відкриваючих і закриваючих дужок в арифметичному виразі, що має три набори дужок "(" i ")", "<" i ">", "[" i "]". Роздрукувати таблицю відповідностей дужок, причому в таблиці повинно бути зазначено, для яких дужок відсутні парні їм дужки. Для ідентифікації дужок використати їх порядкові номери у виразі.
Приклад: Для арифметичного виразу:
1 2 3 4 5 6
(a+b1)/2+6.5]*{4.8+sin(x)
має бути виведена таблиця виду:
Дужки
відкриваюча закриваюча
1 2
- 3
5 6
4 -
Прочерки в таблиці означають відсутність відповідної дужки.
8. Написати програму, що визначає, чи має символьний рядок, що вводиться з клавіатури, правильну форму виду a D b D c D ... D z , де кожний рядок a, b, c, ..., z називається подібним і має форму виду x C y, де x - рядок, що складається з літер A і B, а y - рядок, обернений до рядка x (наприклад, якщо x = AАBABB, то y повинен дорiвнювати BBABАA). Отже, рядок має правильну форму, якщо він складається з будь-якої кiлькостi подiбних рядків, що роздiленi символом D. Визначити чи введений рядок є правильним.
9. Мажоруючим елементом в послідовності A[1..N] називається елемент, що зустрічається в послідовності більше ніж N/2 разів. В послідовності може бути не більше одного мажоруючого елемента. Визначити, чи є в послідовності мажоруючий елемент, і якщо є, то який.
Приклад: Послідовність 3, 3, 4, 2, 4, 4, 2, 4, 4 має мажоруючий елемент 4, тоді як в послідовності 3, 3, 4, 2, 4, 4, 2, 4 мажоруючого елемента немає.
Вказівки до розв’язання задачі: Створіть стек і додавайте або вилучайте зі стеку елементи за таким правилом:
на першому кроці покладіть в стек A[1];
на i-ом кроці (i=2, ..., N) повторіть такі дії:
якщо стек порожній, то покладіть в нього A[і]; інакше, якщо елемент A[і] співпадає з елементом, що знаходиться у вершині стеку, то додайте A[і] в стек; інакше вилучіть один елемент з вершини стеку.
Якщо стек не буде порожнім, то в ньому залишаться лише співпадаючі елементи. Якщо в послідовності є мажоруючий елемент, те він і залишиться в стеку після N-го кроку. Для перевірки (у випадку не порожнього стеку після виконання N-го кроку) чи є елемент у стеку мажоруючим (якщо в стеку більше одного елемента, то вони всі однакові), перегляньте послідовність ще раз і підрахуйте, скільки раз зустрічається в ній елемент, що залишився в стеку. Якщо це число більше N/2, то цей елемент є мажоруючим, інакше - мажоруючого елемента в послідовності немає.
10. Задано n однакових на вигляд каменців, деякі з яких насправді різні по вазі. Є прилад, що дозволяє для двох каменців визначити, однакові вони чи різні (але не показує, який тяжчий). Відомо, що серед цих каменців більшість (більше n/2) однакових. Зробивши не більше n зважувань, знайти хоча б один камінець з цієї більшості.
Вказівки до розв’язання задачі: Дивіться вказівки до попередньої задачі.
3.2.2. Застосування АТД " ЧЕРГА " до розв’язання прикладних задач
1. У магазині стоїть черга з m покупців. Час обслуговування покупця з черги – це випадкове ціле число в діапазоні від 1 до t1. Час додавання нового покупця до черги - це випадкове ціле число в діапазоні від 1 до t2.
Промоделювати стан черги:
а) вивести повідомлення про час виникнення подій ( обслуговування та додавання покупця ) за період часу T (T >> t1, T >> t2);
б) показати залишок черги;
в) розв’язати задачу, передбачивши, що через випадковий час від 1 до t3 до початку черги додається „пільговий” покупець, який обслуговується першим, а через випадковий час від 1 до t4 не витримує та йде з черги останній покупець.
2. Автостоянка має одну полосу, на якій може бути розм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кування вільного місця).
3. Написати програму, що моделює обчислювальну систему з к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 початком її виконання.
4. Ф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 грн.
5. У місті розташовано 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 рази менший за час зміни маршруту. Автобуси можуть рухатись в обох напрямках.
Вказівки до розв’язання задачі: Ідея рішення грунтується на використанні черг. Для кожної зупинки введіть трійку чисел (О,М,Z), де О - номер зупинки, М - номер маршруту, Z - величина затримки. При виборі чергового елемента з черги можливі дві ситуації:
1). Продовжується рух по тому ж маршруту. У цьому випадку в чергу занесіть трійки типу (О',М,Z), де О' - номер зупинки, сусідньої з О, у маршруті М, Z=0.
2). Змінюється маршрут. У цьому випадку в чергу занесіть трійки типу (О,М',Z), де М' - номер зміненого маршруту, Z=3 (затримка на пересадку).
Всі нові трійки породжуються тільки трійками з затримкою, рівною 0. У випадку трійки з ненульовою затримкою занесіть її знову в чергу зі зменшеним на 1 значенням затримки.
6. Надрукувати в порядку зростання перші n натуральних чисел, у розклад яких на прості множники входять тільки числа 2, 3, 5.
Вказівки до розв’язання задачі: Введіть три черги x2, x3, x5, у яких зберігайте елементи, що відповідно в 2, 3, 5 разів більше надрукованих, але ще не надруковані. Найменший з ненадрукованих елементів, нехай це x, ділиться націло на одне з чисел 2, 3, 5. x знаходиться в одній з черг і є в ній першим (менші надруковані, а елементи черг не надруковані). Надрукуйте x, вилучіть його і додайте його кратні. Довжини черг не перевищують числа надрукованих елементів.
7. Дано позначення двох полів шахівниці (наприклад, A5 і C2). Знайти мінімальне число ходів, які потрібні шаховому коневі для переходу з першого поля на друге.
Вказівки до розв’язання задачі: Ідея рішення ґрунтується на використанні черги. Спочатку в чергу міститься елемент, що визначає вихідне положення шахового коня, а відповідна клітка поля позначається як така, яку відвідали.
На кожному з наступних кроків алгоритму (поки черга не порожня або не позначена кінцева клітка) виконуються наступні дії.
Із черги вилучається черговий елемент, що визначає деяку позицію (x,y).
Знаходяться клітки в межах поля, які досяжні з (x,y) одним ходом шахового коня, і які ще не позначені.
Елементи, що відповідають знайденим кліткам, додаються в чергу, а клітки позначаються як такі, яких відвідали.
При цьому спочатку всі клітки повинні бути непозначені, а мітку бажано ставити таку, щоб можна було відновити шлях між полями. Для цього мітку поля можна визначити як позицію поля, з якої вона була позначена.
8. У магазині стоїть черга з m покупців. Час обслуговування покупця з черги – це випадкове ціле число в діапазоні від 1 до t1. Час додавання нового покупця до черги - це випадкове ціле число в діапазоні від 1 до t2. Промоделювати стан черги. Вивести повідомлення про час виникнення подій ( обслуго-вування та додавання покупця ) за період часу T (T >> t1, T >> t2).
9. У магазині стоїть черга з m покупців. Час обслуговування покупця з черги – це випадкове ціле число в діапазоні від 1 до t1. Час додавання нового покупця до черги - це випадкове ціле число
в діапазоні від 1 до t2. Промоделювати стан черги. Показати залишок черги.
10. У магазині стоїть черга з m покупців. Час обслуговування покупця з черги – це випадкове ціле число в діапазоні від 1 до t1. Час додавання нового покупця до черги - це випадкове ціле число в діапазоні від 1 до t2. Промоделювати стан черги. Розв’язати задачу, передбачивши, що через випадковий час від 1 до t3 до початку черги додається „пільговий” покупець, який обслуговується першим, а через випадковий час від 1 до t4 не витримує та йде з черги останній покупець.
3.2.3. Застосування АТД " СПИСОК " до розв’язання прикладних задач
1. Многочлен виду , де представити у вигляді зв’язаного списку в якому кожний вузол має три поля: одне – для коефіцієнта Сi , друге – для показника степеня ni , третє – для вказівника на наступний вузол списку. Для описаного представлення многочленів програмно реалізувати таку операцію:
Додавання двох многочленів.
2. Многочлен виду , де представити у вигляді зв’язаного списку в якому кожний вузол має три поля: одне – для
коефіцієнта Сi , друге – для показника степеня ni , третє – для вказівника на наступний вузол списку. Для описаного представлення многочленів програмно реалізувати таку операцію:
Множення многочлена на одночлен.
3. Многочлен виду , де представити у вигляді зв’язаного списку в якому кожний вузол має три поля: одне – для коефіцієнта Сi , друге – для показника степеня ni , третє – для вказівника на наступний вузол списку. Для описаного представлення многочленів програмно реалізувати таку операцію:
Диференціювання многочлена.
4. Поліном від трьох змінних ( X , Y , Z ) представити у вигляді циклічного списку, в якому кожний вузол має п’ять полів: одне – для коефіцієнта члена поліному , друге – для показника степеня змінної X , третє – для показника степеня змінної Y, четверте – для показника степеня змінної Z, п’яте – для вказівника на наступний вузол списку. Елементи списку мають бути впорядковані спочатку по зменшенню степеня Х, пізніше по зменшенню степеня Y, а після цього по зменшенню степеня Z. Структура збереження поліномів повинна забезпечувати ефективне виконання такої операції над ними:
Додавання двох поліномів.
5. Поліном від трьох змінних ( X , Y , Z ) представити у вигляді циклічного списку, в якому кожний вузол має п’ять полів: одне – для коефіцієнта члена поліному , друге – для показника степеня змінної X , третє – для показника степеня змінної Y, четверте – для показника степеня змінної Z, п’яте – для вказівника на наступний вузол списку. Елементи списку мають бути впорядковані спочатку по зменшенню степеня Х, пізніше по зменшенню степеня Y, а після цього по зменшенню степеня Z. Структура збереження поліномів повинна забезпечувати ефективне виконання такої операції над ними:
Обчислення полінома по заданим значенням X , Y , Z .
6. Написати програму для роботи з розрідженими матрицями, представленими у вигляді зв’язаних списків:
Транспонування розрідженої матриці.
7. Написати програму для роботи з розрідженими матрицями, представленими у вигляді зв’язаних списків:
Додавання двох матриць.
8. Написати програму роботи з довгими числами (довгі числа – це числа, що виходять за діапазон допустимих значень будь-якого стандартного цілого або дійсного типу). Структура збереження довгих чисел повинна забезпечувати ефективну роботу з довільними (додатними і від’ємними) довгими цілими числами. Реалізувати роботу з довгими числами:
Додавання двох довгих чисел.
9. Написати програму роботи з довгими числами (довгі числа – це числа, що виходять за діапазон допустимих значень будь-якого стандартного цілого або дійсного типу). Структура збереження довгих чисел повинна забезпечувати ефективну роботу з довільними (додатними і від’ємними) довгими цілими числами. Реалізувати роботу з довгими числами:
Порівняння двох довгих чисел (дорівнює, не дорівнює, більше, менше).
10. Написати програму роботи з довгими числами (довгі числа – це числа, що виходять за діапазон допустимих значень будь-якого стандартного цілого або дійсного типу). Структура збереження довгих чисел повинна забезпечувати ефективну роботу з довільними (додатними і від’ємними) довгими цілими числами. Реалізувати роботу з довгими числами:
Обчислення значення n!, де n > 12.
3.2.4. Застосування АТД " ДЕРЕВО " до розв’язання прикладних задач
4.1. Операційні системи типу UNIX, PC-DOS (старші версії) підтримують деревоподібну структуру збереження даних на диску. При цьому мінімальна іменована одиниця інформації називається файлом. Файли об'єднуються в каталоги, кожний з яких теж має ім'я. Множина каталогів і окремих файлів можуть у свою чергу також утворити каталог більш високого рівня. Каталог найвищого рівня називається кореневим. Кількість рівнів вкладеності не обмежена. Розглядати тільки випадки без порожніх каталогів (тобто каталогів, що не мають файлів).
Скласти програму для виводу на екран по рівнях:
а) списку всіх елементів даних, "вкладених" у довільний каталог на всіх рівнях;
б) списку всіх каталогів, "вкладених" у довільний каталог;
в) списку всіх файлів, "вкладених" у довільний каталог;
г) списку всіх елементів даних кореневого каталогу, виведених в алфавітному порядку.
Приклад:
На заданій схемі елемент 0 є кореневим каталогом диску;
елементи 2,3,6,10 - каталогами; елементи 1,4,7,9,8,5 - файлами.
Для каталогу 2 перше завдання має виводити таку послідовність:
2
6
4
7
9
Примітка: для всіх завдань замість номерів використовувати імена (текстові значення).
4.2. Глосарій або предметний покажчик підручника складається з впорядкованих по алфавіту основних термінів, кожен з яких супроводжується впорядкованою за зростанням послідовністю номерів сторінок, де він зустрічається, і множиною підтермінів. Підтерміни виводяться на наступних за основним терміном рядках, вони дещо зсунуті вправо відносно основного терміна і впорядковані по алфавіту всередині основного терміна. Кожен підтермін супроводжується впорядкованою за зростанням послідовністю номерів сторінок, де він зустрічається.
Розробити структуру даних для представлення такого предметного покажчика і написати програму для зображення предметного покажчика по вхідних даних, що зберігаються у текстовому файлі.
Кожний вхідний рядок починається або з символу М (основний термін), або з символу S (підтермін). Рядок з символом М містить основний термін, за котрим слідують номери сторінок, на котрих зустрічається основний термін. Рядок з символом S будується аналогічно, за винятком того, що він містить не основний термін, а підтермін. Вхідні рядки з’являються у будь-якому порядку. Єдина умова: кожен підтермін вважається підтерміном найближчого попереднього основного терміна. Для одного основного терміна або підтерміна може бути декілька вхідних рядків (всі номери сторінок, що з’являються для конкретного терміна у будь-якому рядку, повинні бути надруковані разом з цим терміном).
4.3. В зовнішньому текстовому файлі записано програму на мові Паскаль. Відомо, що в цій програмі є ідентифікатори, кожний з яких містить не більше 9 латинських літер і/або цифр. Надрукувати в алфавітному порядку всі різні ідентифікатори цієї програми, вказавши для кожного з них число його входжень в текст програми (врахувати, що великі і малі букви ототожнюються, текст в середині коментарів не враховується, в записі дійсних чисел може зустрічатися літера Е або е ).
4.4. У деякій країні поліція виявила розгалужену мережу опозиційної партії. Партія сильно законспірована і складається з рядових членів і керівників різних рівнів. На чолі партії стоїть один головний керівник - лідер партії. Всі члени партії пронумеровані від 1 до N. Кожний член партії знає тільки свого безпосереднього керівника (рівно одного) і своїх безпосередніх підлеглих (керівник не знає підлеглих свого підлеглого і навпаки). До початку арештів наказ лідера може бути доведений до будь-якого члена партії. З початком арештів членів партії вона розпадеться на дрібні, не зв'язані один з одним групи. Поліцмейстер запевняє, що група, що складається з менш ніж K членів партії, ідеологічно вироджується і не становить погрози для держави. Прагнучи не упустити престиж країни в очах світової суспільної думки, поліцмейстер поставив задачу зробити мінімальну кількість арештів членів партії так, щоб від неї залишилися тільки маленькі групи.
Написати програму, яка б по вхідним даним, що знаходяться в текстовому файлі, описувала структуру підпільної партії і виводила кількість арештів і номери членів партії, яких потрібно заарештувати. При наявності декількох розв'язків вивести одне з них.
4.5. Написати програму реалізації гри Го-Моку. Це нескладна позиційна гра, яка відома зі стародавніх часів і, напевно, вперше виникла у Японії. Ця гра схожа на хрестики-нолики, але набагато цікавіша. За класичними правилами грають на дошці розміром 19x19 клітин (в програмі реалізуйте альтернативні варіанти: скорочений 9x9 та розширений 29x29 клітин). Гравці ставлять свої фішки на вільні клітини дошки по черзі. Виграє той, кому першому пощастить побудувати власну лінійку з п’яти фішок – горизонтальну, вертикальну або діагональну.
4.6. Задано рядок символів S і набір слів А[1], ..., A[k]. Написати програму розбиття рядка S на слова з набору всіма можливими способами.
Приклад: Вхідні дані Результат розбиття
S=ABBC S = A - B - BC
A[1]=A, S = A - BBC
A[2]=AB, S = AB - BC
A[3]=BC,
A[4]=BBC,
A[5]=H,
A[6]=B
4.7. N кісточок доміно за правилами гри викладаються в прямий ланцюжок, починаючи з кісточки, обраної довільним чином, в обидва кінці доти, поки це можливо. Змоделювати гру в доміно і написати програму
а) побудови самого довгого ланцюжка;
б) знаходження такого варіанта викладання кісточок, при якому до моменту, коли ланцюжок не можна далі продовжити, "на руках" залишиться максимальне число очок.
Приклад: Вхідні дані Результат
N= 5 5
1 2 56:62:21:13:36
1 3
2 6
3 6
5 6
4.8. Нехай задано n чоловіків і n жінок, та два n x n масиви P i Q таких, що P(і, j) вказує на надання переваги і-тим чоловіком j-тої жінки, а Q(i, j) – надання переваги і-тою жінкою j-го чоловіка. Написати програму знаходження таких паросполук чоловіків та жінок , щоб оптимізувати переваги.
4.9. Проблема призначення формулюється так: є n людей, що призначаються на n робіт. Вартість призначення i-людини до j-роботи - COST(i, j). Розробити алгоритм і написати програму, яка призначає кожній людині роботу, при мінімальній загальній вартості призначення.
4.10. Задано n завдань для виконання, але тільки k процесорів,
25.01.2013 01:01-
Ділись своїми роботами та отримуй миттєві бонуси!
0%
Оголошення від адміністратора