Лабораторная работа №9 Программирование с использованием рекурсии

9.1. Понятие рекурсии

Решить задачу рекурсивно – это значит разложить ее на подзадачи, которые затем аналогичным образом (т. е. рекурсивно) разбиваются на еще меньшие подзадачи. На определенном уровне подзадачи становятся настолько простыми, что могут быть решены тривиально.

В рекурсивном алгоритме важно предусмотреть способ его остановки, т.е. ввести условие, при котором рекурсивное обращение к функции прекращается.

9.2. Пример выполнения работы

Вычислить среднее значение элементов одномерного массива.

#include <iostream.h>

double Mean_rec(double *A, int n); //прототип рекурсивной функции

double Mean_cyc(double *A, int n); //прототип нерекурсивной функции

void main()

{

double A[10];

int n;

cout << "Enter a size of vector: ";

cin >> n;

cout << "Enter elements of vector:";

for (int i=0; i < n; i++)

cin >> A[i];

cout <<"The mean value by the recursion:";

cout << Mean_rec(A, n) << endl;

cout <<"The mean value by the cycle:";

cout << Mean_cyc(A, n) << endl;

return;

}

double Mean_rec(double *A, int n)

{

if (n > 0)

return A[n - 1] / n + Mean_rec(A, n - 1) * (n - 1) / n;

else

return A[n] / 2;

}

double Mean_cyc(double *A, int n)

{

double mean = 0;

for (int j=0; j < n; j++)

mean = (mean * j + A[j]) / (j + 1);

return mean;

}

9.3. Индивидуальные задания

Решить задачу двумя способами – с применением рекурсии и без нее.

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

1. Вычислить значение выражения при заданном положительном n:

. Последнее значение должно быть равно 0 или 1.

2. Вычислить произведение элементов трехмерного массива.

3. Подсчитать количество цифр в двух заданных целых числах. Не использовать функции работы со строками.

4. В упорядоченном по убыванию массиве положительных чисел a_i, i = 1 ... n найти номер элемента c методом бинарного поиска, используя очевидное соотношение: если , тогда , иначе . Если номер элемента c не найден, то все элементы увеличить в 2 раза.

5. Найти наибольший общий делитель (НОД) чисел M, N и K, используя метод Эйлера: если все K, M, N делятся на Z = min(K, M, N), то НОД (K, M, N) = Z, иначе НОД (K, M, N) = НОД (A % Z, B % Z, Z), где A и B – не равные Z числа.

6. Вычислить значение , используя формулу вычисления квадратного корня , в качестве начального приближения для данной формулы использовать значение .

7. Найти минимальный элемент в массиве a₁, ..., a_n, используя метод деления пополам min (a₁, ..., a_n) = min (min (a₁, ..., a_n/2), min (a_n/2+1, ..., a_n)).

8. Вычислить для четных чисел и для нечетных чисел.

9. Вычислить значение суммы

10. Проверить, является ли заданная строка палиндромом (как обычным палиндромом, так и читаемым в прямом направлении).

11. Подсчитать количество цифр в заданном числе с фиксированной точкой. Не использовать функции работы со строками.

12. Вычислить число Фибоначчи Fb(n). Числа Фибоначчи определяются следующим образом: Fb(0)=1; Fb(1)=1; Fb(n)=Fb(n-1)+Fb(n-2).

13. Вычислить значение выражения , используя для подсчета целых чисел сумму чисел 2 в положительных степенях, а для дробей - в отрицательных степенях. Число разлаживается в ряд .

14. Вычислить значение , используя формулу вычисления кубического корня , в качестве начального приближения для данной формулы использовать значение .

15. Реализовать вычисление натурального числа, которое может стать палиндромом с помощью итеративного процесса «отразить и сложить». Например: 53+35=88. Для разных чисел требуется разное количество итерацией. Алгоритм будет корректно работать до числа 195 включительно.