Класс. МУПР ОП.08 Теория алгоритмов. Методические указания по проведению практических работ по дисциплине Теория алгоритмов

• Название: Методические указания по проведению практических работ по дисциплине Теория алгоритмов
• Анкор: Класс
• Дата: 14.11.2019
• Размер: 3.39 Mb.
• Имя файла: МУПР ОП.08 Теория алгоритмов.doc
• Тип: Методические указания; #95109
• страница: 24 из 29

Практическая работа №17. Разработка рекурсивных алгоритмов

Цель работы:

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

Блок-схема предопределенного процесса – обращение к подзадаче (в С++ к функции):

Рассмотрим задачу вычисления факториала числа N! = 1^.2^.3^{. . .}N. Результатом будет одно число, поэтому лучше алгоритм оформить в виде функции.

Ее блок-схема показана на рисунке. Переменная К используется для накопления произведения и, поскольку 0! = 1 и1! = 1, то в блоке 2 ей сразу присваивается значение 1. Далее, если N>1, то в цикле, образованном блоками 4-5, накапливается искомое произведение и помещается в переменную К. В блоке 6 имя Fact функции получает значение вычисленного произведения из ячейки К. Для процедур действия, размещенного в блоке 6, не может быть, а для функций оно должно быть обязательно, поскольку иначе значение функции на выходе окажется неопределенным.



Обращение к функции в других алгоритмах (головных, процедурах, функциях) производится по ее имени.

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

Пример использования функции Fact показан на рисунке. В операторе присваивания используется обращение к функции для N = 6. После передачи этого значения в алгоритм и вычислений внутри него результат будет сначала присвоен имени функции, т. е. переменной Fact, а затем в операторе присваивания - переменной L.



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

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

void Rec(int a){

if (a>0)Rec(a-1);

cout<<"\n a="<
}

Рассмотрим, что произойдет, если в основной программе поставить вызов, например, вида Rec(3).

void main(){clrscr();

int x;

cout<<"\nx=";cin>>x;

Rec(x);

getch(); }

Ниже представлена блок-схема, показывающая последовательность выполнения операторов.



Результат работы программы:

/*

x=3

a=0

a=1

a=2

a=3

*/

Процедура Rec вызывается с параметром a = 3. В ней содержится вызов процедуры Rec с параметром a = 2. Предыдущий вызов еще не завершился, поэтому можете представить себе, что создается еще одна процедура и до окончания ее работы первая свою работу не заканчивает. Процесс вызова заканчивается, когда параметр a = 0. В этот момент одновременно выполняются 4 экземпляра процедуры. Количество одновременно выполняемых процедур называют глубиной рекурсии.

Четвертая вызванная процедура (Rec(0)) напечатает число 0 и закончит свою работу. После этого управление возвращается к процедуре, которая ее вызвала (Rec(1)) и печатается число 1. И так далее пока не завершатся все процедуры. Результатом исходного вызова будет печать четырех чисел: 0, 1, 2, 3.

Еще один визуальный образ происходящего представлен на рисунке.



Выполнение процедуры Rec с параметром 3 состоит из выполнения процедуры Rec с параметром 2 и печати числа 3. В свою очередь выполнение процедуры Rec с параметром 2 состоит из выполнения процедуры Rec с параметром 1 и печати числа 2. И т. д.
Пример

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

//rec03

//рекурсия вычисление факториала

#include

#include

long fact(int n) {

int f;

if (n==1) f=1;

else

f=n*fact(n-1);

return f;

}
void main(){

clrscr(); int a;

cout<<"a="; cin>>a;

cout<<"\n Factorial="<
getch();

}

/*

a=7

Factorial=5040

*/

Пусть n=3. Как будет выполняться вызов fact(n) ? На рисунке представлена схема выполнения вызова функции. Стрелки указывают порядок вычисления. Сначала происходит движение по стрелкам вниз, указывающее на то, что происходит временное прерывание выполнения текущего вызова, и переход к выполнению вызова более низкого уровня, пока не будет получен тривиальный случай. Затем происходит подъем вверх, что означает возобновление прерванных вызовов. Первым возобновится выполнение такого вызова, который был прерван последним.



Схема выполнения вызова рекурсивной функции
Задание

1. Составить алгоритм вычисления НОД двух чисел с помощью рекурсивной функции.

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

3. Напишите рекурсивную функцию, переворачивающую заданное натуральное число.
Дополнительные задания

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

Напишите рекурсивную функцию, вычисляющую n!!.

2. Напишите рекурсивную функцию, определяющую количество единиц в двоичном представлении натурального числа.

3. Написать функцию сложения двух чисел, используя только прибавление единицы.

4. Написать функцию умножения двух чисел, используя только операцию сложения.

5. Проверить, является ли фрагмент строки с i-го по j-й символ палиндромом.

6. Подсчитать количество цифр в заданном числе.