Лабораторная работа № 5. Рекурсивные алгоритмы

Рекурсия - это такая организация работы, при которой функция вызывает сама себя.

Задание	Краткие теоретические сведения
1. Изучить использование простых рекурсивных функций на примере программы, представленной в правой части. Определить признак конца ввода чисел, проанализировав текст программы. Добавить операторы, позволяющие определить, сколько раз функция binPrn вызывает сама себя.	Пример программы перевода десятичного числа в двоичный вид с использованием рекурсии.
2. Выполнить програм-му, разработанную с использованием рекурсии. Реализовать алгоритм без использования рекурсии.	Пример. Определить, является ли заданная строка палиндромом, т.е. читается одинаково слева направо и справа налево. Идея решения заключается в просмотре строки одновременно слева направо и справа налево и сравнении соответствующих символов. Если в какой-то момент символы не совпадают, делается вывод о том, что строка не является палиндромом, если же удается достичь середины строки и при этом все соответствующие символы совпали, то строка является палиндромом. Граничное условие - строка является палиндромом, если она пустая или состоит из одного символа.
3. Выполнить программу, приведенную в правой части. Записать ее условие. Добавить любое слово в массив w и проанализировать результат работы программы. Добавить операторы вывода сообщения о том, что некоторое слово в массиве w не подходит и его нужно изменить.	#include <iostream> using namespace std; char *w[]={"ПАЛКА","ЛЯГУШКА", "КАПЛЯ", "КАРТА", NULL}; int TEST(char *s, char *r) { int n; n=strlen(s); if (n==0) return 1; for (;*s!=0 && n>1; s++,n--) if (strncmp(s,r,n)==0) return 1; return 0; } int step(char *lw)// текущее слово { setlocale (LC_CTYPE, "Russian"); int n; for (n=0; w[n]!=NULL;n++) if (*w[n]!=0) break; if (w[n]==NULL)// цепочка выстроена return 1;   for (n=0; w[n]!=NULL;n++) { char *pw; if (*w[n]==0) continue; pw=w[n];// пустое слово - пропустить w[n]=""; if (TEST(lw, pw)) { if (step(pw))//присоединено { cout << pw << "\n"; return 1; } } w[n]=pw } return 0; } void main() { step(""); }

4. В соответствии со своим вариантом выполнить задания из таблицы, представленной ниже.

5. К номеру своего варианта прибавить число 2 и написать программу для новых исходных данных (для вариантов с 15 по 16 перейти к вариантам с 1 по 2).

№	Условие задачи	Пояснения к алгоритму
1, 2	Разработать программу, реализующую рекурсивную функцию подсчета количества x(m) разбиений натурального числа m в виде суммы натуральных чисел.	Для m = 4 разбиения: 4, 3+1, 2+2, 2+1+1, 1+1+1+1. Таким образом, x(m) = 5. Функция подсчета P(m, n) количества разбиений натурального числа m со слагаемыми, не превосходящими n, определяется следующим образом: При этом x(m) = P(m,m).
3, 4	Разработать программу, реализующую рекурсивную функцию f(x, n), вычисляющую величину xn/n! при любом вещественном x и любом неотрицательном целом n.	Для вычисления xn-1/(n-1)! надо рекурсивно обратиться к f(x, n-1), а затем полученную величину умножить на x/n, чтобы получить значение f(x, n). Функция f(x, n)принимает следующий вид:
5, 6	Разработать программу, реализующую рекурсивную функцию подсчета количества всех положительных делителей натурального числа n.	Рассмотрим более общую задачу подсчета для натурального числа n количества всех его положительных делителей, меньших или равных заданному натуральному числу x. Пусть dn(n) и dnx(n, x) - соответственно функции для решения исходной и обобщенной задач. Рекурсивную функцию dnx(n, x), по которой последовательно подвергаются испытанию на делители n все числа от 1 до x включительно, можно определить так: Очевидно, что dn(n) = dnx(n, n).
7, 8	Задан прямоугольник со сторонами а и b (a, b - натуральные числа). Разбить его на части с помощью квадратов. Определить, сколько квадратов получится, если каждый раз выбирается самый большой квадрат.	Пусть, например, a > b. Тогда, отрезав от прямоугольника floor(a/b) квадратов со сторонами длиной b, снова окажемся перед исходной задачей, в которой a = b и b = mod(a, b) (b = a - floor(a / b) × b). В качестве базы рекурсии можно взять случай b = 0. Если numsq(a, b) - функция, возвращающая решение задачи при заданных длинах a и b сторон исходного прямоугольника, то
9, 10	Рекурсивно описать функцию C(m, n), где 0<=m<=n, для биноминального коэффициента Сn.	Формулы имеют следующий вид: Сno= Сnn= 1; Сnm= Сn-1m+ Сn-1m-1
11, 12	Для целых неотрицательных чисел n, m разрешены операции: нахождения последующего числа (n + 1) и предыдущего числа n-1 (n > 0). Промоделировать с помощью рекурсивных функций операции нахождения суммы (n + m), разности (n - m),умножения (n × m), возведения в степень n ^ m (n > 0)	Для суммы a + b очевидно соотношение: Оно задает одновременно и базу рекурсии и правило декомпозиции. По нему построена следующая рекурсивная функция: Для разности: Умножение: Возведение в степень:
13, 14	Пусть функция f(x) вещественной переменной x непрерывна на отрезке [a, b] и f(a)×f(b) < 0. Разработать рекурсивную программу нахождения на отрезке [a, b] какого-либо вещественного корня.	Для определения корня можно использовать метод деления отрезка пополам. С использованием рекурсии: Здесь e-заданная точность решения.
15, 16	Разработать программу, реализующую рекурсивный алгоритм для вычисления значений полиномов по определенной функции.	Функция имеет следующий вид:

В начало практикума