Лабораторная работа 34. Рекурсия и рекурсивные алгоритмы

Цель работы: изучить понятие, виды рекурсии и рекурсивную триаду, научиться разрабатывать рекурсивную триаду при решении задач на языке C++.

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

Теоретические сведения.

Ознакомьтесь с материалом лекции.

Задания к лабораторной работе.

Составьте рекурсивную функцию для решения задачи (по вариантам).

1. Найдите сумму всех трехзначных чисел, кратных 25.
2. Переведите натуральное число в восьмеричную систему счисления.
3. Найдите -ый член геометрической прогрессии, заданной первым членом и знаменателем.
4. Найдите сумму первых четных натуральных чисел
5. Найдите -ый член арифметической прогрессии, заданной первым членом и разностью.

6. Определите закономерность формирования членов последовательности . Найдите -ый член последовательности, сократив количество рекурсивных вызовов.

2. Найдите сумму первых натуральных чисел, оканчивающихся цифрой 5.
3. Функция определена на полуинтервале следующим образом: Выполните ее периодическое продолжение на множество действительных чисел. Найдите значение полученной функции для данного .
4. Переведите натуральное число в двоичную систему счисления.
5. Разработайте рекурсивную функцию, подсчитывающую количество способов разбиения выпуклого многоугольника на треугольники непересекающимися диагоналями.

12. Определите закономерность формирования членов последовательности . Найдите -ый член последовательности, сократив количество рекурсивных вызовов.

Указания к выполнению работы.

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

Следует реализовать каждое задание в соответствии с приведенными этапами:

• изучить словесную постановку задачи, выделив при этом все виды данных;
• сформулировать математическую постановку задачи;
• выбрать метод решения задачи, если это необходимо;
• разработать графическую схему алгоритма;
• записать разработанный алгоритм на языке С++;
• разработать контрольный тест к программе;
• отладить программу;
• представить отчет по работе.

Требования к отчету.

Отчет по лабораторной работе должен соответствовать следующей структуре.

• Титульный лист.
• Словесная постановка задачи. В этом подразделе проводится полное описание задачи. Описывается суть задачи, анализ входящих в нее физических величин, область их допустимых значений, единицы их измерения, возможные ограничения, анализ условий при которых задача имеет решение (не имеет решения), анализ ожидаемых результатов.
• Математическая модель. В этом подразделе вводятся математические описания физических величин и математическое описание их взаимодействий. Цель подраздела – представить решаемую задачу в математической формулировке.
• Алгоритм решения задачи. В подразделе описывается разработка структуры алгоритма, обосновывается абстракция данных, задача разбивается на подзадачи. Схема алгоритма выполняется по ЕСПД (ГОСТ 19.003-80 и ГОСТ 19.002-80).
• Листинг программы. Подраздел должен содержать текст программы на языке программирования С++, реализованный в среде MS Visual Studio 2010.
• Контрольный тест. Подраздел содержит наборы исходных данных и полученные в ходе выполнения программы результаты.
• Выводы по лабораторной работе.
• Ответы на контрольные вопросы.

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

Прямое обращение функции к самой себе предполагает, что в теле функции содержится вызов этой же функции, но с другим набором фактических параметров. Такой способ организации работы называется прямой рекурсией. Например, чтобы найти сумму первых n натуральных чисел, надо сумму первых (n-1) чисел сложить с числом n, то есть имеет место зависимость: S_n=S_n-1+n. Вычисление происходит с помощью аналогичных рассуждений. Такая цепочка взаимных обращений в конечном итоге сведется к вычислению суммы одного первого элемента, которая равна самому элементу.

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

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

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

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

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

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