Пример 3 . Задача о коэффициентах Безу
Теоретический материал.
В окружающем нас мире часто можно встретить объекты, обладающие самоподобием. То есть часть большого объекта в чем-то сходна с самим объектом. Например, ветка дерева повторяет форму и характер ветвления, схожие с самим деревом. Приведенные ниже графические объекты также обладают самоподобием (рис. 3.1). Такие объекты называются рекурсивными.
Рис. 3.1. Рекурсивные графические объекты
Рекурсия в программировании – это пошаговое разбиение задачи на подзадачи, подобные исходной.
Рекурсивный алгоритм – это алгоритм, в определении которого содержится прямой или косвенный вызов этого же алгоритма.
Функция называется рекурсивной, если в своем теле она содержит обращение к самой себе с измененным набором параметров. При этом количество обращений конечно, так как в итоге решение сводится к базовому случаю, когда ответ очевиден.
Пример 1 . В арифметической прогрессии найдите an, если известны а1 = -2.5, d =0.4, не используя формулу n-го члена прогрессии.
По определению арифметической прогрессии, an=an-1+d, при этом
an-1=an-2+d, an-2=an-3+d,... a2=a1+d.
Таким образом, нахождение an для номера n сводится к решению аналогичной задачи, но только для номера n-1, что в свою очередь сводится к решению для номера n-2, и так далее, пока не будет достигнут номер 1 (значение а1 дано по условию задачи).
Float arifm (int n, float a, float d)
{
if (n<1)
Return 0; // для неположительных номеров
|
|
|
if (n==1)
return a; // базовый случай : n=1
return arifm(n-1,a,d)+d; // общий случай
}
В рекурсивных функциях несколько раз используется return. В базовом случае возвращается конкретный результат (в примере – значение а ), а общий случай предусматривает вызов функцией себя же, но с меняющимися значениями отдельных параметров (в примере изменяется только номер члена последовательности, при этом не меняются разность и первый член прогрессии).
Для решения задач рекурсивными методами разрабатывают следующие этапы, образующие рекурсивную триаду:
· параметризация – выделяют параметры, которые используются для описания условия задачи, а затем в решении;
· база рекурсии – определяют тривиальный случай, при котором решение очевидно, то есть не требуется обращение функции к себе;
· декомпозиция – выражают общий случай через более простые подзадачи с измененными параметрами.
Пример 2 . Для целого неотрицательного числа n найдите его факториал.
Разработаем рекурсивную триаду.
Параметризация: n – неотрицательное целое число.
База рекурсии: для n =0 факториал равен 1.
Декомпозиция: n!=(n-1)!*n.
Int Fact (int n)
{ if ( n <0)
return 0; // для отрицательных чисел
if ( n ==0) // базовый случай: n =0
|
|
|
return 1;
return n * Fact ( n -1); // (общий случай (декомпозиция)
}
Эффективность рекурсивного или итерационного способов решения одной и той же задачи определяется в ходе анализа работоспособности программы на различных наборах данных. Таким образом, рекурсия не является универсальным способом в программировании. Ее следует рассматривать как альтернативный вариант при разработке алгоритмов решения задач.
Область памяти, предназначенная для хранения всех промежуточных значений локальных переменных при каждом следующем рекурсивном обращении, образует рекурсивный стек. Для каждого текущего обращения формируется локальный слой данных стека (при этом совпадающие идентификаторы разных слоев стека независимы друг от друга и не отождествляются). Завершение вычислений происходит посредством восстановления значений данных каждого слоя в порядке, обратном рекурсивным обращениям. В силу подобной организации количество рекурсивных обращений ограничено размером области памяти, выделяемой под программный код. При заполнении всей предоставленной области памяти попытка вызова следующего рекурсивного обращения приводит к ошибке переполнения стека.
Рассмотрим задачи, для которых можно предложить рекурсивные алгоритмы решения, в то время как итерационные алгоритмы были бы сложными и искусственными.
|
|
|
Пример 3 . Задача о коэффициентах Безу
Для любых натуральных чисел n и m найдите коэффициенты Безу, то есть такие целые a и b, что выполняется равенство:
nod(n,m)=a*n+b*m,
(где nod(n,m) – наибольший общий делитель n и m ).
nod(12,30)=6=3*12+(-1)*30 = (-2)*12+1*30
Параметризация.
m, n – данные натуральные числа, неизменяемые параметры;
d – наибольший общий делитель данных чисел, неизменяемый параметр;
bm, bn – коэффициенты Безу при n и m соответственно, эти параметры меняются при очередном рекурсивном вызове функции.
База рекурсии. Если при очередном обращении к функции с передаваемыми параметрами выполняется равенство d=m*bm–n*bn, то коэффициенты Безу найдены. Требуется вывести линейную комбинацию.
Декомпозиция. Если равенство не выполняется, то инкрементно увеличиваем коэффициент при меньшем из чисел ( n или m ). Следующий вызов рекурсивной функции выполняется с измененным набором отдельных параметров. При этом снова проверяется база рекурсии, и рекурсивный алгоритм повторяется (либо достигается база и функция завершает работу, либо выполняется декомпозиционный переход).
|
|
|
//Коэффициенты Безу
#include <iostream>
#include <stdio.h>
using namespace std;
int nod(int m, int n);
void bezu(int d, int m, int n, int bm, int bn);
Int main()
{
int x,y,del,buf;
cout <<"\nВведите два натуральных числа:\ n ";
cout<<"X= ";cin>>x;
cout<<"Y= ";cin>>y;
if (x < y)
{buf = x; x = y; y = buf;}
del=nod(x,y);
cout<<"\n Линейная комбинация :\n");
bezu(del,x,y,1,1);
return 0;
}
//функция нахождения наибольшего общего делителя двух чисел
Int nod(int m, int n)
{
if (m%n==0)
return n;
return nod(n,m%n);
}
//функция нахождения и вывода на экран коэффициентов Безу
Дата добавления: 2021-05-18; просмотров: 159; Мы поможем в написании вашей работы! |
Мы поможем в написании ваших работ!