Слайд 1Анализ трудоемкости рекурсивных алгоритмов методом подсчета вершин дерева рекурсии
Слайд 2рекурсивная триада
Рекурсивную триаду составляют
параметризация
выделение базы
декомпозиция
Слайд 3последовательность Фибоначчи
обозначения для конкретного входного параметра D:
R(D) – общее число
вершин дерева рекурсии,
RV(D) – объем рекурсии без листьев (внутренние вершины),
RL(D)
– количество листьев дерева рекурсии,
HR(D) – глубина рекурсии.
int Fib(int n){ //n – номер члена последовательности
if(n<3) return 1; //база рекурсии
return Fib(n-1)+Fib(n-2); //декомпозиция
}
Слайд 4Полное дерево рекурсии для пятого члена последовательности Фибоначчи
Слайд 5Характеристиками рассматриваемого метода оценки алгоритма будут следующие величины.
Слайд 6Задача о разрезании прямоугольника на квадраты.
Разработаем рекурсивную триаду.
Параметризация: m, n
– натуральные числа, соответствующие размерам прямоугольника.
База рекурсии: для m=n число
получившихся квадратов равно 1, так как данный прямоугольник уже является квадратом.
Декомпозиция: если m!=n , то возможны два случая m < n или m > n.
Слайд 7#include "stdafx.h"
#include
using namespace std;
int kv(int m,int n);
int _tmain(int argc,
_TCHAR* argv[]) {
int a,b,k;
printf("Введите стороны прямоугольника->");
scanf("%d%d",&a,&b);
k
= kv(a,b);
printf("Прямоугольник со сторонами %d и %d можно разрезать
на %d квадратов",a,b,k);
system("pause");
return 0;
}
int kv(int m,int n){ //m,n – стороны прямоугольника
if(m==n) return 1; //база рекурсии
if(m>n) return 1+kv(m-n,n); //декомпозиция для m>n
return 1+kv(m,n-m); //декомпозиция для m
}
Пример разрезания прямоугольника
13x5 на квадраты
"); scanf("%d%d",&a,&b); k = kv(a,b); printf("Прямоугольник со сторонами %d и %d можно разрезать на %d квадратов",a,b,k); system("pause"); return 0;}int kv(int m,int n){ //m,n – стороны прямоугольника if(m==n) return 1; //база рекурсии if(m>n) return 1+kv(m-n,n); //декомпозиция для m>n return 1+kv(m,n-m); //декомпозиция для m">
Слайд 8Характеристиками рассматриваемого метода оценки алгоритма будут следующие величины
Пример полного дерева
рекурсии для разрезания прямоугольника 13x5 на квадраты
Слайд 9Задача о нахождении центра тяжести выпуклого многоугольника.
Разработаем рекурсивную триаду.
Параметризация: x,
y – вещественные массивы, в которых хранятся координаты вершин многоугольника;
n – это число вершин многоугольника, по условию задачи, n>1 так как минимальное число вершин имеет двуугольник (отрезок).
База рекурсии: для n=2 в качестве многоугольника рассматривается отрезок, центром тяжести которого является его середина
Слайд 10Если координаты концов отрезка заданы как (x0,y0) и (x1,y1), то
координаты середины вычисляются по формуле:
Декомпозиция: если n>2, то рассмотрим последовательное
нахождение центров тяжести треугольника, четырехугольника и т.д.
Слайд 11Для n=3 центром тяжести треугольника является точка пересечения его медиан
Слайд 12Для n=4 центром тяжести четырехугольника является точка, делящая в отношении
3 : 1, считая от вершины, отрезок
Слайд 13Если концы отрезка заданы координатами вершины (xn,yn) и центра тяжести
(n-1) -угольника (cxn-1,cyn-1),
то при делении отрезка в данном отношении
получаем координаты:
Слайд 14#include "stdafx.h"
#include
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 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;
Слайд 15#include "stdafx.h"
#include
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 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;
}
Слайд 16void 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;
Слайд 17Характеристиками рассматриваемого метода оценки алгоритма будут следующие величины.
Слайд 18Задача о разбиении целого на части.
Например, разбиение числа 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
Слайд 19Пусть зависимость R(n,k) вычисляет количество разбиений числа n на сумму
слагаемых, не превосходящих k
свойства R(n,k).
2.R(n,k)=1
3.Если второй параметр превосходит значение первого
, то имеет место равенство R(n,k)=R(n,n)
4.Если в сумму входит слагаемое, равное первому параметру, то такое представление также единственно (содержит только это слагаемое), поэтому имеет место равенство: R(n,n)=R(n,n-1)+1.
5. (n>k), R(n,k)=R(n-k,k)+R(n,k-1).
Слайд 20Разработаем рекурсивную триаду.
Параметризация: Рассмотрим разбиение натурального числа n на сумму
таких слагаемых, которые не превосходят натурального числа k.
База рекурсии: исходя
из свойств рассмотренной зависимости, выделяются два базовых случая:
при n=1 R(n,k)=1,
при k=1 R(n,k)=1.
Слайд 21Декомпозиция: общий случай задачи сводится к трем случаям, которые и
составляют декомпозиционные отношения.
при n=k R(n,k)=R(n,n-1)+1,
при nk
R(n,k)=R(n-k,k)+R(n,k-1).
Слайд 22#include "stdafx.h"
#include
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);
}
Слайд 23Задача о переводе натурального числа в шестнадцатеричную систему счисления.
n10=kp
Параметризация: n
– данное натуральное число, р – основание системы счисления.
База рекурсии:
на основании правил перевода чисел из десятичной системы в систему счисления с основанием р, деление нацело на основание системы выполняется до тех пор, пока неполное частное не станет равным нулю, то есть: если целая часть частного n и р равна нулю, то k = n. Данное условие можно реализовать иначе, сравнив n и р: целая часть частного равна нулю, если n < р.
Декомпозиция: в общем случае k формируется из цифр целой части частного n и р, представленной в системе счисления с основанием р, и остатка от деления n на p.
Слайд 24#include "stdafx.h"
#include
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);
}