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

Пример 2. Задача о нахождении центра тяжести выпуклого многоугольника.

Выпуклый многоугольник задан на плоскости координатами своих вершин. Найдите его центр тяжести.

Разработаем рекурсивную триаду.

Параметризация: x, y – вещественные массивы, в которых хранятся координаты вершин многоугольника; n – это число вершин многоугольника, по условию задачи, n>1 так как минимальное число вершин имеет двуугольник (отрезок).

База рекурсии: для n=2 в качестве многоугольника рассматривается отрезок, центром тяжести которого является его середина (рис. 34А). При этом середина делит отрезок в отношении 1 : 1. Если координаты концов отрезка заданы как (x0,y0) и (x1,y1), то координаты середины вычисляются по формуле:

Декомпозиция: если n>2, то рассмотрим последовательное нахождение центров тяжести треугольника, четырехугольника и т.д.

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

Для n=4 центром тяжести четырехугольника является точка, делящая в отношении 3 : 1, считая от вершины, отрезок: он образован центром тяжести треугольника, построенного на трех вершинах, и четвертой вершиной (рис. 34C).

Таким образом, для нахождения центра тяжести n -угольника необходимо разделить в отношении (n-1): 1, считая от вершины, отрезок: он образован центром тяжести (n-1) -угольника и n -ой вершиной рассматриваемого многоугольника. Если концы отрезка заданы координатами вершины (xn,yn) и центра тяжести (n-1) -угольника (cxn-1,cyn-1), то при делении отрезка в данном отношении получаем координаты:

#include "stdafx.h"
#include <iostream>
using namespace std;
#define max 20
void centr(int n,float *x, float *y, float *c);

int _tmain(int argc, _TCHAR* argv[]){
  int m, i=0;
  FILE *f;
  if ( ( f = fopen("in.txt", "r") ) == NULL )
    perror("in.txt");
  else {
    fscanf(f, "%d",m);
    printf("\n%d",m);
    if ( m < 2 || m > max ) //вырожденный многоугольник
      printf ("Вырожденный многоугольник");
    else {
     float *px,*py,*pc;
      px = new float[m];
      py = new float[m]; 
      pc = new float[2]; 
      pc[0] = pc[1] = 0;
      while(i<m) {
        fscanf(f, "%f %f",px[i], py[i]); 
        printf("\n%f %f",px[i], py[i]); 
        i++;
      } 
      centr(m,px,py,pc);
      printf ("\nЦентр тяжести имеет координаты: 
              (%.4f, %.4f)",pc[0],pc[1]);
      delete [] pc;
      delete [] py;
      delete [] px;
    }
    fclose(f); 
  }
  system("pause");
  return 0;
}

void centr(int n,float *x, float *y, float *c){        
//n - количество вершин, 
//x,y - координаты вершин,
//c - координаты центра тяжести
  if(n==2){ //база рекурсии
           c[0]=(x[0]+x[1])/2; 
           c[1]=(y[0]+y[1])/2;
          }         
  if(n>2) { //декомпозиция
           centr(n-1,x,y,c);
           c[0]= (x[n-1] + (n-1)*c[0])/n;
           c[1]= (y[n-1] + (n-1)*c[1])/n;
         }
}

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

Однако в данном случае для более достоверной оценки необходимо учитывать емкостные характеристики алгоритма.

Пример 3. Задача о разбиении целого на части.

Найдите количество разбиений натурального числа на сумму натуральных слагаемых.

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

Например, разбиение числа 6 будет представлено 11 комбинациями:

6
5+1
4+2,  4+1+1
3+3,  3+2+1,  3+1+1+1
2+2+2,  2+2+1+1,  2+1+1+1+1
1+1+1+1+1+1

Рассмотрим решение в общем виде. Пусть зависимость R(n,k) вычисляет количество разбиений числа n на сумму слагаемых, не превосходящих k. Опишем свойства R(n,k).

Если в сумме все слагаемые не превосходят 1, то такое представление единственно, то есть R(n,k)=1.

Если рассматриваемое число равно 1, то при любом натуральном значении второго параметра разбиение также единственно: R(n,k)=1.

Если второй параметр превосходит значение первого , то имеет место равенство R(n,k)=R(n,n), так как для представления натурального числа в сумму не могут входить числа, превосходящие его.

Если в сумму входит слагаемое, равное первому параметру, то такое представление также единственно (содержит только это слагаемое), поэтому имеет место равенство: R(n,n)=R(n,n-1)+1.

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

Разработаем рекурсивную триаду.

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

База рекурсии: исходя из свойств рассмотренной зависимости, выделяются два базовых случая:

при n=1     R(n,k)=1,

при k=1     R(n,k)=1.

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

при n=k     R(n,k)=R(n,n-1)+1,

при n<k     R(n,k)=R(n,n),

при n>k     R(n,k)=R(n-k,k)+R(n,k-1).

#include "stdafx.h"
#include <iostream>
using namespace std;
unsigned long int Razbienie(unsigned long int n, 
                            unsigned long int k);

int _tmain(int argc, _TCHAR* argv[]){
  unsigned long int number, max,num;
  printf ("\nВведите натуральное число: ");
  scanf ("%d", number);
  printf ("Введите максимальное натуральное слагаемое в 
           сумме: ");
  scanf ("%d", max); 
  num=Razbienie(number,max);
  printf ("Число %d можно представить в виде суммы с 
           максимальным слагаемым %d.", number, max);
  printf ("\nКоличество разбиений равно %d",num);
  system("pause");
  return 0;
}

unsigned long int Razbienie(unsigned long int n,
                            unsigned long int k){
  if(n==1 || k==1)  return 1;
  if(n<=k)  return Razbienie(n,n-1)+1;        
  return Razbienie(n,k-1)+Razbienie(n-k,k);
}

Пример 4. Задача о переводе натурального числа в шестнадцатеричную систему счисления.

Дано натуральное число, не выходящее за пределы типа unsigned long. Число представлено в десятичной системе счисления. Переведите его в систему счисления с основанием 16.

Пусть требуется перевести целое число n из десятичной в р -ичную систему счисления (по условию задачи, р = 16), то есть найти такое k, чтобы выполнялось равенство n10=kp.

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

База рекурсии: на основании правил перевода чисел из десятичной системы в систему счисления с основанием р, деление нацело на основание системы выполняется до тех пор, пока неполное частное не станет равным нулю, то есть: если целая часть частного n и р равна нулю, то k = n. Данное условие можно реализовать иначе, сравнив n и р: целая часть частного равна нулю, если n < р.

Декомпозиция: в общем случае k формируется из цифр целой части частного n и р, представленной в системе счисления с основанием р, и остатка от деления n на p.

#include "stdafx.h"
#include <iostream>
using namespace std;
#define maxline 50 
void perevod( unsigned long n, unsigned int p,FILE *pf);

int _tmain(int argc, _TCHAR* argv[]){
  unsigned long number10;
  unsigned int osn=16; 
  char number16[maxline];
  FILE *f;
  if ((f=fopen("out.txt", "w"))==NULL)
    perror("out.txt");
  else {
    printf ("\nВведите число в десятичной системе: "); 
    scanf("%ld", number10);
    perevod(number10, osn, f); 
   fclose(f);
  }
  if ((f=fopen("out.txt", "r"))==NULL)
    perror("out.txt"); 
  else {  
    fscanf(f,"%s",number16);
    printf("\n %ld(10)=%s(16)", number10, number16);
    fclose(f); 
  }
  system("pause");
  return 0;
}

void perevod(unsigned long n, unsigned int p, FILE *pf){
  char c;
  unsigned int r;
  if(n >= p) perevod (n/p, p, pf);//декомпозиция
  r=n%p;
  c=r < 10 ? char (r+48) : char (r+55);
  putc(c, pf);
}

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

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

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

Декомпозиция – это выражение общего случая через более простые подзадачи с измененными параметрами.

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

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

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

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

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

Прямая рекурсия – это непосредственное обращение рекурсивной функции к себе, но с иным набором входных данных.

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

Рекурсивная функция – это функция, которая в своем теле содержит обращение к самой себе с измененным набором параметров.

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

Рекурсия – это определение объекта посредством ссылки на себя.

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

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

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

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

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

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

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

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

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

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

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

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

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

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