5. Форми рекурсії.

У попередній розділ На головну | У наступний розділ

1. Описати рекурсивную функцію Fact (N) дійсного типу, яка обчислює значення факторіала N! = 1 • 2 • ... • N (N> 0 - параметр цілого типу). За допомогою цієї функції обчислити факторіали п'яти довільних натуральних чисел.
2. Описати рекурсивную функцію Fact2 (N) дійсного типу, яка обчислює значення подвійного факторіала N !! = N • (N-2) • (N-4) • ... (N> 0 - параметр цілого типу; останній співмножник в творі дорівнює 2, якщо N - парне число, і 1, якщо N - непарне). За допомогою цієї функції обчислити подвійні факторіали п'яти довільних натуральних чисел.
3. Описати рекурсивную функцію PowerN (X, N) дійсного типу, яка знаходить значення N-го ступеня числа X за формулами:
X0 = 1,
XN = (XN / 2) 2 при парних N> 0, XN = X • XN-1 при непарних N> 0,
XN = 1 / X-N при N <0
(X ≠ 0 - дійсне число, N - ціле; у формулі для парних N повинна використовуватися операція цілочисельного ділення). За допомогою цієї функції знайти значення XN для даного X при довільних значеннях N.
4. Описати рекурсивную функцію Fib1 (N) цілого типу, яка обчислює N-й елемент послідовності чисел Фібоначчі (N - ціле число):
F1 = F2 = 1, FK = FK-2 + FK-1, K = 3, 4, ....
За допомогою цієї функції знайти п'ять чисел Фібоначчі з даними номерами, і вивести ці числа разом з кількістю рекурсивних викликів функції Fib1, потребовавшихся для їх знаходження.
5. Описати рекурсивную функцію Combin1 (N, K) цілого типу, яка знаходить C (N, K) - число поєднань з N елементів по K - за допомогою рекурентного співвідношення:
C (N, 0) = C (N, N) = 1,
C (N, K) = C (N - 1, K) + C (N - 1, K - 1) при 0 <K <N.
Параметри функції - цілі числа; N> 0, 0 ≤ K ≤ N. Дано число N і п'ять різних значень K. Вивести числа C (N, K) разом з кількістю рекурсивних викликів функції Combin1, потребовавшихся для їх знаходження.
6. Описати рекурсивную функцію RootK (X, K, N) дійсного типу, яка знаходить наближене значення кореня K-го ступеня з числа X за формулою:
Y0 = 1, YN + 1 = YN - (YN - X / (YN) K-1) / K,
де YN позначає RootK (X, K, N) при фіксованих X і K. Параметри функції: X (> 0) - дійсне число, K (> 1) і N (> 0) - цілі. За допомогою функції RootK знайти для даного числа X наближені значення його кореня K-го ступеня при шести даних значеннях N.
7. Описати рекурсивную функцію GCD (A, B) цілого типу, яка знаходить найбільший спільний дільник (НСД, greatest common divisor) двох цілих позитивних чисел A і B, використовуючи алгоритм Евкліда:
НСД (A, B) = НСД (B, A mod B), B ≠ 0; НСД (A, 0) = A,
де «mod» позначає операцію взяття залишку від ділення. За допомогою цієї функції знайти НСД (A, B), НСД (A, C), НСД (A, D), якщо дано числа A, B, C, D.
8. Описати рекурсивную функцію DigitSum (K) цілого типу, яка знаходить суму цифр цілого числа K, не використовуючи оператор циклу. За допомогою цієї функції знайти суми чисел для п'яти довільних цілих чисел.
9. Описати рекурсивную функцію MaxElem (A, N) цілого типу, яка знаходить максимальний елемент цілочисельного масиву A розміру N (1 ≤ N ≤ 10), не використовуючи оператор циклу. За допомогою цієї функції знайти максимальні елементи масивів A, B, C розміру NA, NB, NC відповідно.
10. Описати рекурсивную функцію DigitCount (S) цілого типу, яка знаходить кількість цифр в рядку S, не використовуючи оператор циклу. За допомогою цієї функції знайти кількість цифр у кожній з п'яти даних рядків.
11. Описати рекурсивную функцію Palindrome (S) логічного типу, яка повертає True, якщо рядок S є паліндромом (тобто читається однаково зліва направо і справа наліво), і False в іншому випадку. Оператор циклу в тілі функції не використовувати. Вивести значення функції Palindrome для п'яти довільних рядків.
12. Вивести значення цілочисельного виразу, заданого у вигляді рядка S. Вираз визначається наступним чином:
<Вираз> :: = <цифра> | <Вираз> + <цифра> |
  <Вираз> - <цифра>
13. Вивести значення цілочисельного виразу, заданого у вигляді рядка S. Вираз визначається наступним чином:
<Вираз> :: = <терм> | <Вираз> + <терм> |
  <Вираз> - <терм>
<Терм> :: = <цифра> | <Терм> * <цифра>
14. Вивести значення цілочисельного виразу, заданого у вигляді рядка S. Вираз визначається наступним чином:
<Вираз> :: = <цифра> |
  (<Вираз> <знак> <вираз>)
<Знак> :: = + | - | *
15. Перевірити правильність виразу, заданого у вигляді непорожній рядки S (вираз визначається за тими ж правилами, що і в завданні 14). Якщо вираз складено правильно, то вивести 0, в іншому випадку вивести номер першого помилкового, зайвого або відсутнього символу в рядку S.
16. Вивести значення логічного виразу, заданого у вигляді рядка S. Вираз визначається наступним чином ( «T» - True, «F» - False):
<Вираз> :: = T | F | And (<вираз>, <вираз>) |
  Or (<вираз>, <вираз>)
17*. Дано дерево глибини N, кожна внутрішня вершина якого має K (<10) безпосередніх нащадків (нумеруються від 1 до K). Корінь дерева має номер 0. Записати в текстовий файл з даними ім'ям всі можливі шляхи, що ведуть від кореня до листя. Перебирати шляху, починаючи з «самого лівого» і закінчуючи «самим правим» (при цьому першими замінювати кінцеві елементи шляху).
18*. Дано дерево глибини N, кожна внутрішня вершина якого має K (<10) безпосередніх нащадків (нумеруються від 1 до K). Корінь дерева має номер 0. Записати в текстовий файл з даними ім'ям всі шляхи, що ведуть від кореня до листя і задовольняють наступній умові: ніякі сусідні елементи шляху не нумеруються однією і тією ж цифрою. Порядок перебору шляхів такої ж, як в завданні 17.
19*. Дано дерево глибини N, кожна внутрішня вершина якого має 3 безпосередніх нащадка: A з вагою 1, B з вагою 0 і C з вагою -1. Корінь дерева D має вагу 0. Записати в текстовий файл з такою назвою все шляху від кореня до листя, що відповідають таким умовам: сумарна вага елементів для будь-якого початкового відрізка шляху неположітелен, а сумарна вага всіх елементів шляху дорівнює 0. Порядок перебору шляхів такої ж, як в завданні 17.
20*. Дано дерево глибини N того ж типу, що й в завданні 19. Записати в текстовий файл з такою назвою все шляху від кореня до листя, що відповідають таким умовам: ніякі сусідні елементи шляху не позначаються однією і тією ж буквою, а сумарна вага всіх елементів шляху дорівнює 0. Порядок перебору шляхів такої ж, як в завданні 17.

Остання зміна: Monday 23 April 2018 10:33 AM