1. С помощью рекурсивной функции найдите с заданной точностью квадратный корень , воспользовавшись итерационной формулой Ньютона:
Y0=1
Вычисления производите пока |Yi – Yi-1| не станет меньше заданного EPS..
Используя эту функцию, составьте другую рекурсивную функцию, которая для заданного а вычисляет
.
2. Разработайте рекурсивную функцию нахождения наибольшего общего делителя двух чисел m и n, используя алгоритм Евклида ( например, НОД(96, 36) : 96 = 2 · 36 + 24; 36 = 1 · 24 +12; 24 = 2 · 12 + 0. Следовательно, НОД(96, 36) = 12). Используя эту функцию, составьте вторую рекурсивную функцию для нахождения наибольшего общего делителя натуральных чисел а1, а2, … аn.одномерного массива.
3. Найдите количество n-значных чисел в m-ичной системе счисления, у каждого из которых сумма цифр равна k. При этом в качестве n-значного числа мы допускаем и числа, начинающиеся с одного или нескольких нулей.
4. Вычислите количество различных представлений заданного натурального числа n в виде суммы не менее двух попарно различных натуральных слагаемых. Представления, отличающиеся лишь порядком слагаемых, различными не считаются.
5. Дана матрица a(m, n), состоящая из нулей и единиц. Найдите в ней прямоугольную подматрицу из одних единиц максимального размера (т.е. с максимальным произведением высоты на длину).
6. Дана матрица a(m, n). Найдите в ней прямоугольную подматрицу, сумма элементов которой максимальна.
7. Дана матрица a(m, n). Найдите в ней путь от элемента a[i1, j1] до элемента a[i2, j2] с максимальной суммой. Ходить можно по горизонталям и вертикалям. Каждый элемент матрицы может входить в путь не более одного раза.
8. Дана матрица a(m, n). Найдите в ней путь от элемента первой строки матрицы до элемента последней строки с максимальной суммой. Ходить можно вниз по вертикали или диагоналям.
9. Вычислите определитель заданной матрицы, пользуясь формулой разложения по первой строке:
где матрица Вk получается из матрицы А вычеркиванием первой строки и k-го столбца.
10. Лабиринт задан матрицей a(m, n), состоящей из нулей и единиц, причем а[1, 1] = 0 и a[m, n] = 0. Разработайте рекурсивную процедуру нахождения пути из клетки а[1, 1] в a[m, n]. Путь должен состоять из элементов, равных нулю. Ходить можно только по вертикалям и горизонталям.
11. Задано число А и два вектора b[1..n] и c[1..n]. Найдите множество I, являющееся подмножеством множества {1, ..., n}, такое, что , а является максимальной из всех возможных.
12. Разработайте рекурсивную функцию, находящую сумму двух натуральных чисел, заданных массивами своих цифр а1, а2, …, аn и b1, b2, …, bm.
13. Разработайте рекурсивную функцию сортировки одномерного массива методом слияния.
14. Дано n различных натуральных чисел. Разработайте рекурсивную функцию формирования всех перестановок этих чисел.
15. Даны два натуральных числа m и n. Найдите НОД(m, n) и натуральные x и y такие, что mx + ny = НОД(m, n).
16. Даны три натуральных числа m, n и k, причем k делится на НОД(m, n). Найдите какое-нибудь целочисленное решение уравнения mx + ny = k.
17. Имеется n населенных пунктов, пронумерованных от 1 до n. Некоторые пары пунктов соединены дорогами. Разработайте рекурсивную процедуру определения, можно ли попасть по этим дорогам из 1-го пункта в n-й.
18. Вводятся три неотрицательных числа d, i, c и две строки X и Y. Найдите преобразование строки X в Y минимальной стоимости. Допустимы следующие три операции:
- удалить любой символ из X (стоимость операции d);
- вставить любой символ в X (стоимость операции i);
- заменить символ в X на произвольный (стоимость операции с).
19. Строка символов состоит из букв А, В и С. Разработайте рекурсивную функцию, преобразующую данную строку по правилам:
а) удаляет четыре подряд идущие буквы А;
б) удаляет из последовательности ВАВА одну пару ВА;
в) удаляет комбинацию АВС.
Преобразования выполняйте до тех пор, пока ни одной из перечисленных комбинаций не останется.
20. Даны две строки x и y. Строка x состоит из нулей и единиц, строка y – из символов A и B. Можно ли строку x преобразовать в строку y по следующему правилу: цифра 0 преобразуется в непустую последовательность букв A, а цифра 1 – либо в непустую последовательность букв A, либо в непустую последовательность букв B?
21. Задано конечное множество жителей некоего города, причем для каждого из жителей перечислены имена его детей. Жители X и Y считаются родственниками, если:
а) либо Х – ребенок Y,
б) либо Y – ребенок X,
в) либо существует некий Z такой, что Х является родственником Z, а Z является родственником Y.
Перечислите все пары жителей города, которые являются родственниками.
22. На шахматной доске расставьте 8 ферзей так, чтобы они не «били» друг друга.
23. Имеется полоска клетчатой бумаги шириной в одну клетку и длиной в n клеток. На первой клетке установлена шашка. Одним ходом шашку можно передвигать на одну или две клетки. Разработайте рекурсивную функцию, определяющую количество способов продвижения шашки на n-ю клетку.
, воспользовавшись итерационной формулой Ньютона:
.
, а 
является максимальной из всех возможных.