3. Порядок виконання роботи

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

2. Згідно з індивідуальним завданням розробити алгоритм розв’язання задачі.

3. Підготувати програмну реалізацію розробленого алгоритму. Засобами вбудованого тексто-вого редактора інтегрованого середовища набрати текст підготовленої програми. Відкомпілювати, налагодити та виконати програму.

4. Протестувати програму згідно зі складеною системою тестів і, при потребі, підкоректувати текст програми. Проаналізувати отримані результати.

5. Написати контрольне опитування по темі.

6. Оформити звіт по роботі.

Без підготовкі до роботи (програмної реалізації розробленого алгоритму) студент до роботи не допускається.

4. Завдання на лабораторну роботу

4.1. Вибір варіанта індивідуального завдання

№ варіанта = [(день народження) + (ASCII–код другої літери прізвища – мала латинська літера)] % 30 + 1

4.2. Варіанти завдань

Змоделювати чергу або дек на базі статичного масиву згідно з завданням. Написати основні операції для роботи з чергою (push, pop, front, empty, full) або деком (push_left, push_right, pop_left, pop_right, front_left, front_right, empty, full) і продемонструвати правильність їх виконання. Для цього (якщо в завданні не вказано інший спосіб) в програмі на вході задати послідовність з К (К>10) цілих чисел (числа вводити з клавіатури). Всі додатні числа послідовно заносити в чергу (дек), кожне від’ємне число має вилучати з черги (деку) один елемент (при роботі з деком, парні числа працюють з правим кінцем деку, а непарні – з лівим). Виводити на екран динаміку вмісту черги (деку) під час обробки заданої послідовності. Вхідну послідовність чисел задати такою, щоб вона демонструвала роботу основних операцій та генерувала виникнення ситуацій "втрати значимості черги"(queue underflow) і "переповнення черги" (queue overflow) або "втрати значимості деку"(deq underflow) і "переповнення деку" (deq overflow).

Примітка: після реалізації черги або деку працювати з ними як з абстрактними типами даних, а не як з масивами.

1. Змоделювати циклічну чергу, в якій реалізований такий механізм додавання нового елемента: якщо досягнутий кінець масиву, то новий елемент додається в перший елемент масиву, якщо це можливо. Після обробки всієї заданої вхідної послідовності перевірити, чи елементи черги будуть відсортовані по зростанню, чи ні.

2. Змоделювати чергу, в якій до опису черги додано дві змінні EMPTY та FULL замість функцій empty() та full() відповідно. Переписати основні функції роботи з чергою з врахуванням цих змінних. Показати динаміку вмісту черги. Після обробки всієї заданої вхідної послідовності перевірити, чи є в черзі три однакових елемента, що йдуть підряд.

3. Змоделювати дек з обмеженим входом (тобто вилучати з дека можна з обох кінців, а додавати тільки з одного). Після обробки всієї заданої вхідної послідовності змінити порядок слідування елементів в деку на протилежний.

4. Змоделювати чергу, в якій покажчик кінця черги вказує не на останній елемент черги, а на перший вільний елемент масиву. Після обробки всієї заданої вхідної послідовності перевірити, чи елементи черги будуть відсортовані по спаданню, відсортовані по зростанню або невідсортовані.

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

6. Змоделювати дек, в якому до опису деку додано дві функції commute_left та commute_right, які заміняють елемент, що знаходиться в кінці деку (правому або лівому відповідно), на заданий елемент. Кожний раз, коли після операції вилучення в лівому або в правому кінці деку опиниться число меньше за 10, то треба подвоїти його значення. Після обробки всієї заданої вхідної послідовності збільшити в два раза значення кожного елемента черги.

7. Змоделювати чергу за допомогою масиву INFO[N], де INFO[0], а не окрема змiнна, використовується для зберiгання початку черги, INFO[N-1], а не окрема змiнна, використовується для зберiгання кінця черги; решта елементів масиву можуть містити елементи самої черги. Після обробки всієї заданої вхідної послідовності перевірити, чи буде в черзі непарна кількість елементів, чи ні.

8. Змоделювати чергу, в якій реалізований такий механізм вилучення елемента з черги: початок черги завжди знаходиться в першому елементі масиву; при вилученні одного елемента з черги, всі решта елементів пересуваються на одну позицію ближче до початку масиву. Після обробки всієї заданої вхідної послідовності визначити, чи сума всіх парних чисел черги буде більшою за суму непарних, чи ні.

9. Змоделювати чергу, в якій до опису черги додано змінну EMPTY замість функції empty(). Переписати основні функції роботи з чергою з врахуванням цієї змінної. Після обробки всієї заданої вхідної послідовності знайти довжину найбільш довгої послідовності однакових елементів черги, що йдуть підряд.

10. Змоделювати дек (тобто додавати i вилучати елементи можна з обох кінців). Після обробки всієї заданої вхідної послідовності продублювати всі елементи дека (тобто замість кожного одного елемента має стати підряд два однакових).

11. Змоделювати чергу з пріоритетами. Новий елемент додається завжди в кінець черги, а при вилученні елемента в черзі шукається (цей пошук може бути тільки послідовним) елемент із максимальним пріоритетом і після цього він вилучається з черги. На вході задається послідовність слів. Пріоритет визначається як довжина слова. Якщо слово починається з великої літери, то воно додається в чергу, якщо з малої, то з черги вилучається один елемент. Після обробки всієї заданої вхідної послідовності визначити найбільшу кількість елементів з однаковим пріоритетом.

12. Змоделювати чергу, в якій замість двох функцій pop і front використовується тільки одна функція pop, яка робить ці дві дії одночасно, тобто і вилучає елемент зі стека, і повертає його значення. Після обробки всієї заданої вхідної послідовності перевірити, чи є в черзі два однакових елемента, що йдуть підряд.

13. Змоделювати чергу, в якій реалізований такий механізм додавання нового елемента: якщо досягнутий кінець масиву, то всі елементи черги пересуваються на початок масиву. Після обробки всієї заданої вхідної послідовності визначити, чи є в черзі хоча б одне число менше за 7.

14. Змоделювати чергу, в якій до опису черги додано функцію wipe_out, яка вилучає всі елементи з черги. Кожний раз, коли у вхідній послідовності зустрічається число 0, то всі елементи мають бути вилучені з черги. Після обробки всієї заданої вхідної послідовності перевірити, чи є в черзі одинакові числа.

15. Змоделювати чергу, в якій до опису черги додано змінну FULL замість функції full(). Переписати основні функції роботи з чергою з врахуванням цієї змінної. Показати динаміку вмісту черги. Після обробки всієї заданої вхідної послідовності знайти кількість елементів черги, які більші за своїх сусідів.

16. Змоделювати дек, в якому до опису деку додано дві функції commute_left та commute_right, які заміняють елемент, що знаходиться в кінці деку (правому або лівому відповідно), на заданий елемент. Кожний раз, коли після операції додавання в лівому або в правому кінці деку опиниться число більше за 50, то треба зменшити його значення на 10. Після обробки всієї заданої вхідної послідовності перевірити, чи буде дек “дзеркальним” (тобто перший елемент буде дорівнювати останньому, другий – передостанньому і т.д.).

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

18. Змоделювати чергу за допомогою двох стеків. Додавання елемента до черги зводиться до додавання до одного зі стеков, а перевірка, чи черга порожня - до перевірки, чи порожні обидва стеки. При вилученні елемента з черги можливі два випадки. Якщо стек, де знаходиться початок черги, не порожній, то вилучається з нього елемент. Якщо він порожній, то попередньо в нього переписуються всі елементи другого стеку, змінюючи порядок (це відбувається автоматично при перекладанні елементів з одного стеку в інший) і далі задача зводиться до першого випадку.

19. Змоделювати дек, в якому до опису деку додано функцію change, яка міняє значення елементів, що знаходяться в лівому та в правому кінцях деку. Кожний раз, коли у вхідній послідовності зустрінеться число 0, то треба обміняти значення лівого і правого кінців деку. Після обробки всієї заданої вхідної послідовності знайти суму парних чисел деку.

20. Змоделювати чергу з пріоритетами у якій послідовність елементів черги весь час підтримується впорядкованою, тобто кожний новий елемент додається на те місце в черзі, яке визначається його пріоритетом, а при вилученні завжди вибирається елемент з початку черги. На вході задається послідовність слів. Пріоритет визначається як довжина слова. Якщо слово починається з голосної літери, то воно додається в чергу, якщо з приголосної, то з черги вилучається один елемент. Після обробки всієї заданої вхідної послідовності знайти кількість елементів черги з пріоритетами більшими за 3.

21. Змоделювати дек з обмеженим виходом (тобто додавати в дек можна з обох кінців, а вилучати тільки з одного). Після обробки всієї заданої вхідної послідовності перетворити отриманий дек так, щоб він не містив однакових елементів, що йдуть підряд (тобто замість кожної послідовності однакових елементів має залишитись тільки один елемент, наприклад, з деку з вмістом 22230115555 треба отримати дек з вмістом 23015).

22. Змоделювати циклічну чергу, в якій реалізований такий механізм додавання нового елемента: якщо досягнутий кінець масиву, то новий елемент додається в перший елемент масиву, якщо це можливо. Після обробки всієї заданої вхідної послідовності перевірити, чи всі числа у черзі будуть парними, чи ні.

23. Змоделювати чергу з пріоритетами у якій послідовність елементів черги весь час підтримується впорядкованою, тобто кожний новий елемент додається на те місце в черзі, яке визначається його пріоритетом, а при вилученні завжди вибирається елемент з початку черги. На вході задається послідовність цілих чисел. Пріоритет кожного числа визначається як кількість ціфр у цьому числі. Додатні числа заносяться в чергу, а кожне від’ємне число вилучає з черги один елемент. Після обробки всієї заданої вхідної послідовності знайти найбільший елемент черги.

24. Змоделювати дек (тобто додавати i вилучати елементи можна з обох кінців). Після обробки всієї заданої вхідної послідовності перевірити, чи є в черзі одинакові елементи.

25. Змоделювати чергу, в якій до опису черги додано функцію double, яка збільшує в два рази значення кожного елемента черги. Кожний раз, коли у вхідній послідовності зустрінеться число 0, то треба подвоїти всі елементи черги. Після обробки всієї заданої вхідної послідовності визначити, чи є у черзі хоча б одне число менше за 10.

26. Змоделювати чергу, в якій реалізований такий механізм вилучення елемента з черги: початок черги завжди знаходиться в першому елементі масиву; при вилученні одного елемента з черги, всі решта елементів пересуваються на одну позицію ближче до початку масиву. Після обробки всієї заданої вхідної послідовності знайти середнє арифметичне всіх елементів черги.

27. Змоделювати дек з обмеженим входом (тобто вилучати з дека можна з обох кінців, а додавати тільки з одного). Після обробки всієї заданої вхідної послідовності визначити, чи є у черзі хоча б одне число, що містить тільки однакові цифри.

28. Змоделювати чергу за допомогою масиву, в якому перший елемент масиву, а не окрема змiнна, використовується для зберiгання початку черги і останній елемент масиву, а не окрема змiнна, використовується для зберiгання кінця черги; решта елементів масиву можуть містити елементи самої черги. Після обробки всієї заданої вхідної послідовності перевірити, чи елементи черги будуть відсортовані по спаданню, чи ні.

29. Змоделювати чергу, в якій реалізований такий механізм додавання нового елемента: якщо досягнутий кінець масиву, то всі елементи черги пересуваються на початок масиву. Після обробки всієї заданої вхідної послідовності знайти три найбільших елемента черги.

30. Змоделювати чергу, в якій до опису черги додано функцію only, яка вилучає з черги всі елементи, значення яких співпадають з заданим значенням. Кожний раз після операції вилучення, якщо на початку черги опиняється парне число, то з черги вилучаються всі числа з таким самим значенням. Після обробки всієї заданої вхідної послідовності знайти сума всіх парних чисел, що залишились у черзі.