Файл: Рекурсивные и итерационные алгоритмы: особенности и примеры использования (Определение итерационного алгоритма).pdf

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

3. Практика использования рекурсии и итерации

3.1. Практическое применение рекурсии на примере решения экономической задачи

Применим рекурсивный алгоритм к расчету банковских процентов по вкладу.

Вкладчик кладет в банк некоторую сумму под некоторые проценты на некоторый период. Требуется найти ту сумму, которую вкладчик сможет получить по окончании срока вклада.

Обозначим:

s-начальная сумма вклада

p-процентная ставка банка

per-период, на который положен вклад

Рекурсия расчета:

Если pеr=0, то gеt_totаl_sum := sum

Иначе sum := sum + gеt_pеrсents(sum, perс);

get_tоtal_sum := gеt_totаl_sum(sum, perс, per - 1);

В нашем случае get_total_sum-рекурсивная функция.

Код программы

var s,p,per:integer;

function get_perc(const val, perc: Single): Single;

begin

get_perc:= perc * val/100;

end;

function get_total_sum(sum, perc: Single; period: Integer): Single;

begin

if period = 0 then

get_total_sum := sum

else begin

sum := sum + get_perc(sum, perc);

get_total_sum := get_total_sum(sum, perc, period - 1);

end;

end;

begin

write ('введите начальную сумму вклада ');

readln(s);

write ('введите процентную ставку ');

readln(p);

write ('введите период ');

readln(per);

writeln('вклад достигнет суммы = ',get_total_sum(s, p, per):0:2);

readln;

end.

Блок-схема алгоритма

get_total_sum

period = 0

Да

get_total_sum := sum

sum := sum + get_percents(sum, percent)

get_total_sum := get_total_sum(sum, percent, period - 1)

Конец

Рисунок 18 - Блок-схема рекурсивной функции get_total_sum

get_percents

get_percents := percent * value / 100

Конец

Рисунок 19 - Блок-схема get_percent

Начало

'введите начальную сумму вклада '

s

'введите процентную ставку '

p

'введите период '

per

'вклад достигнет суммы = ',get_total_sum(s, p, per):0:2

Конец

Рисунок 20 - Блок-схема основной программы

Тестирующий пример

введите начальную сумму вклада 10000

введите процентную ставку 15

введите период 5

вклад достигнет суммы = 20113.57

Демонстрация работы программы представлена на рисунке 21.

Рисунок 21 - Демонстрация работы тестового примера в программе

Разработанная программа показывает, что запись алгоритма с использованием рекурсии компактен, понятен и прост при чтении. При расчете банковских процентов на любом современном компьютере будет достаточно стековой памяти для развертывания рекурсии. Приведенный рекурсивный алгоритм является оптимальным.

3.2. Практическое применение рекурсии на примере нахождения корней квадратного уравнения методом половинчатого деления (Дихотомии)

Приведем пример решения уравнения y=x²-1 методом Дихотомии.

Для решения данной задачи необходимо знать интервал, в котором корень существует. Функция y(x)= x²-1 непрерывна на всей области своего определения и в частности, на интервале [a,b]. Для простоты считать, что отрезок [a,b] задается таким образом, что корень на нем есть (иначе основная программа должна содержать проверку наличия корня).

Метод половинного деления для непрерывных функций заключается в следующем:

Базисное утверждение: Если абсолютная величина функции в середине отрезка не превышает заданного значения точности, то координата середины отрезка и есть корень.

Проверка наличия корня осуществляется по смене знака функции на концах отрезка. Если знаки функции на концах отрезка различны, то на отрезке корень есть.

Рекурсивное утверждение: Корень расположен между серединой отрезка и тем концом, значение функции в котором по знаку не совпадает со значением функции в середине отрезка.

Код программы

program dixotomi;

var a,b,e,x:real;

procedure ro(a,b,e:real;var r:real);

var f,x:real;

begin x:=(a+b)/2;

f:=x*x-1;

if abs(f)>e then

begin

if (a*a-1)*f>0 then ro(x,b,e,r)

else ro(a,x,e,r)

end;

end;

begin

readln(a,b,e);

ro(a,b,e,x);

writeln(x);

end.

Тестирующий пример

0 3

0.0001

1

Корень существует на данном отрезке и равен 1.

Блок-схема алгоритма приведена на рисунке 22.

ro

x:=(a+b)/2

f:=x*x-1

abs(f)>e

Да

(a*a-1)*f>0

Да

ro(x,b,e,r)

ro(a,x,e,r)

Конец

Рисунок 22 Метод Дихотомии

Фрагмент кода рекурсии приведен ниже:

procedure ro(a,b,e:real;var r:real);

var f,x:real;

begin x:=(a+b)/2;

f:=x*x-1;

if abs(f)>e then

begin

if (a*a-1)*f>0 then ro(x,b,e,r)

else ro(a,x,e,r)

end;

end;

Рекурсивная процедура ro вызывает сама себя в процессе обработки данных.

3.3. Практическое применение рекурсии на примере фракталов

Применение рекурсии в построении геометрических фракталов началось в конце 70-х годов. Все фигуры самоподобны, т.е. увеличенные части объекта походят на сам объект и друг на друга.

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

На рисунке 23 приведен пример программы, рисующей фракталы.

Рисунок 23 Фракталы (N=10)

Код программы

uses GraphABC;

procedure Pifagor(x0, y0, a, L: real; N: integer);

const k = 0.6; { изменение длины }

var x1, y1: real; { локальные переменные }

begin

if N > 0 then begin

x1 := x0 + L*cos(a);

y1 := y0 - L*sin(a);

Line(round(x0), round(y0),

round(x1), round(y1));

Pifagor (x1, y1, a+pi/4, L*k, N-1);

Pifagor (x1, y1, a-pi/4, L*k, N-1);

end;

end;

begin

Pifagor (250, 400, pi/2, 100, 10);

end.

На рисунке 18 приведена блок-схема алгоритма.

Pifagor

N > 0

Да

x1 := x0 + L*cos(a)

y1 := y0 - L*sin(a)

Line(round(x0), round(y0),

round(x1), round(y1))

Pifagor (x1, y1, a+pi/4, L*k, N-1)

Pifagor (x1, y1, a-pi/4, L*k, N-1)

Конец

Рисунок 24 Блок-схема фрактала

Рекурсивная процедура вызывается один раз в теле программы

Pifagor (250, 400, pi/2, 100, 10) и алгоритм выполняется 10 раз.

На рисунке 25 приведен пример выполнения алгоритма 5 раз.

Рисунок 25 Фрактал (N=5 )

3.4. Практическое применение итерации на примере применения метода Дихотомии

Вычислим корень уравнения y= cos x-x с заданной точностью e=0.001.

Код программы:

function F(x:real):real;

begin

F:=x*x-1;

end;

var a,b,c,x,e:real;

begin

a:=0;

b:=1;

e:=0.0001;

repeat

c:=(a+b)/2;

if F(a)*F(c)<=0 then b:=c

else a:=c;

until abs(b-a)<e;

x:=(a+b)/2;

writeln('Для уравнения y=x*x-1');

writeln ('В интервале от 0 до 1 с погрешностью 0.0001');

writeln ('x=',x:0:4);

end.

Вывод программы

Для уравнения y=x*x-1

В интервале от 0 до 1 с погрешностью 0.0001

x=1.0000

Рисунок 26 - Тестирующий пример

В пункте 3.2. приведено решение этого примера с помощью рекурсии. Ответы совпадают с точностью е=0.0001.

3.5. Практическое применение итерации на примере вычисления факториала

Приведем механизм итераций для вычисления факториала натурального числа. Факториал вычисляется следующим образом:

N! = 1 * 2 * 3 * … * (N-1) * N (1)

Факториал представляет собой произведение натуральных чисел от 1 до N включительно. Запишем формулу (1) в виде итерации.

N_i=N_i-1*N

Где N₀=1

Код программы

var

n, i, s: integer;

begin

read(n);

s := 1;i:=1;

while i <=n do

begin

s := s * i;

i:=i+1;

end;

writeln(s);

end.

Тестирующий пример

5

120

Рисунок 27 - Вычисление факториала

Заключение

При работе с информацией требуются нестандартные решения программистов. Исследование заключается в том, что бы сравнить итерационные методы решения с рекурсивным подходом в программировании.

Вывод: любую задачу можно решить с использованием итерационного алгоритма и рекурсии. Рекурсия позволяет создавать "понятные" и "читаемые" алгоритмы, быстро сходящиеся, но необходимо грамотно использовать рекурсивные методы вместо простых итерационных алгоритмов. Правильность работы рекурсии зависит от технических характеристик компьютера. Процессор не может обеспечить бесконечный рекурсивный спуск вниз, необходимо создавать промежуточные точки выхода из рекурсии, позволяющие проводить анализ правильности работы алгоритма. Итерационные алгоритмы используются при реализации итерационных численных методов. В итерационных алгоритмах необходимо обеспечить обязательное достижение условия выхода из цикла (сходимость итерационного процесса).

В работе проведен анализ научных источников по теме «Рекурсивные и итерационные алгоритмы: особенности и примеры использования»; описаны принципы написания итерационных алгоритмов; описаны принципы написания рекурсивных алгоритмов; разобраны примеры задач с итерационным методом решения и рекурсии; проведено сравнение работы итерационных алгоритмов и рекурсии.

Само понятие рекурсии отражает черту абстрактного мышления, проявляющуюся в самых различных областях науки: математике, геометрии, биологии, физике, синтаксическом анализе и трансляции, древовидной сортировке и обработке данных с динамической структурой, шахматных задачах, задачах с лабиринтами, генетических алгоритмах. Рекурсия избавляет программиста от необходимости последовательного описания процессов, благодаря чему уменьшается код программы и трудоемкость программиста по созданию алгоритма. Большим успехом в программировании считается то, что практически все современные языки программирования поддерживают рекурсию. Недостатком рекурсивного алгоритма может быть нехватка свободной оперативной памяти компьютера для развертывания всего рекурсивного механизма задачи. Но, с этим недостатком можно справиться, если производить промежуточный вывод результата и проводить его анализ.

Итерационные методы при не сходимости приводят к зацикливанию программы, что сразу видит программист.