Лабораторная работа №9 Программирование с использованием рекурсии
9.1. Понятие рекурсии
Решить задачу рекурсивно – это значит разложить ее на подзадачи, которые затем аналогичным образом (т. е. рекурсивно) разбиваются на еще меньшие подзадачи. На определенном уровне подзадачи становятся настолько простыми, что могут быть решены тривиально.
В рекурсивном алгоритме важно предусмотреть способ его остановки, т.е. ввести условие, при котором рекурсивное обращение к функции прекращается.
9.2. Пример выполнения работы
Условие
1. Написать программу для вычисления
двумя методами. Один метод вычисляет
сумму без использования рекурсии, другой
с использованием
рекурсии.
#include <iostream.h>
#include <math.h>
double sum(int);
double sumr(int);
int main ()
{
int n;
cout << "vvedite n "; cin >> n;
cout << "s (ne rekurs) = " << sum(n) << endl;
cout << "s (rekurs) = " << sumr(n) << endl;
return 0;
}
double sum(int n)
{
for (double s=0, int i=1; i<=n; i++) s += (pow(i+1,2))/i;
return s;
}
double sumr(int n)
{
if (n==1) return 4;
else return sumr(n-1)+pow(n+1,2)/n;
}
Условие 2. Найти max (a1, ..., an), разбив задачу на элементарные подзадачи: max(max (max (a1...an–2), an–1), an), … .
int maxr2(int i)
{
if (i==0) return a[0];
else {
int mx=maxr2(i-1);
if (a[i]>mx) return a[i];
else return mx;
}
}
Условие 3. Задача о Ханойской башне. Имеется три стержня s1, s2, s3. На первом из них нанизаны n дисков различных диаметров, образующих правильную пирамиду – чем выше расположен диск, тем меньше его диаметр. Требуется переместить всю башню на второй стержень, причем диски можно переносить по одному, нельзя помещать диск на диск меньшего диаметра, для промежуточного хранения можно использовать третий диск.
void hanr(int n, int s1, int s2, int s3)
{
if (n>0) {
Hanr(n-1,s1,s3,s2);
cout << "perenesty s "<<s1<<" na "<<s2<<endl;
Hanr(n-1,s3,s2,s1);
}
}
9.3. Индивидуальные задания
Решить задачу двумя способами – с применением рекурсии и без нее.
1. Вычислить среднее значение элементов одномерного массива.
2. Вычислить произведение элементов одномерного массива.
3. Подсчитать количество цифр в заданном числе.
4. В
упорядоченном массиве целых чисел ai,
i = 1 ... n
найти номер элемента c
методом бинарного поиска, используя
очевидное соотношение: если
,
тогда
,
иначе
.
Если элемент c
отсутствует в массиве, то вывести
соответствующее сообщение.
5. Найти наибольший общий делитель чисел M и N используя метод Эйлера: если M делится на N, то НОД (N, M) = N, иначе НОД (N, M) = = НОД (M % N, N).
6. Вычислить значение полинома степени n по формуле
.
7.
Вычислить значение
,
используя формулу
,
в качестве начального приближения
использовать значение x0
= (1+a)/2.
8. Найти максимальный элемент в массиве a1, ..., an, используя метод деления пополам max (a1, ..., an) = max (max (a1, ..., an/2), max (an/2+1, ..., an)).
9.
Вычислить
.
10. Вычислить произведение n 2 (n четное) сомножителей
11.
Вычислить
по следующему алгоритму:
,
если N четное;
,
если N нечетное.
12.
Вычислить
13.
Вычислить произведение двух целых
положительных чисел
по следующему алгоритму:
,
если b четное;
,
если b нечетное.
Если b = 0, то p
= 0.
14. Вычислить значение суммы S = 1/1! + 1/2! + ... + 1/k!
15. Проверить, является ли заданная строка палиндромом.