10. РЕКУРСИВНІ СТРУКТУРИ ДАНИХ
Зауваження. Всі рекурсивні
структури даних у цьому розділі реалізовувати на базі вказівників та динамічної
пам’яті.
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 до t1. Час додавання нового покупця до черги - це випадкове ціле
число в діапазоні від 1 до t2. Промоделювати стан
черги (тобто показати час виникнення подій – обслуговування та додавання
покупця) за період часу T (T
>> t1, T >> t2). Показати залишок черги.
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 до t3 до початку черги
додається „пільговий” покупець, який обслуговується першим, а через випадковий
час від 1 до t4 не витримує та йде з черги останній
покупець.
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)
Видалити елемент списку вершин.
Використовуючи цей модуль, розв’язати задачі:
а) додати вершину графа;
б) видалити вершину графа;
в) перевірити, чи існує шлях між двома вершинами;
г) знайти найкоротший шлях між двома вершинами.