РЕКУРСИВНІ СТРУКТУРИ ДАНИХ

          Зауваження. Всі рекурсивні структури даних у цьому розділі реалізовувати на базі вказівників та динамічної пам’яті.

          10.1. Описати модуль для реалізації стеку символів. Передбачити виконання дій над стеком:

1)     Почати роботу.

2)     Чи порожній стек?

3)     Вштовхнути елемент у стек.

4)     Верхівка стеку.

5)     Забрати верхівку стеку.

Використовуючи цей модуль, розв’язати задачу: на вхід поступає послідовність символів. Впорядкувати цю послідовність за зростанням.

Вказівка. Для впорядкування використати 2 стеки.

          10.2. Використовуючи модуль для реалізації стеку символів (див. завдання 10.1), скласти підпрограми:

а) довжина стеку;

б) змiнити верхiвку стеку;

в) інверсiя стеку;

г) забрати n елементiв стеку.

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

1)     Почати роботу.

2)     Чи порожня черга?

3)     Додати елемент до кінця черги.

4)     Взяти елемент з початку черги.

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

          10.4. Використовуючи модуль для реалізації черги цілих чисел (див. завдання 10.3), розв’язати наступну задачу. У черзі є m чисел. Проводять nвипробувань, в результаті кожного з яких отримують випадкові числа 0 або 1. Якщо отримано 0, то треба взяти елемент з початку черги та показати його на екрані. Якщо отримано 1, то ввести число з клавіатури та додати до кінця черги. Після завершення випробувань показати залишок черги.

Вказівка. Використати генератор випадкових чисел (підпрограми randomize – ініціалізації генератора - та random(k) – отримання випадкового натурального числа у діапазоні від 0 до (k-1)).

          10.5. Використовуючи модуль для реалізації черги цілих чисел (див. завдання 10.3), розв’язати задачу “лічилка”, яка формулюється наступним чином. По колу розташовано n гравців, що мають номери від 1 до n. У лічилці m слів. Починають лічити з першого гравця. n-ий гравець вибуває, після чого знову починають лічити з гравця, що є наступним за тим, що вибув, і т. д. Треба показати послідовність номерів, що вибувають, при заданих значеннях n та m.

          10.6. Використовуючи модуль для реалізації черги цілих чисел (див. завдання 10.3), розв’язати наступну задачу. У магазині стоїть черга з mпокупців. Час обслуговування покупця з черги – це випадкове ціле число в діапазоні від 1 до t₁. Час додавання нового покупця до черги - це випадкове ціле число в діапазоні від 1 до t₂. Промоделювати стан черги (тобто показати час виникнення подій – обслуговування та додавання покупця) за період часу T (T >>  t₁, T >>  t₂). Показати залишок черги.

          10.7. Використовуючи модуль для реалізації черги цілих чисел (див. завдання 10.3), скласти підпрограми:

а) інверсiя черги;

б) забрати n елементiв черги;

в) конкатенацiя двох черг;

г) порiвняти 2 черги.

          10.8. Описати модуль для реалізації деку цілих чисел. Передбачити виконання дій над деком:

1)     Почати роботу.

2)     Чи порожній дек?

3)     Додати елемент до початку деку.

4)     Взяти елемент з початку деку.

5)     Додати елемент до кінця деку.

6)     Взяти елемент з кінця деку.

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

          10.9. Використовуючи модуль для реалізації деку цілих чисел (див. завдання 10.8), реалізувати стек цілих чисел на базі деку. Реалізувати стек на базі деку - означає описати модуль та реалізувати дії над стеком викликами відповідних підпрограм, що реалізують дії над деком. Для реалізованого стеку розв’язати задачу інвертування вхідної послідовності цілих чисел.

          10.10. Використовуючи модуль для реалізації деку цілих чисел (див. завдання 10.8), реалізувати чергу на базі деку (див. попереднє завдання). Для реалізованої черги розв’язати задачу обчислення довжини черги.

          10.11. Розв’язати задачу “лічилка” (див. завдання 10.5), використовуючи модуль для реалізації деку цілих чисел (див. завдання 10.8).

          10.12. Використовуючи модуль для реалізації деку цілих чисел (див. завдання 10.8), розв’язати задачу 10.4, передбачивши однак чотири можливих результати кожного випробування (випадкові числа від 0 до 3):

·        0 – взяти елемент з початку деку та показати його на екрані;

·        1 – ввести число з клавіатури та додати його до початку деку;

·        2 – взяти елемент з кінця деку та показати його на екрані;

·        3 – ввести число з клавіатури та додати його до кінця деку.

          10.13. Використовуючи модуль для реалізації деку цілих чисел (див. завдання 10.8), розв’язати задачу 10.6, передбачивши що через випадковий час від 1 до t₃ до початку черги додається „пільговий” покупець, який обслуговується першим, а через випадковий час від 1 до t₄ не витримує та йде з черги останній покупець.

          10.14. Використовуючи модуль для реалізації деку цілих чисел (див. завдання 10.8), скласти підпрограми:

а) інверсiя деку;

б) конкатенацiя двох декiв;

в) порiвняти 2 деки;

г) забрати n елементiв з початку деку;

д) забрати n елементiв з кiнця деку;

е) замiнити початок деку;

є) замiнити кiнець деку.

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

1)     Почати роботу.

2)     Чи порожній список?

3)     Додати елемент.

4)     Голова списку.

5)     Хвіст списку.

Використовуючи цей модуль, скласти підпрограми:

а) обчислення довжини списку Len(L) та пошуку у списку елемента, рівного заданому числу Search(L, x);

б) конкатенації двох списків Concat(L1, L2) та інверсії списку Invert(L);

в) сортування списку Sort(L);

г) перевірки, чи є один список початком другого IsBeg(L1, L2) та чи входить один список у другий IsIn(L1, L2);

д) заміни всіх входжень у список елемента m числом n Replace(L, m, n).

          10.16. Використовуючи модуль для реалізації класичного списку цілих чисел (див. завдання 10.15), скласти підпрограми:

а) IsSymm(L) - перевірка списку на симетричність;

б) Copy(L, m, n) - видiлити з списку L n елементiв, починаючи з елемента з номером т у новий список;

в) Del(L, m, n) - видалення n елеменiв списку L, починаючи з m-го.

          10.17. Використовуючи модуль для реалізації класичного списку цілих чисел (див. завдання 10.15), скласти підпрограми для реалізації додаткових дій над списком: App(L, x) – дописати елемент у кінець списку, Lst(L) – повернути останній елемент списку, Bgn(L) – повернути початок списку без останнього елемента.

          10.18. Описати модуль для реалізації списку цілих чисел з поточним елементом. Передбачити виконання дій над списком:

1)     Почати роботу.

2)     Чи порожній залишок списку?

3)     Встати до початку списку.

4)     Перейти до наступного елемента.

5)     Поточний елемент.

6)     Вставити елемент.

7)     Видалити елемент.

Використовуючи цей модуль, скласти підпрограми:

а) пошуку у списку елемента, рівного заданому числу Search(L, x);

б) сортування списку Sort(L);

в) конкатенації двох списків Concat(L1, L2);

г) присвоєння для списків Let(L1, L2) та обчислення довжини списку Len(L);

д) перевірки, чи є один список початком другого IsBeg(L1, L2) та чи входить один список у другий IsIn(L1, L2);

е) інверсії списку Invert(L).

          10.19. Використовуючи модуль для реалізації списку цілих чисел з поточним елементом (див. завдання 10.18), скласти підпрограми:

а) Change(L, n) - замiнити поточний елемент списку з поточним елементом L числом n;

б) IsSymm(L) - перевірка списку на симетричність;

в) Copy(L, m, n, L1) - видiлити з списку L n елементiв, починаючи з елемента з номером т у новий список L1;

г) Del(L, m, n) - видалення n елеменiв списку L, починаючи з m-го.

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

1)     Почати роботу.

2)     Довжина списку.

3)     Перейти до наступного елемента.

4)     Поточний елемент.

5)     Вставити елемент.

6)     Видалити елемент.

Використовуючи цей модуль, розв’язати задачі:

а) “лічилка” (див. завдання 10.5);

б) пошук у списку елемента, рівного заданому числу Search(L, x) та присвоєння для списків Let(L1, L2);

в) знайти послідовність рівних елементів списку, що йдуть підряд, максимальної довжини;

г) видалити із списку всі повторні входження елементів;

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

          10.21. Використовуючи модуль для реалізації кільцевого списку цілих чисел (див. завдання 10.20), скласти підпрограми:

а) Change(L, n) - замiнити поточний елемент списку L числом n;

б) IsSymm(L) - перевірка списку на симетричність;

в) Copy(L, m, n, L1) - видiлити з списку L n елементiв, починаючи з елемента з номером т у новий список L1;

г) Del(L, m, n) - видалення n елеменiв списку L, починаючи з m-го, по відношенню до поточного, елемента кільцевого списку.

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

1)           Почати роботу.

2)           Чи порожній список?

3)           Чи порожній початок списку?

4)           Чи порожній кінець списку?

5)           Встати до початку списку.

6)           Встати до кінця списку.

7)           Перейти до наступного елемента.

8)           Перейти до попереднього елемента.

9)           Поточний елемент.

10)      Вставити елемент перед поточним.

11)      Вставити елемент після поточного.

12)      Видалити елемент.

Використовуючи цей модуль, розв’язати задачі:

а) пошуку у списку елемента, рівного заданому числу Search(L, x) та обчислення довжини списку Len(L);

б) сортування списку Sort(L);

в) конкатенації двох списків Concat(L1, L2) та присвоєння для списків Let(L1, L2);

г) перевірки, чи є один список початком другого IsBeg(L1, L2) та чи входить один список у другий IsIn(L1, L2).

          10.23. Використовуючи модуль для реалізації двозв’язного списку цілих чисел (див. завдання 10.22), реалізувати на базі двозв’язного списку:

а) стек (розв’язати для стеку задачу інвертування послідовності символів);

б) чергу (розв’язати для черги задачу “лічилка” (див. завдання 10.5));

в) дек (розв’язати для деку задачу “лічилка” (див. завдання 10.5));

г) список з поточним елементом (розв’язати для списку задачу пошуку елемента у списку).

          10.24. Використовуючи модуль для реалізації двозв’язного списку цілих чисел (див. завдання 10.22), скласти підпрограми:

а) Change(L, n) - замiнити поточний елемент списку L числом n;

б) Copy(L, m, n, L1) - видiлити з списку L n елементiв, починаючи з елемента з номером т у новий список L1;

в) Del(L, m, n) - видалення n елеменiв списку L, починаючи з m-го.

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

1)     Почати роботу.

2)     Чи порожнє дерево?

3)     Створити дерево.

4)     Корінь дерева.

5)     Лівий син.

6)     Правий син.

Використовуючи цей модуль, розв’язати задачі:

а) виведення дерева на екран Print(t);

б) пошуку у дереві елемента, рівного заданому числу Search(t, x);

в) побудови бінарного дерева пошуку та пошуку елемента у ньому (бінарне дерева називають деревом пошуку, якщо для будь-якого його піддерева корінь цього піддерева не менше кожної вершини лівого сина та не більше кожної вершини правого сина);

г) обчислення висоти дерева Height(t);

д) перевірки, чи входить одне дерево у другие IsIn(t1, t2).

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

1)           Почати роботу.

2)           Чи порожнє дерево?

3)           Створити вершину.

4)           Корінь дерева.

5)           Список синів.

6)           Видалити вершину.

7)           Почати роботу із списком синів.

8)           Чи порожній залишок списку синів?

9)           Встати до початку списку синів.

10)      Перейти до наступного елемента списку синів.

11)      Поточний елемент списку синів.

12)      Вставити елемент у список синів.

13)      Видалити елемент списку синів.

Використовуючи цей модуль, розв’язати задачі:

а) побудови бінарного дерева за сильно розгалуженим деревом;

б) пошуку у дереві елемента, рівного заданому числу Search(t, x);

в) обчислення висоти дерева Height(t);

г) перевірки, чи входить одне дерево у другие IsIn(t1, t2).

          10.27. Описати модуль для реалізації графів. Передбачити виконання дій над графом:

1)                 Створити вершину.

2)                 Навантаження вершини.

3)                 Список попередників.

4)                 Список наступників.

5)                 Змінити список попередників.

6)                 Змінити список наступників.

7)                 Видалити вершину.

8)                 Почати роботу із списком вершин.

9)                 Чи порожній залишок списку вершин?

10)            Встати до початку списку вершин.

11)            Перейти до наступного елемента списку вершин.

12)            Поточний елемент списку вершин.

13)            Вставити елемент у список вершин.

14)            Видалити елемент списку вершин.

Використовуючи цей модуль, розв’язати задачі:

а) додати вершину графа;

б) видалити вершину графа;

в) перевірити, чи існує шлях між двома вершинами;

г) знайти найкоротший шлях між двома вершинами.

МОДУЛІ

          9.1. Описати модуль для реалізації універального комплексного типу (див. завдання 7.30). Реалізувати операції, відношення та інструкції:

1)           взяти комплексне число;

2)           показати комплексне число;

3)           чи рівні два комплексних числа;

4)           сума двох комплексних чисел;

5)           різниця двох компдексних чисел;

6)           добуток двох комплексних чисел;

7)           частка від ділення двох комплексних чисел;

8)           модуль комплексного числа;

9)           піднесення комплексного числа до натурального степеня;

10)      добуток комплексного числа та дійсного числа;

11)      переведення комплексного числа до алгебраїчної форми;

12)      переведення комплексного числа до тригонометричної форми.

З використанням модуля знайти корені рівняння a*z²+b*z+c=0 з комплексними коефіцієнтами a, b, c.

          9.2. Описати модуль роботи з відрізками на числовій вісі. Тип відрізку представити у вигляді запису:

          тип Відрізок = запис

                                                a, b: дійсн;

                                                empty: бул

                                      кз;

де a, b - границі відрізку, empty - ознака того, що відрізок порожній.

Реалізувати дії над відрізками:

1)     зробити відрізок t порожнім;

2)     чи порожній відрізок t;

3)     покласти відрізок t рівним a, b;

4)     покласти відрізок t рівним перетину відрізків t1, t2.

З використанням модуля скласти програму розв’язку системи квадратних нерівностей вигляду x²+p_ix+q_i>0. Пари коефіцієнтів нерівностей p_i, q_iвводяться з пристрою введення.

          9.3. Описати модуль для реалізації мультимножини цілих чисел на базі вектора. Мультимножина - це множина в якій для кожного елемента запам’ятовується не лише його входження, але й кількість входжень. Мультимножину описати як

          тип Мультимножина = масив [0..n] із нат;

де n - відома константа. Кількість входжень елемента k (0<=k<=n) у мультимножину - це значення елемента масиву з індексом k.

Реалізувати дії над мультимножинами:

1)     зробити мультимножину порожньою;

2)     чи є мультимножина порожньою;

3)     додати елемент до мультимножини;

4)     забрати елемент з мультимножини (кількість входжень елемента зменшується на 1, якщо елемент не входить - відмова);

5)     кількість входжень елемента у мультимножину;

6)     об’єднання двох мультимножин (в результаті об’єднання кідькість входжень елемента визначається як максимальна з двох мультимножин);

7)     перетин двох мультимножин (в результаті кількість входжень елемента визначається як мінімальна з двох мультимножин);

З використанням модуля розв’язати задачі:

а) знайти символ, який входить у рядок S максимальну кількість разів (див. завдання 7.111);

б) перевірити, чи складаються рядки S1, S2 з одних і тих же символів, які входять у ці рядки однакову кількість разів;

в) перевірити, чи вірно, що всі символи рядка S1, входять також у рядок S2, причому не меншу кількість разів, ніж у S1.

          9.4. Описати модуль для реалізації обмеженого стеку символів на базі вектора. Стек - це впорядкована сукупність однотипних елементів, в якій є доступ до одного елемента, що називається верхівкою стеку. Стек символів на базі масиву можна описати як:

          тип Стек = масив [1..n] із симв;

де n - відома константа. Елементи стеку будуть займати початковий відрізок вектора до деякого індекса top, який вказує на верхівку стеку.

Реалізувати дії над стеком:

1)     зробити стек порожнім;

2)     чи порожній стек;

3)     вштовхнути елемент у стек (додати новий елемент, який стає верхівкою стеку);

4)     верхівка стеку (повернути значення верхівки стеку; для порожнього стеку - відмова);

5)     забрати верхівку стеку (забрати верхній елемент стеку; для порожнього стеку - відмова).

З використанням модуля виконати інвертування вхідної послідовності символів.

          9.5. Описати модуль роботи з точками та відрізками на площині. Типи точки та відрізку представити у вигляді записів:

          тип   Точка = запис

                                                x, y: дійсн;

                                      кз;

                   Відрізок = запис

                                                a, b: Точка;

                                      кз;

Реалізувати дії над точками:

1)     взяти точку t;

2)     покласти точку t рівною (x, y);

3)     показати точку t.

Реалізувати дії над відрізками:

1)     взяти відрізок s;

2)     показати відрізок s;

3)     покласти відрізок s рівним a, b;

4)     довжина відрізку s;

5)     чи лежить точка t на одній прямій з відрізком s;

6)     чи лежить точка t всередині відрізку s;

7)     площа трикутника, утвореного точкою t та відрізком s.

У файлі записано послідовність точок. З використанням модуля роботи з точками та відрізками на площині знайти:

а) трикутник з найбільшою площею, утворений точками послідовності;

б) коло найменшого радіуса, всередині якого лежать всі точки послідовності;

в) відрізок, на якому лежить найбільша кількість точок послідовності;

г) коло, на якому лежить найбільша кількість точок послідовності.

          9.6. Описати модуль та скласти програму для реалізації гри у “хрестики-нолики” на полі розміром 3x3. У модулі реалізувати дії:

          1) зробити хід гравця;

          2) зробити хід комп’ютера;

          3) показати ігрове поле.

          9.7. Відома гра у “морський бій” полягає у наступному. Два гравці на двох полях 10x10 розставляють „кораблі” – прямокутники (4 – розміром 1x1, 3 – розміром 2x1, 2 – розміром 3x1, 1 – розміром 4x1). Кораблі не можуть мати сусідніх клітин по горизонталі, вертикалі або діагоналі. Гравці не бачать розстановку кораблів супротивника. Потім гравці по черзі роблять ходи (кожний хід – це вказання клітини на полі). Якщо гравець потрапляє на поле, яке займає корабель супротивника, він має право на позачерговий хід. Виграє той, хто першим знешкодить всі кораблі супротивника.

          Описати модуль та програму для реалізації гри у “морський бій” між гравцем та комп’ютером. Передбачити у модулі реалізацію дій:

1)     додати корабель;

2)     зробити хід гравця;

3)     зробити хід комп’ютера;

4)     показати ігрове поле (поле гравця та стан поля комп’ютера).

ПОШУК ТА СОРТУВАННЯ

          8.1. Дано вектор a з n цілих компонент. Знайти зростаючу підпослідовність компонентів вектора найбільшої довжини.

Вказівка. Використати вектор b, у який записувати останні елементи зростаючих підпослідовностей компонент з a довжини 1, 2, ..., k. Якщо на деякому кроці циклу a[i] > b[k], то записати у (k+1)-й елемент вектора b компонент a[i] та збільшити значення k на 1. Інакше знайти перший елемент вектора b, b[j] такий, що a[i] <= b[j] та записати a[i] на місце b[j]. Оскільки елементи вектора b впорядковані, використати бінарний пошук для знаходження індекса j. Після того, як закінчимо прохід вектора a останній елемент вектора b буде останнім елементом шуканої підпослідовності, а кількість елементів вектора b,k - її довжиною. Для того, щоб показати саму підпослідовність (в оберненому порядку), можна використати цикл:

          i¬n;

          поки k>0 повт

                   поки a[i]<b[k] повт

                             i¬i-1

                   кц;

                   показати(a[i]);

                   k¬k-1

          кц

          8.2. Визначити процедуру впорядкування рядків дійсної матриці

а) за неспаданням їх перших елементів;

б) за незростанням сум їх елементів;

в) за неспаданням їх найменших елементів;

г) за незростанням їх найбільших елементів.

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

          8.3. Дано масив з n точок площини, заданих своїми координатами. Впорядкивати точки за неспаданням відстані від початку координат.

          8.4. Дано текстові файли F та G. Відомо, що кількість слів у файлі F не більше n, де n - відома константа. Перевірити, чи всі слова з файлу Gвходять у файл F.

Вказівка. Використати масив рядків a з n елементів, у який записати всі різні слова файлу F, впорядковані за зростанням. Використати бінарний пошук для пошуку слова з файлу G у масиві a.

          8.5. В умовах попереднього завдання визначити кількість входжень кожного слова файлу F у файл G.

Вказівка. У масиві a з попереднього завдання зберігати разом зі словом кількість його входжень у файл G.

          8.6. Даний текстовий файл F. Відомо, що кількість слів у файлі F не більше n, де n - відома константа. Побудувати за файлом F пару файлів G та H, щоб у компонентах файлу G зберігались усі різні слова файлу F, впорядковані за алфавітом, а у файлі H - цілі числа. Причому i-е число файлу H - це номер i-го слова з файлу F у файлі G.

Вказівка. Використати масив рядків a з n елементів, у який записати всі різні слова файлу F, впорядковані за зростанням.

          8.7. Нехай файли A та B, компонентами яких є цілі числа, впорядковані з неспаданням. Отримати у файлі C всі числа з файлів A та B без повторень. Файл C повинен бути впорядкований за зростанням.

          8.8. Даний файл F, компонентами якого є цілі числа. Отримати у файлі G всі непарні числя, що входять у F. Числа у файлі G повинні йти:

а) у порядку незростання;

б) у порядку спадання без повторень.

          8.9. Даний текстовий файл F. Записати у файл G всі різні слова файлу F у порядку зростання.