Решение задач на использование рекурсивных алгоритмов

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

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

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

разбиение условий задачи на части;

разбиение требований задачи на части;

разбиение области определения задачи на части.

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

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

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

введение недостающих по смыслу задачи элементов между данными и искомыми элементами (дополнительное построение на чертеже, новые переменные для составления уравнений и т.п.);

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

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

"Увидеть";

"Переформулировать";

"Обобщить";

"Использовать характеристическое свойство";

"Перенести часть условий в проверку";

"Обратить функцию";

"Найти родственника".

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

Опорная схема "Увидеть"

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

Опорная схема "Переформулировать"

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

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

Вкладчик положил в банк сумму в sum денежных единиц под p процентов за один период времени. Составим функцию, возвращающую величину вклада по истечении n периодов времени.

Вычисление значения величины вклада можно проводить по известной формуле сложных процентов: $$sum\left(1+\frac{p}{100}\right)n$$. Но рассмотрим рекурсивный вариант алгоритма решения задачи.

Параметризация: выбор параметров следует непосредственно из условия задачи, то есть – процент вклада, n – количество периодов хранения вклада.

База рекурсии: для n=0 размер суммы не изменится, то есть останется sum.

Декомпозиция: если n>0, то размер вклада вычисляется как сумма за n-1 периодов, увеличенная на процент p.

float Deposit(float sum, float p, int n){
  if(n==0) return sum; //база рекурсии
  return Deposit(sum,p,n-1)*(1+p/100); //декомпозиция 
}

Общее количество рекурсивных вызовов при вычислении Deposit(sum, p, n) равно n. Можно уменьшить это значение до величины порядка O(log2n+1) исходя из следующих двух декомпозиционных посылок, описывающих случаи четного и нечетного n.

float DepositNew(float sum, float p, int n){
  if (n==0) return sum ;// база рекурсии
  if (n%2==0) //декомпозиция для четного n
      return sum*pow(DepositNew(1.0,p,n/2),2);
  //декомпозиция для нечетного n
  return sum*(1+p/100)*DepositNew(1.0,p,n-1); 
}

Опорная схема "Обобщить"

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

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

Рассмотрим задачу под названием "Абракадабра". Последовательность из латинских букв строится следующим образом. На нулевом шаге она пуста. На каждом последующем шаге последовательность удваивается, то есть приписывается сама к себе, и к ней слева добавляется очередная буква алфавита (a, b, c, ...). По заданному числу n определить символ, который стоит на n -м месте последовательности, получившейся после шага 26.

Приведем первые шаги формирования последовательности: 0 ? пустая последовательность, 1 - "a", 2 - "baa", 3 - "cbaabaa", 4 - "dcbaabaacbaabaa" и так далее по закономерности. Данный процесс носит рекурсивный характер.

Параметризация. Построим более общую функцию, чем это требуется по условиям задачи. Пусть значение функции Abra(k,n) - n -я буква в последовательности, полученной на шаге k (k = 1, ..., 26). Будем возвращать значение функции в виде целочисленного кода, соответствующего требуемому символу.

База рекурсии. Значение Abra(k,1) равно k -й букве латинского алфавита. Этот факт можно взять в качестве базы рекурсии.

Декомпозицию удобно организовать по k, проводя "раскрутку" последовательности по шагам в обратном направлении. Это приводит к следующей зависимости:

если n<=2k-1, то искомый символ находится на (n-1) месте в латинском алфавите;

если n>2k-1, то искомый символ находится на (2k-1) месте в латинском алфавите.

int Abra(int k, int n){ 
  if (n > pow(2, k-1)-1 || k > 26) return 0; 
  //корректность входных данных
  if (n == 1) return k+96; //база рекурсии
  return Abra(k-1, n-(n <= pow(2, k-1) ? 1 : pow(2, k-1))); 
  //декомпозиция
}

Опорная схема "Характеристические свойства"

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

Рассмотрим задачу о "Допустимых последовательностях". Последовательность Q(N) длины N, составленная из символов 0 и 1, называется допустимой, если в ней нет двух подряд идущих символов 1. В противном случае Q(N) называется недопустимой. Определим K(N) - общее количество допустимых последовательностей для натурального значения N.

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

Пусть набор представлен в виде вектора v с компонентами 0 и 1 (с нумерацией их от 0 до N-1 ). Определим предикат P(v), истинный только на допустимых наборах v. Формализованная запись этого предиката выглядит следующим образом:

$$P(v)=(\forall (0\le i\le N-2))(\neg ((v_{i}=1)(v_{i+1}=1)))= \\ =(\forall (0\le i\le N-2))((v_{i}=1)\wedge (v_{i+1}=0)\vee (v_{i}=0)\wedge (v_{i+1}=0)\vee (v_{i}=0)\wedge (v_{i+1}=1))= \\ =(\forall (0\le i\le N-2))((v_{i+1}=0)\vee ((v_{i+1}=1)\wedge (v_{i}=0)))= \\ =((\forall (0\le i\le N-3))((v_{i+1}=0)\vee ((v_{i+1}=1)\wedge (v_{i}=0))))\wedge \\ \wedge ((v_{N-1}=0)\vee ((v_{N-1}=1)\wedge (v_{N-2}=0)))= \\ =(((\forall (0\le i\le N-3))((v_{i+1}=0)\vee ((v_{i+1}=1)\wedge (v_{i}=0))))\wedge (v_{N-1}=0))\vee \\ \vee (((\forall (0\le i\le N-3))((v_{i+1}=0)\vee ((v_{i+1}=1)\wedge (v_{i}=0))))\wedge ((v_{N-2}=0)\wedge (v_{N-1}=1)))$$

Фактически формальными преобразованиями предиката мы получили его декомпозицию, то есть множество M(N) допустимых векторов длины N(N >= 3) можно представить в виде объединения двух непересекающихся подмножеств:$$M(N)=(M(N-1)x{0})\cup\left(M(N-2)\times \left\{ \begin{pmatrix} 0 \\ 1 \end{pmatrix} \right\}\right).$$

Здесь под декартовыми произведениями M(N-1)x{0} и M(N-2)x{(0,1)T} понимаются множества векторов длины N. В первом случае последняя компонента векторов равна 0, а первые N-1 компонентов составляют допустимые векторы длиной N-1. Во втором случае последние две компоненты равны соответственно 0 и 1, а первые N-2 компоненты составляют допустимые векторы длины N-2. Кроме того: M(1)={(0),(1)} ; M(2)={(0,0)T,(0,1)T,(1,0)T}. Отсюда вытекает справедливость следующего рекуррентного соотношения:

K(1)=2, K(2)=3,, K(N)=K(N-1)+K(N-2) (N>=3).

Таким образом, K(N)=F(N+2), то есть искомая последовательность K(N) есть сдвиг последовательности Фибоначчи F(N) на два элемента влево. Для вычисления K(N) можно написать рекурсивную функцию, аналогичную функции вычисления членов последовательности Фибоначчи.

Опорная схема "Перенести часть условий в проверку"

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

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

Опорная схема "Обратить функцию"

Задачи на обращение функций являются достаточно распространенными. Иногда возникает вопрос об обращении функций, заданных посредством алгоритмов. Пусть, например, относительно параметра $$x\in X$$ решается уравнение вида f(x)=a при некотором известном рекурсивном алгоритме f и заданной величине $$a\in Y$$, где X и Y - множества. Тогда знание обратной для f рекурсивной функции $$g(y) (y\in Y)$$ сразу же позволило бы решить исходное уравнение: f(x)=a, g(f(x))=g(a), x=g(a).

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

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

Опорная схема "Найти родственника"

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

Рассмотрим пример, связанный с экзотическими средними. Пусть a0 и b0 - два положительных числа (a0 > b0). Составим их среднее арифметическое и среднее геометрическое. Продолжим этот процесс рекурсивно. Если числа an и bn уже построены, то определим an+1 и bn+1 следующим образом:$$a_{n+1}=\frac{a_n+b_n}{2},\quad b_{n+1}=\sqrt{a_n\cdot b_n}\quad (n=0,1,...)$$

Можно показать, что a0>an>an+1>bn+1>bn>b0 (n=1,2,...). Откуда вытекает, что обе последовательности (an) и (bn) с двух разных сторон монотонно стремятся к общему пределу, который называют средним арифметико-геометрическим или экзотическим средним исходных чисел a0 и b0. Таким образом, при любом заданном n (n=0,1,2,...) числа (an) и (bn) служат приближениями сверху и снизу для среднего арифметико-геометрического a0 и b0. Для поиска экзотического среднего можно составить функцию, реализующую косвенную рекурсию. При этом параметризация, база и декомпозиция в явном виде приведены в задаче.

#include "stdafx.h"
#include <iostream>
using namespace std;
float Arifm(int n, float a, float b);
float Geom(int n, float a, float b);

int _tmain(int argc, _TCHAR* argv[]){
  int n;
  float a,b;
  do {
  printf ("a>0, a=");
  scanf("%f",a);  
  printf ("b>0, b=");
  scanf("%f",b); 
  printf ("n>0, n=");
  scanf("%d",n); }
  while (a<=0 || b<=0 || n<=0);
  printf("Exotic: between %f and %f",
          Arifm(n,a,b),Geom(n,a,b));
  system("pause");
  return 0;
}

float Arifm(int n, float a, float b){ 
  if (n==0) return a;
  return (Arifm (n-1,a,b)+Geom(n-1,a,b))/2;
}
 
float Geom(int n, float a, float b){ 
  if (n==0) return b;
  return pow(double(Arifm (n-1,a,b)*Geom(n-1,a,b)),0.5);
}

Ключевые термины

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

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

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

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

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

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

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

Введение вспомогательных элементов – это прием использования при решении задачи дополнительных параметров, явно не указанных в постановке задачи.

Моделирование – это замена исходной задачи ее моделью в виде математических описаний.

Опорные схемы рекурсивных вычислений – это подходы к выбору рекурсии как метода решения задач.

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

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

Краткие итоги

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

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

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

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

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

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

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

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

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

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

Лабораторная работа 35. Решение задач на использование рекурсивных алгоритмов

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

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

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

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

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

Выполните приведенные ниже задания.

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

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

Для данных натуральных n и m найдите цепную дробь, соответствующую отношению n/m.

Вычислите значение функции Аккермана двумя способами: непосредственно из определения и снизив трудоемкость алгоритма. Найдите каждым способом Akkerman(3, 7) и Akkerman(8, 20). Функция Аккермана определяется рекурсивно для неотрицательных целых чисел m и n следующим образом:$$A(m,n)= \begin{cases} n+1,\text{ при }m=0 \\ A(m-1,1),\text{ при }m>0,n=0; \\ A(m-1,A(m,n-1)),\text{ при }m>0,n>0. \end{cases}$$

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

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

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

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

изучить словесную постановку задачи, выделив при этом все виды данных;

сформулировать математическую постановку задачи;

выбрать метод решения задачи, если это необходимо;

разработать графическую схему алгоритма;

записать разработанный алгоритм на языке С++;

разработать контрольный тест к программе;

отладить программу;

представить отчет по работе.

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

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

Титульный лист.

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

Математическая модель. В этом подразделе вводятся математические описания физических величин и математическое описание их взаимодействий. Цель подраздела – представить решаемую задачу в математической формулировке.

Алгоритм решения задачи. В подразделе описывается разработка структуры алгоритма, обосновывается абстракция данных, задача разбивается на подзадачи. Схема алгоритма выполняется по ЕСПД (ГОСТ 19.003-80 и ГОСТ 19.002-80).

Листинг программы. Подраздел должен содержать текст программы на языке программирования С++, реализованный в среде MS Visual Studio 2010.

Контрольный тест. Подраздел содержит наборы исходных данных и полученные в ходе выполнения программы результаты.

Выводы по лабораторной работе.

Ответы на контрольные вопросы.

Контрольные вопросы

Почему рекурсию нельзя рассматривать как универсальный метод решения задач?

Почему опорные схемы решения задач рекурсивными способами не являются жестко привязанными к отдельным классам задач?

Каким образом анализ решения обратной задачи может привести к решению поставленной задачи?

По каким признакам "находится родственник" в одноименной опорной схеме?

Всегда ли отбрасывание условий и переход к подзадаче могут привести к эквивалентной задаче? Обоснуйте ответ примерами.

Какие свойства объектов выступают в роли характеристических в соответствующей опорной схеме?