Лабораторна робота № 3

Тема роботи: Програмування рекурсивних функцій

Мета роботи: _ практично закріпити теоретичні знання про рекурсивні функції; _ навчитися застосовувати рекурсивні функції для реалізації різноманітних рекурентних залежностей і процесів; _ порівняти рекурсивний та нерекурсивний (ітераційний) варіанти програми (функцій) за складністю, наочністю і швидкодією.

Завдання лабораторної роботи:

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

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

2. Написати ітераційний (нерекурсивний) варіант (варіанти) заданої функції. У процесі роботи ця функція може звертатися до інших допоміжних функцій.

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

4. Ввести текст програми та зберегти його в особистому каталозі.

5. Реалізувати програму для декількох наборів вхідних даних і занотувати результати.

6. Написати рекурсивний варіант реалізації заданої функції. Можливо, що рекурсивна функція буде викликатися з іншої додаткової функції або рекурсивна функція буде виконувати тільки якусь частину з того завдання, яке має виконувати вказана функція. Обов’язково треба звернути увагу на базис – умову завершення рекурсії та на коректне задання параметрів і запис рекурсивних викликів. Яку рекурсію – хвостову чи внутрішню краще застосувати в рекурсивній функції? Яка між ними різниця?

7. Реалізувати програму з рекурсивною функцією для тих самих вхідних даних, що в п.5, і порівняти отримані результати. Записати їх у звіт.

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

9. Офрмити звіт з лабораторної роботи. У висновках до роботи порівняти рекурсивний та ітераційний (нерекурсивний) варіанти реалізації заданих функцій.

Варіанти індивідуальних завдань

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

2. Розробити функцію, яка визначає та виводить на екран всі можливі подання заданого натурального числа N (N 50000) у формі суми рівно k (k 10) доданків (теж натуральних чисел). З клавіатури ввести масив беззнакових цілих чисел. Використовуючи розроблену функцію, подати розклад кожного з введених чисел на задану кількість доданків. Забезпечити зупинку виведення після кожного числа.

3. Розробити функцію, яка обчислює найменше спільне кратне (НСК) двох заданих натуральних чисел. З клавіатури ввести декілька беззнакових цілих чисел. Використовуючи розроблену функцію, визначити НСК усіх введених чисел.

4. Розробити функцію, яка переставляє у зворотному порядку цифри заданого довгого цілого числа (наприклад, число 5321 перетворюється у 1235 ). З клавіатури ввести масив довгих цілих чисел. Використовуючи розроблену функцію, замінити всі числа цього масиву і надрукувати результат заміни.

5. Розробити функцію, яка вставляє в масив дійсних чисел, відсортований у порядку зростання значень елементів, додаткове число, зберігаючи загальну впоряд­кованість. З клавіатури ввести матрицю дійсних чисел, в якій елементи кожного рядка відсортовані за зростанням значень. Використовуючи розроблену функцію, вставити в кожен рядок матриці на відповідне місце заданий додатковий елемент. Надрукувати доповнену матрицю.

6. Розробити функцію, яка перевіряє, чи заданий символьний рядок є правильним записом 16-го коду цілого додатного числа, і повертає десяткове значення цього числа (або -1 у разі помилки). З клавіатури ввести послідовність символьних рядків із 16-ми кодами чисел. На основі розробленої функції обчислити десяткове значення кожного з цих чисел. Надрукувати результат перетворення кодів у формі таблиці, відзначивши рядки, в яких записані неправильні 16-ві коди.

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

8. Розробити функцію, яка формує масив заданої довжини із цілих випадкових чисел, що потрапляють у діапазон min ..  max. Cеред елементів вектора не повинно бути однакових. Використовуючи розроблену функцію, сформувати матрицю заданого розміру, у кожному рядку якої всі елементи різні.

9. Розробити функцію, яка вилучає зі заданого символьного рядка всі цифрові символи і повертає кількість вилучених цифр. З клавіатури ввести послідовність символьних рядків. Викорис­товуючи розроблену функцію, витерти з введених рядків усі символи цифр. Надрукувати рядки без чисел та зазначити, з якого рядка вилучено найбільше символів.

10. Розробити функцію, яка перетворює символьний рядок, що містить 2-10-й код числа, у відповідне числове десяткове значення. З клавіатури ввести декілька символьних рядків із 2-10-ми кодами чисел. На основі розробленої функції надрукувати таблицю всіх введених 2-10-х кодів та їхніх десяткових значень.

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

12. Розробити функцію для порівняння двох українських слів за абетковим порядком. З клавіатури по одному ввести набір українських слів і занести їх у масив рядків. Використовуючи розроблену функцію, відсортувати введені слова за абетковим порядком.

13. Розробити функцію, яка міняє місцями відповідні за номером елементи двох векторів цілих чисел однакової довжини. З клавіатури ввести цілочислову матрицю. На основі розробленої функції переставити рядки введеної матриці у зворотному порядку. Надрукувати матрицю після переставляння елементів.

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

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

16. Розробити функцію, яка перетворює заданий символьний рядок, в якому записано двійковий код числа, у відповідне десяткове число і повертає значення цього числа (або -1 у разі помилки). З клавіатури ввести декілька рядків із двійковими кодами чисел. На основі розробленої функції обчислити десяткове значення кожного з них. Надрукувати таблицю введених двійкових кодів та їхніх десяткових значень, відзна­чивши коди з помилками.

17. Розробити функцію, яка обчислює т. зв. цифровий корінь заданого довгого натураль­ного числа (цифровий корінь знаходять так: додають всі цифри цього числа, потім всі цифри знайденої суми і повторювати цей процес доти, поки в результаті не буде однорозрядне число – цифра). З клавіатури ввести масив довгих беззнакових цілих чисел. Використовуючи розроблену функцію, знайти цифровий корінь кожного з введених чисел. Результат подати у формі таблиці.

18. Розробити функцію, яка визначає всі точки (x, y) з цілочисловими координатами, які потрапляють у круг з радіусом R і центром у точці (x₀, y₀) і повертає їхню кількість. З клавіатури ввести координати центра і радіус заданого круга. Використовуючи розроблену функцію, надрукувати всі точки з цілочисловими координатами, які потрапляють у цей круг і вказати їхню загальну кількість.

19. Розробити функцію, яка обчислює найбільший спільний дільник (НСД) двох заданих натуральних чисел. З клавіатури ввести декілька беззнакових цілих чисел. Використовуючи розроблену функцію, визначити НСД усіх введених чисел.

20. Розробити функцію, яка формує символьний рядок, що відповідає коду заданого цілого числа в системі числення з основою N (N 10). У масив занести послідовність введених з клавіатури цілих натуральних чисел – введення має завершуватись довільним симво­лом. На основі розробленої функції надрукувати таблицю введених чисел та їхніх кодів.

21. Розробити функцію, яка обчислює визначник заданої матриці дійсних чисел, використо­вуючи розклад за першомим рядком:

Матриця B отримується з матриці A шляхом викреслюванням першого рядка та k-го стовпця. . Використовуючи розроблену функцію, обчислити значення визначників заданих матриць дійсних чисел.

22. Розробити функцію, яка обчислює суму двох чисел, заданих у сімковій системі числення і записаних у формі символьних рядків (кожне число може складатися із 1-50 сімкових цифр). З клавіатури ввести декілька рядків із сімковими кодами чисел. На основі розробленої функції обчислити суму всіх пар цих чисел. Надрукувати кожну пару та їхню суму в окремому рядку.

23. Розробити функцію, яка формує та виводить на екран всі неоднакові послідовності з N нулів та одиниць, що містять рівно K одиниць (N і – два натуральні числа,   K  N  100 ). Проілюструвати роботу функції для різних вхідних значень.

24. Розробити функцію, яка обчислює значення полінома степеня у заданій точці ( – дійсне число), не використовуючи операції піднесення до степеня. Коефіцієнти полінома є дійсними числами і зберігаються у масиві за порядку зменшення степенів. З клавіатури ввести матрицю дійсних чисел. Використовуючи розроблену функцію, визначити значення поліномів степеня n, для коефіцієнтів, що задаються у кожному рядку матриці.

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

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

Сформувати масив з K випадкових дійсних чисел у діапазоні 1-100. На основі розробленої функції надрукувати таблицю згенерованих чисел та їхніх степенів (щонайменше трьох-чотирьох).

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

28. Розробити функцію, яка визначає кількість слів у реченні, що містять задану літеру. З кла­віа­тури ввести декілька речень. Використовуючи розроблену функцію, визначити загальну кількість таких слів та речення, в якому їх найбільше (якщо таких декілька, то вказати всі).

29. Розробити функцію, яка визначає найменший елемент заданого масиву дійсних чисел і додатково повертає його номер (нумерацію починати з 1). З клавіатури ввести матрицю дійсних чисел. Використовуючи розроблену функцію, визначити найменший елемент у кожному рядку і вказати його номер.