Рекурсия

Рекурсия: простейшие алгоритмы

Задания этой подгруппы можно легко решить и без использования рекурсии. Данное обстоятельство связано с тем, что в заданиях рассматриваются простейшие примеры рекурсии, легко сводимые к итерационным алгоритмам. Более того, в некоторых случаях непосредственные вычисления по рекурсивным формулам оказываются весьма неэффективными. Однако именно на подобных примерах проще всего получить первоначальные навыки разработки рекурсивных алгоритмов.

Recur1°.^{[Pascal] [C#] [VB.NET]} Описать рекурсивную функцию Fact(N) вещественного типа, вычисляющую значение факториала

N! = 1·2·…·N

(N > 0 — параметр целого типа). С помощью этой функции вычислить факториалы пяти данных чисел.

Recur2.^{[Pascal] [C#] [VB.NET]} Описать рекурсивную функцию Fact2(N) вещественного типа, вычисляющую значение двойного факториала

N!! = N·(N−2)·(N−4)·…

(N > 0 — параметр целого типа; последний сомножитель в произведении равен 2, если N — четное число, и 1, если N — нечетное). С помощью этой функции вычислить двойные факториалы пяти данных чисел.

Recur3.^{[Pascal] [C#] [VB.NET]} Описать рекурсивную функцию PowerN(X, N) вещественного типа, находящую значение N-й степени числа X по формулам:

X ⁰ = 1,
X ^N = (X ^N/2)² при четных N > 0,        X ^N = X·X ^N−1 при нечетных N > 0,
X ^N = 1/X ^−N при N < 0

(X ≠ 0 — вещественное число, N — целое; в формуле для четных N должна использоваться операция целочисленного деления). С помощью этой функции найти значения X ^N для данного X при пяти данных значениях N.

Recur4°.^{[Pascal] [C#] [VB.NET]} Описать рекурсивную функцию Fib1(N) целого типа, вычисляющую N-й элемент последовательности чисел Фибоначчи (N — целое число):

F₁ = F₂ = 1,        F_K = F_K−2 + F_K−1,    K = 3, 4, … .

С помощью этой функции найти пять чисел Фибоначчи с данными номерами, и вывести эти числа вместе с количеством рекурсивных вызовов функции Fib1, потребовавшихся для их нахождения.

Recur5°.^{[Pascal] [C#] [VB.NET]} Описать рекурсивную функцию Fib2(N) целого типа, вычисляющую N-й элемент последовательности чисел Фибоначчи (N — целое число):

F₁ = F₂ = 1,        F_K = F_K−2 + F_K−1,    K = 3, 4, … .

Считать, что номер N не превосходит 20. Для уменьшения количества рекурсивных вызовов по сравнению с функцией Fib1 (см. задание Recur4) создать вспомогательный массив для хранения уже вычисленных чисел Фибоначчи и обращаться к нему при выполнении функции Fib2. С помощью функции Fib2 найти пять чисел Фибоначчи с данными номерами.

Recur6.^{[Pascal] [C#] [VB.NET]} Описать рекурсивную функцию 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, потребовавшихся для их нахождения.

Recur7.^{[Pascal] [C#] [VB.NET]} Описать рекурсивную функцию Combin2(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 не превосходит 20. Для уменьшения количества рекурсивных вызовов по сравнению с функцией Combin1 (см. задание Recur6) описать вспомогательный двумерный массив для хранения уже вычисленных чисел C(N, K) и обращаться к нему при выполнении функции Combin2. С помощью функции Combin2 найти числа C(N, K) для данного значения N и пяти различных значений K.

Recur8.^{[Pascal] [C#] [VB.NET]} Описать рекурсивную функцию RootK(X, K, N) вещественного типа, находящую приближенное значение корня K-й степени из числа X по формуле:

Y₀ = 1,        Y_N+1 = Y_N − (Y_N − X/(Y_N)^K−1)/K,

где Y_N обозначает RootK(X, K, N) при фиксированных X и K. Параметры функции: X (> 0) — вещественное число, K (> 1) и N (> 0) — целые. С помощью функции RootK найти для данного числа X приближенные значения его корня K-й степени при шести данных значениях N.

Recur9.^{[Pascal] [C#] [VB.NET]} Описать рекурсивную функцию 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.

Recur10°.^{[Pascal] [C#] [VB.NET]} Описать рекурсивную функцию DigitSum(K) целого типа, которая находит сумму цифр целого числа K, не используя оператор цикла. С помощью этой функции найти суммы цифр для пяти данных целых чисел.

Recur11.^{[Pascal] [C#] [VB.NET]} Описать рекурсивную функцию MaxElem(A, N) целого типа, которая находит максимальный элемент целочисленного массива A размера N (1 ≤ N ≤ 10), не используя оператор цикла. С помощью этой функции найти максимальные элементы массивов A, B, C размера N_A, N_B, N_C соответственно.

Recur12.^{[Pascal] [C#] [VB.NET]} Описать рекурсивную функцию DigitCount(S) целого типа, которая находит количество цифр в строке S, не используя оператор цикла. С помощью этой функции найти количество цифр в каждой из пяти данных строк.

Recur13.^{[Pascal] [C#] [VB.NET]} Описать рекурсивную функцию Palindrome(S) логического типа, возвращающую True, если строка S является палиндромом (т. е. читается одинаково слева направо и справа налево), и False в противном случае. Оператор цикла в теле функции не использовать. Вывести значения функции Palindrome для пяти данных строк.

Рекурсия: разбор выражений

Во всех заданиях данной подгруппы предполагается, что исходные строки, определяющие выражения, не содержат пробелов.

При выполнении заданий не следует использовать оператор цикла.

Recur14°.^{[Pascal] [C#] [VB.NET]} Вывести значение целочисленного выражения, заданного в виде строки S. Выражение определяется следующим образом:

Recur15°.^{[Pascal] [C#] [VB.NET]} Вывести значение целочисленного выражения, заданного в виде строки S. Выражение определяется следующим образом:

Recur16°.^{[Pascal] [C#] [VB.NET]} Вывести значение целочисленного выражения, заданного в виде строки S. Выражение определяется следующим образом:

Recur17°.^{[Pascal] [C#] [VB.NET]} Вывести значение целочисленного выражения, заданного в виде строки S. Выражение определяется следующим образом:

Recur18°.^{[Pascal] [C#] [VB.NET]} Проверить правильность выражения, заданного в виде непустой строки S (выражение определяется по тем же правилам, что и в задании Recur17). Если выражение составлено правильно, то вывести True, иначе вывести False.

Recur19.^{[Pascal] [C#] [VB.NET]} Проверить правильность выражения, заданного в виде непустой строки S (выражение определяется по тем же правилам, что и в задании Recur17). Если выражение составлено правильно, то вывести 0, в противном случае вывести номер первого ошибочного, лишнего или недостающего символа в строке S.

Recur20.^{[Pascal] [C#] [VB.NET]} Вывести значение целочисленного выражения, заданного в виде строки S. Выражение определяется следующим образом (функция M возвращает максимальный из своих параметров, а функция m — минимальный):

Recur21°.^{[Pascal] [C#] [VB.NET]} Вывести значение логического выражения, заданного в виде строки S. Выражение определяется следующим образом («T» — True, «F» — False):

Recur22.^{[Pascal] [C#] [VB.NET]} Вывести значение целочисленного выражения, заданного в виде строки S. Выражение определяется следующим образом (функция M возвращает максимальный из своих параметров, а функция m — минимальный):

Recur23.^{[Pascal] [C#] [VB.NET]} Вывести значение логического выражения, заданного в виде строки S. Выражение определяется следующим образом («T» — True, «F» — False):

Recur24.^{[Pascal] [C#] [VB.NET]} Вывести значение логического выражения, заданного в виде строки S. Выражение определяется следующим образом («T» — True, «F» — False):

Рекурсия: перебор с возвратом

Recur25°.^{[Pascal] [C#] [VB.NET]} Дано дерево глубины N, каждая внутренняя вершина которого имеет K (< 10) непосредственных потомков (нумеруются от 1 до K). Корень дерева имеет номер 0. Записать в текстовый файл с данным именем все возможные пути, ведущие от корня к листьям. Перебирать пути, начиная с «самого левого» и заканчивая «самым правым» (при этом первыми заменять конечные элементы пути).

Recur26.^{[Pascal] [C#] [VB.NET]} Дано дерево глубины N, каждая внутренняя вершина которого имеет K (< 10) непосредственных потомков (нумеруются от 1 до K). Корень дерева имеет номер 0. Записать в текстовый файл с данным именем все пути, ведущие от корня к листьям и удовлетворяющие следующему условию: никакие соседние элементы пути не нумеруются одной и той же цифрой. Порядок перебора путей такой же, как в задании Recur25.

Recur27°.^{[Pascal] [C#] [VB.NET]} Дано дерево глубины N (N — четное), каждая внутренняя вершина которого имеет 2 непосредственных потомка: A с весом 1 и B с весом −1. Корень дерева C имеет вес 0. Записать в текстовый файл с данным именем все пути от корня к листьям, удовлетворяющие следующему условию: суммарный вес элементов пути равен 0. Порядок перебора путей такой же, как в задании Recur25.

Recur28.^{[Pascal] [C#] [VB.NET]} Дано дерево глубины N того же типа, что и в задании Recur27. Записать в текстовый файл с данным именем все пути от корня к листьям, удовлетворяющие следующему условию: суммарный вес элементов для любого начального отрезка пути неотрицателен. Порядок перебора путей такой же, как в задании Recur25.

Recur29.^{[Pascal] [C#] [VB.NET]} Дано дерево глубины N, каждая внутренняя вершина которого имеет 3 непосредственных потомка: A с весом 1, B с весом 0 и C с весом −1. Корень дерева D имеет вес 0. Записать в текстовый файл с данным именем все пути от корня к листьям, удовлетворяющие следующим условиям: суммарный вес элементов для любого начального отрезка пути неположителен, а суммарный вес всех элементов пути равен 0. Порядок перебора путей такой же, как в задании Recur25.

Recur30.^{[Pascal] [C#] [VB.NET]} Дано дерево глубины N того же типа, что и в задании Recur29. Записать в текстовый файл с данным именем все пути от корня к листьям, удовлетворяющие следующим условиям: никакие соседние элементы пути не обозначаются одной и той же буквой, а суммарный вес всех элементов пути равен 0. Порядок перебора путей такой же, как в задании Recur25.