Простейшие рекурсивные алгоритмы

Задания этого раздела можно легко решить и без использования рекур-

сии. Данное обстоятельство связано с тем, что в заданиях рассматриваются

простейшие примеры рекурсии, легко сводимые к итерационным алгоритмам.

Более того, в некоторых случаях непосредственные вычисления по рекурсив-

ным формулам оказываются весьма неэффективными (см., например, задания

Recur4 и Recur6). Однако именно на подобных примерах проще всего получить

первоначальные навыки разработки рекурсивных алгоритмов.

Recur1◦. Описать рекурсивную функцию Fact(N ) вещественного типа, вычис-

ляющую значение факториала

N ! = 1·2·. . .·N

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

факториалы пяти данных чисел.

Recur2. Описать рекурсивную функцию Fact2(N ) вещественного типа, вычис-

ляющую значение двойного факториала

Рекурсия

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

(N > 0 — параметр целого типа; последний сомножитель в произведении

равен 2, если N — четное число, и 1, если N — нечетное). С помощью

этой функции вычислить двойные факториалы пяти данных чисел.

Recur3. Описать рекурсивную функцию PowerN(X, N ) вещественного типа,

находящую значение N -й степени числа X по формулам:

X 0 = 1,

X N = (X N/2)2 при четных N > 0,

X N = X ·X N−1 при нечетных N > 0,

X N = 1/X −N при N < 0

(X6= 0 — вещественное число, N — целое; в формуле для четных N долж-

на использоваться операция целочисленного деления). С помощью этой

функции найти значения X N для данного X при пяти данных значени-

ях N.

Recur4◦ . Описать рекурсивную функцию Fib1(N ) целого типа, вычисляющую

N -й элемент последовательности чисел Фибоначчи (N — целое число):

F₁= F₂= 1,

F_K= F_K−2 + F_K−1 , K = 3, 4, . . . .

С помощью этой функции найти пять чисел Фибоначчи с данными но-

мерами, и вывести эти числа вместе с количеством рекурсивных вызовов

функции Fib1, потребовавшихся для их нахождения.

Recur5◦ . Описать рекурсивную функцию 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. Описать рекурсивную функцию 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, потребовавшихся для их

нахождения.

112

М. Э. Абрамян. Электронный задачник Programming Taskbook 4.6

Recur7. Описать рекурсивную функцию 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. Описать рекурсивную функцию 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. Описать рекурсивную функцию NOD(A, B) целого типа, находящую

наибольший общий делитель (НОД) двух целых положительных чисел A

и B, используя алгоритм Евклида:

НОД(A, B) = НОД(B, A mod B), если B6= 0;

НОД(A, 0) = A.

С помощью этой функции найти НОД(A, B), НОД(A, C), НОД(A, D), если

даны числа A, B, C, D.

Recur10◦. Описать рекурсивную функцию DigitSum(K) целого типа, которая

находит сумму цифр целого числа K, не используя оператор цикла. С

помощью этой функции найти суммы цифр для пяти данных целых чисел.

Recur11. Описать рекурсивную функцию MaxElem(A, N ) целого типа, кото-

рая находит максимальный элемент целочисленного массива A размера N

(1 ≤ N ≤ 10), не используя оператор цикла. С помощью этой функции

найти максимальные элементы массивов A, B, C размера N_A, N_B, N_C

соответственно.

Recur12. Описать рекурсивную функцию DigitCount(S) целого типа, которая

находит количество цифр в строке S, не используя оператор цикла. С

Рекурсия

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

строк.

Recur13. Описать рекурсивную функцию Palindrom(S) логического типа, воз-

вращающую TRUE, если строка S является палиндромом (то есть читается

одинаково слева направо и справа налево), и FALSE в противном случае.

Оператор цикла в теле функции не использовать. Вывести значения функ-

ции Palindrom для пяти данных строк.

Разбор выражений

Во всех заданиях данного пункта предполагается, что исходные строки,

определяющие выражения, не содержат пробелов. При выполнении заданий

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

Recur14◦ . Вывести значение целочисленного выражения, заданного в виде

строки S. Выражение определяется следующим образом:

<выражение> ::= <цифра> | <выражение> + <цифра> |

<выражение> − <цифра>

Recur15◦ . Вывести значение целочисленного выражения, заданного в виде

строки S. Выражение определяется следующим образом:

<выражение> ::= <терм> | <выражение> + <терм> |

<выражение> − <терм>

<терм>

::= <цифра> | <терм> * <цифра>

Recur16◦ . Вывести значение целочисленного выражения, заданного в виде

строки S. Выражение определяется следующим образом:

<выражение> ::= <терм> | <выражение> + <терм> |

<выражение> − <терм>

<терм>

<элемент>

::= <элемент> | <терм> * <элемент>

::= <цифра> | (<выражение>)

Recur17◦ . Вывести значение целочисленного выражения, заданного в виде

строки S. Выражение определяется следующим образом:

<выражение> ::= <цифра> |

(<выражение><знак><выражение>)

<знак>

::= + | − | *

Recur18◦ . Проверить правильность выражения, заданного в виде непустой

строки S (выражение определяется по тем же правилам, что и в задании

114

М. Э. Абрамян. Электронный задачник Programming Taskbook 4.6

Recur17). Если выражение составлено правильно, то вывести TRUE, иначе

вывести FALSE.

Recur19. Проверить правильность выражения, заданного в виде непустой

строки S (выражение определяется по тем же правилам, что и в зада-

нии Recur17). Если выражение составлено правильно, то вывести 0, в

противном случае вывести номер первого ошибочного, лишнего или недо-

стающего символа в строке S.

Recur20. Вывести значение целочисленного выражения, заданного в виде

строки S. Выражение определяется следующим образом (функция M воз-

вращает максимальный из своих параметров, а функция m — минималь-

ный):

<выражение> ::= <цифра> | M(<выражение> , <выражение>) |

m(<выражение> , <выражение>)

Recur21◦. Вывести значение логического выражения, заданного в виде стро-

ки S. Выражение определяется следующим образом («T» — TRUE, «F» —

FALSE):

<выражение> ::= T | F | And(<выражение> , <выражение>) |

Or(<выражение> , <выражение>)

Recur22. Вывести значение целочисленного выражения, заданного в виде

строки S. Выражение определяется следующим образом (функция M воз-

вращает максимальный из своих параметров, а функция m — минималь-

ный):

<выражение> ::= <цифра> | M(<параметры>) | m(<параметры>)

<параметры> ::= <выражение> | <выражение> , <параметры>

Recur23. Вывести значение логического выражения, заданного в виде стро-

ки S. Выражение определяется следующим образом («T» — TRUE, «F» —

FALSE):

<выражение> ::= T | F | And(<параметры>) | Or(<параметры>)

<параметры> ::= <выражение> | <выражение> , <параметры>

Recur24. Вывести значение логического выражения, заданного в виде стро-

ки S. Выражение определяется следующим образом («T» — TRUE, «F» —

FALSE):

<выражение> ::= T | F | And(<параметры>) |

Or(<параметры>) | Not(<выражение>)

<параметры> ::= <выражение> | <выражение> , <параметры>

Рекурсия

Перебор с возвратом

Recur25◦ . Дано дерево глубины N, каждая внутренняя вершина которого имеет

K (< 10) непосредственных потомков (нумеруются от 1 до K). Корень

дерева имеет номер 0. Записать в текстовый файл с данным именем все

возможные пути, ведущие от корня к листьям. Перебирать пути, начиная

с «самого левого» и заканчивая «самым правым» (при этом первыми

заменять конечные элементы пути).

Recur26. Дано дерево глубины N, каждая внутренняя вершина которого име-

ет K (< 10) непосредственных потомков (нумеруются от 1 до K). Корень

дерева имеет номер 0. Записать в текстовый файл с данным именем все

пути, ведущие от корня к листьям и удовлетворяющие следующему усло-

вию: никакие соседние элементы пути не нумеруются одной и той же

цифрой. Порядок перебора путей такой же, как в задании Recur25.

Recur27◦ . Дано дерево глубины N (N — четное), каждая внутренняя вершина

которого имеет 2 непосредственных потомка: A с весом 1 и B с весом −1.

Корень дерева C имеет вес 0. Записать в текстовый файл с данным именем

все пути от корня к листьям, удовлетворяющие следующему условию:

суммарный вес элементов пути равен 0. Порядок перебора путей такой

же, как в задании Recur25.

Recur28. Дано дерево глубины N того же типа, что и в задании Recur27.

Записать в текстовый файл с данным именем все пути от корня к листьям,

удовлетворяющие следующему условию: суммарный вес элементов для

любого начального отрезка пути неотрицателен. Порядок перебора путей

такой же, как в задании Recur25.

Recur29. Дано дерево глубины N, каждая внутренняя вершина которого имеет

3 непосредственных потомка: A с весом 1, B с весом 0 и C с весом −1.

Корень дерева D имеет вес 0. Записать в текстовый файл с данным име-

нем все пути от корня к листьям, удовлетворяющие следующим условиям:

суммарный вес элементов для любого начального отрезка пути неположи-

телен, а суммарный вес всех элементов пути равен 0. Порядок перебора

путей такой же, как в задании Recur25.

Recur30. Дано дерево глубины N того же типа, что и в задании Recur29. За-

писать в текстовый файл с данным именем все пути от корня к листьям,

удовлетворяющие следующим условиям: никакие соседние элементы пу-

ти не обозначаются одной и той же буквой, а суммарный вес всех эле-

ментов пути равен 0. Порядок перебора путей такой же, как в задании

116

Recur25.

М. Э. Абрамян. Электронный задачник Programming Taskbook 4.6