Міністерство освіти і науки України

Національний авіаційний університет

Кафедра прикладної інформатики

Лабораторна робота № 11

З дисципліни: «Теорія алгоритмів»

Виконав

Студент ІКІТ - 112

Односумов Микола

Київ 2015

Тема: «Рекурсивні алгоритми»

Теоретичні відомості

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

Значения функции факториал задаются выражением: 0!=1, n=n*(n-1)!. Они образуют множество {1,2,6,…}:

0!=1, 1=1*0!, 2=2*1!, 6=3*2! и т.д.

Все его элементы, кроме первого, определяются рекурсивно.

Как видим, функция факториал задаётся рекуррентным соотношением порядка 1 и начальным отрезком 0!=1. Вообще, любое рекуррентное соотношение порядка k вместе с заданием первых k элементов последовательности является примером рекурсивного определения.

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

Чтобы подобная “бесконечность” не возникала в рекурсивном определении, должны выполняться следующие условия:

1. множество определяемых объектов является частично упорядоченным;

2. каждая убывающая по этому упорядочению последовательность элементов заканчивается некоторым минимальным элементом;

3. минимальные элементы определяются нерекурсивно;

4. неминимальные элементы определяются с помощью элементов, которые меньше их по этому упорядочению.

Если процедура р содержит явное обращение к самой себе, то она называется явно рекурсивной. Если процедура р содержит обращение к некоторой процедуре q, которая в свою очередь содержит прямое или косвенное обращение к р, то р - называется косвенно рекурсивной.

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

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

Следует понимать, что любой рекурсивный метод можно преобразовать в обычный метод. И практически любой метод можно преобразовать в рекурсивный, если выявить рекуррентное соотношение между вычисляемыми в методе значениями.

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

Завдання

Варіант №15

Дана последовательность натуральных чисел (одно число в строке), завершающаяся двумя числами 0 подряд. Определите, сколько раз в этой последовательности встречается число 1. Числа, идущие после двух нулей, необходимо игнорировать.

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

Ввод	Вывод
1 0 1 0 0 1	2

Блок-схема:

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

#include <iostream>

#include <math.h>

#include <stdlib.h>

#include <conio.h>

#include <time.h>

#include <stdio.h>

using namespace std;

int cseq(int i,int j,int a,string seq);

int sequence (int i=0,int j=0,int a=0)

{

string seq;

cout << "Vvedite posledovatelnost': " << endl;

getline(cin,seq);

return cseq(i,j,a,seq);

}

int cseq(int i,int j,int a,string seq)

{

if (a==2)

{

cout << "Kilkist' odinic': " << j;

return 0;

}

if (((a==0)||(a==1))&&(seq[i]=='1'))

{

cseq(i+1,j+1,0,seq);

}

if (((a==0)||(a==1))&&(seq[i]=='0'))

{

cseq(i+1,j,a+1,seq);

}

if (i==seq.length())

{

cout << "Kilkist' odinic': " << j;

return 0;

}

else

return 0;

}

int main()

{

sequence();

return 0;}

Скрiншоти:

Висновок:

Я навчився будувати рекурсивнi функцii.