С. Задачи повышенной сложности

1. С помощью рекурсивной функции найдите с заданной точностью квадратный корень , воспользовавшись итерационной формулой Ньютона:

Y ₀=1

Вычисления производите пока |Y_i – Y_i-1| не станет меньше заданного EPS..

Используя эту функцию, составьте другую рекурсивную функцию, которая для заданного а вычисляет

.

2. Разработайте рекурсивную функцию нахождения наибольшего общего делителя двух чисел m и n, используя алгоритм Евклида (например, НОД(96, 36): 96 = 2 · 36 + 24; 36 = 1 · 24 +12; 24 = 2 · 12 + 0. Следовательно, НОД(96, 36) = 12). Используя эту функцию, составьте вторую рекурсивную функцию для нахождения наибольшего общего делителя натуральных чисел а ₁, а ₂, … а_n. одномерного массива.

НОД(n₁, n₂,... n_m) = НОД (НОД (n₁, n₂,... n_m–1), n_m)_.

3. Найдите количество n -значных чисел в m -ичной системе счисления, у каждого из которых сумма цифр равна k. При этом в качестве n- значного числа мы допускаем и числа, начинающиеся с одного или нескольких нулей.

4. Вычислите количество различных представлений заданного натурального числа n в виде суммы не менее двух попарно различных натуральных слагаемых. Представления, отличающиеся лишь порядком слагаемых, различными не считаются.

5. Дана матрица a (m, n), состоящая из нулей и единиц. Найдите в ней прямоугольную подматрицу из одних единиц максимального размера (т.е. с максимальным произведением высоты на длину).

6. Дана матрица a (m, n). Найдите в ней прямоугольную подматрицу, сумма элементов которой максимальна.

7. Дана матрица a (m, n). Найдите в ней путь от элемента a [ i 1, j 1] до элемента a [ i 2, j 2] с максимальной суммой. Ходить можно по горизонталям и вертикалям. Каждый элемент матрицы может входить в путь не более одного раза.

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. Разработайте рекурсивную функцию, находящую сумму двух натуральных чисел, заданных массивами своих цифр а ₁, а ₂, …, а_n и b ₁, b ₂, …, b_m.

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 -ю клетку.