М. Э. Абрамян Programming Taskbook
Рекурсия Простейшие рекурсивные алгоритмы
жүктеу/скачать 0,52 Mb. Pdf көрінісі
|
Задачник Абрамяна
| Рекурсия
Простейшие рекурсивные алгоритмы Задания этого раздела можно легко решить и без использования рекур- сии. Данное обстоятельство связано с тем, что в заданиях рассматриваются простейшие примеры рекурсии, легко сводимые к итерационным алгоритмам. Более того, в некоторых случаях непосредственные вычисления по рекурсив- ным формулам оказываются весьма неэффективными (см., например, задания 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 (X 6= 0 — вещественное число, N — целое; в формуле для четных N долж- на использоваться операция целочисленного деления). С помощью этой функции найти значения X N для данного X при пяти данных значени- ях N. Recur4. Описать рекурсивную функцию Fib1(N) целого типа, вычисляющую N-й элемент последовательности чисел Фибоначчи (N — целое число): F 1 = F 2 = 1, F K = F K−2 + F K−1 , K = 3, 4, . . . . С помощью этой функции найти пять чисел Фибоначчи с данными но- мерами, и вывести эти числа вместе с количеством рекурсивных вызовов 106 М. Э. Абрамян. Электронный задачник Programming Taskbook 4.5 функции Fib1, потребовавшихся для их нахождения. Recur5. Описать рекурсивную функцию Fib2(N) целого типа, вычисляющую N-й элемент последовательности чисел Фибоначчи (N — целое число): F 1 = F 2 = 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, потребовавшихся для их нахождения. 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 0 = 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) — целые. Рекурсия 107 С помощью функции RootK найти для данного числа X приближенные значения его корня K-й степени при шести данных значениях N. Recur9. Описать рекурсивную функцию NOD(A, B) целого типа, находящую наибольший общий делитель (НОД) двух целых положительных чисел A и B, используя алгоритм Евклида: НОД(A, B) = НОД(B, A mod B), если B 6= 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 для пяти данных строк. жүктеу/скачать 0,52 Mb. Достарыңызбен бөлісу:
|