IX Международная студенческая научная конференция Студенческий научный форум - 2017

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

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

Пример 1. Например, напишем программу для генерации натуральных чисел от 1 до a. Вспомним определение натурального числа – это либо 1, либо целое число, следующее за натуральным. Таким образом, функция генерации натуральных чисел должна принимать значение 1 при n=1 и вызывать саму себя с аргументом n-1, при n>1. Реализация программы приведена в листинге 1.

Листинг 1. Рекурсивная функция генерации простых чисел

function nat_chisla(n: integer):integer;

var a:integer;

begin

if (n=1) then begin

n:=1;

write(n,' ');end

else

begin

a:=nat_chisla(n-1);

write(n,' ');

end;

end;

var a: integer;

begin

readln(a);

a:=nat_chisla(a);

end.

Пример 2. Факториал:

Листинг 2. Рекурсивное определение факториала

functionfact(n: integer):integer;

var a:integer;

begin

if (n=0) then a:=1 else

a:=n*fact(n-1);

fact:=a;

end;

var a: integer;

begin

readln(a);

a:=fact(a);

write(a,' ');

end.

Пример 3. Числа Фибоначчи:

Листинг 3.Рекурсивное определение ряда чисел Фиббоначи

function fib(n:integer):integer;

var a:integer;

begin

if (n=0) or (n=1) then begin

a:=1; end

else

begin

a:=fib(n-1)+fib(n-2);

end;

fib:=a;

end;

var a,n,i: integer;

begin

readln(n);

for n:=1 to ndo

begin

a:=fib(n-1);

write(a, ' ');

end;

end.

Пример 4. Определение корней уравнения y=x²-2 на заданном отрезке методом половинного деления.

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

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

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

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

Листинг 4.Рекурсивное определение корня уравнения

методом половинного деления

program ex;

var a,b,eps,x:real;

procedure root(a,b,eps:real,var r):real;

var f,x:real;

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

f:=x*x-1;

if abs(f)>eps then

begin

if (a*a-1)*f>0 then root(x,b,eps,r)

else root(a,x,eps,r)

end;

end;

begin

readln(a,b,eps);

root(a,b,eps,x);

writeln(x);

end.

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

Понятия фрактал, фрактальная геометрия и фрактальная графика, появились в конце 70-х. Слово фрактал образовано от латинского fractus и в переводе означает «состоящий из фрагментов». Оно было предложено математиком Бенуа Мандельбротом в 1975 году для обозначения нерегулярных, но самоподобных структур. Рождение фрактальной геометрии принято связывать с выходом в 1977 году книги Мандельброта «The Fractal Geometry of Nature». В его работах использованы научные результаты других ученых, работавших в 1875 – 1925 годах в той же области (Пуанкаре, Фату, Жюлиа, Кантор, Хаусдорф). Но только в наше время удалось объединить их работы в единую систему. Определение фрактала, данное Мандельбротом: фракталом называется структура, состоящая из частей, которые в каком-то смысле подобны целому [5]. Самоподобие – одно из основных свойств фракталов. Объект называют самоподобным, когда увеличенные части объекта походят на сам объект и друг на друга.

Фрактал представляет собой сложную геометрическую фигуру, которая составлена из нескольких бесконечной последовательности частей, каждая из которых подобна всей фигуре целиком, и повторяется при уменьшении масштаба. В двухмерном случае их получают с помощью некоторой ломаной (или поверхности в трехмерном случае), называемой генератором. За один шаг алгоритма каждый из отрезков, составляющих ломаную, заменяется на ломаную-генератор, в соответствующем масштабе. В результате бесконечного повторения этой процедуры, получается геометрический фрактал.

Пример 5. Дерево Пифагора из N уровней – это ствол и отходящие от него симметрично два дерева Пифагора из N-1 уровней, такие что длина их стволов в 2 раза меньше и угол между ними равен 90^o.

Рис. 1. Процесс формирования геометрического фрактала «Дерево Пифагора»

Листинг 5. Построение «Дерева Пифагора»

usesGraphABC;

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.

Пример 6. Рекурсивная окружность из n уровней – это круг и располагающиеся по бокам и в середине его пять окружностей с радиусом в два раза меньше изначальной окружности.

Рис. 2. Процесс формирования рекурсивной окружности

Листинг 6. Построение «Рекурсивной окружности»

usesGraphABC;

procedure krug(x, y, R, n: integer);

begin

Circle(x, y, R);

if N>0 then begin

Circle(x+R, y, R div 2);

Circle(x-R, y, R div 2);

Circle(x, y+R, R div 2);

Circle(x, y-R, R div 2);

R:=R div 2;

krug(x,y,R,n-1);

end;

end;

begin

var x, y, R, N: integer;

x:=300;

y:=300;

R:=100;

krug (x, y, R, 10);

end.

Пример 7. Фрактал «Башня» получается путем вызова процедуры рисования прямоугольника.

Рис. 3. Процесс формирования фрактала «Башня»

Листинг 7. Построение фрактала «Башня»

usesGraphABC;

procedure kubiki(x1, y1, x2, y2, b: integer);

begin

SetBrushStyle(bsClear);

while x10 then begin

rectangle (x1, y1, x2, y2);

x2:=x2-b;

y2:=y2+b;

kvadrat(x1, y1, x2, y2, b, n-1);

end;

end;

begin

var x1, y1, x2, y2, b, n:integer;

x1:=100;

y1:=500;

x2:=500;

y2:=100;

n:=10;

b:=(y1-y2) div n;

kvadrat(x1, y1, x2, y2, b, n);

end.

Пример 9. Фрактальная кривая «Ромбы» представляет собой ромб и вписанные него n-ромбов, вершины которых располагаются на середине стороны большего ромба. Для квадрата находят середины его сторон. Эти точки соединяются линиями, в результате чего образуется другой квадрат, вписанный в первоначальный. К последующим квадратам применяется та же процедура.

Рис. 5. Процесс формирования рекурсивных ромбов

Листинг 9. Построение фрактала «Башня»

usesGraphABC;

procedure rect(xa,ya,xb,yb,xc,yc,xd,yd,n:integer);

var xp,yp,xr,yr,xq,yq,xf,yf: integer;

begin

if n>0 then begin

xp:=(xa+xb) div 2; //нахождение середин сторон

yp:=(ya+yb) div 2;

xr:=(xb+xc) div 2;

yr:=(yb+yc) div 2;

xq:=(xc+xd) div 2;

yq:=(yc+yd) div 2;

xf:=(xa+xd) div 2;

yf:=(ya+yd) div 2;

MoveTo(xp,yp);LineTo(xr,yr);

MoveTo(xr,yr);LineTo(xq,yq);

MoveTo(xq,yq);LineTo(xf,yf);

MoveTo(xf,yf);LineTo(xp,yp);

rect(xp,yp,xr,yr,xq,yq,xf,yf,n-1);

end;end;

var xa,ya,xb,yb,xc,yc,xd,yd,n: integer;

begin

n:=3;

xa:=0; ya:=500; //задание начальных значений

xb:=500; yb:=500;

xc:=500; yc:=50;

xd:=0; yd:=50;

Rect(xa,ya,xb,yb,xc,yc,xd,yd,n);

end. Оценка трудоемкости рекурсивных алгоритмов

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

Рассмотрим один из методов анализа трудоемкости рекурсивного алгоритма, который строится на основе подсчета вершин рекурсивного дерева [6]. Для оценки трудоемкости рекурсивных алгоритмов строится полное дерево рекурсии. Структура дерева рекурсии представлена на рисунке 6.

Рис. 6. Структура дерева рекурсии

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

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

При этом объем рекурсии – это одна из характеристик сложности рекурсивных вычислений для конкретного набора параметров, представляющая собой количество вершин полного рекурсивного дерева без единицы.

Будем использовать следующие обозначения для конкретного входного параметра D:

R(D) – общее число вершин дерева рекурсии,

R_V(D) – объем рекурсии без листьев (внутренние вершины),

R_L(D) – количество листьев дерева рекурсии,

H_R(D) – глубина рекурсии.

Например, для вычисления n-го члена последовательности Фибоначчи в первой главе работы разработана следующая рекурсивная функция:

functionfib(n:integer):integer; //n – номер члена последовательности

var a:integer;

begin

if (n=0) or (n=1) then a:=1 // база рекурсии

else a:=fib(n-1)+fib(n-2); //декомпозиция

fib:=a;

end;

Тогда полное дереворекурсии для вычисления пятого члена последовательности Фибоначчи будет иметь вид (рис. 6).

Рис. 6. Полное дерево рекурсии для пятого члена последовательности Фибоначчи

Характеристиками рассматриваемого метода оценки алгоритма будут следующие величины (табл 1).

Таблица 1

Характеристики рекурсивного алгоритма нахождения

D = 5	D = n
R(D)=9	R(D)=2fn-1
RV(D)=4	RV(D)=fn-1
RL(D)=5	RL(D)=fn
HR(D)=4	HR(D)=n-

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

ВЫВОДЫ

1. Метод рекурсии эффективен при решении вычислительных математических задач и задач на построение геометрических фигур, когда они могут быть сведены к самоподобным.

2. Рекурсивную функцию можно сформулировать из математического определения.

3. Для создания корректного рекурсивного алгоритма необходимо определить базу и шаг рекурсии.

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

5. Трудоемкость рекурсивного алгоритма можно оценить методом подсчета вершин дерева рекурсии.

Список литературы

1. Пильщиков В.Н. Сборник упражнений по языку Паскаль. М.: Наука, 1989. 160 с.

2. Рекурсивная функция [Электронный ресурс]. URL: http://www.studfiles.ru/preview/2428909/

3. Рекурсия. Основные определения. [Электронный ресурс]. URL: http://www.studfiles.ru/preview/1877393/

4. Фаронов В.В. Турбо Паскаль 7.0. Начальный курс: учебное пособие. М.: КНОРУС, 2006. 576 с.

5. Что такое фракталы. [Электронный ресурс]. URL: http://www.bolshoyvopros.ru/questions/1206626-chto-takoe-fraktaly-ih-priroda.html

6. Ульянов М.В. Ресурно-эффективные компьютерные алгоритмы. [Электронный ресур]. URL: http://www.ipu.ru/sites/default/files/publications/31

Код для цитирования: Скопировать