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

вершин дерева рекурсии,
RV(D) – объем рекурсии без листьев (внутренние вершины),
RL(D)

– количество листьев дерева рекурсии,
HR(D) – глубина рекурсии.

int Fib(int n){ //n – номер члена последовательности
if(n<3) return 1; //база рекурсии
return Fib(n-1)+Fib(n-2); //декомпозиция
}

– натуральные числа, соответствующие размерам прямоугольника.
База рекурсии: для m=n число

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

_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 на квадраты

рекурсии для разрезания прямоугольника 13x5 на квадраты

y – вещественные массивы, в которых хранятся координаты вершин многоугольника;

n – это число вершин многоугольника, по условию задачи, n>1 так как минимальное число вершин имеет двуугольник (отрезок).

База рекурсии: для n=2 в качестве многоугольника рассматривается отрезок, центром тяжести которого является его середина

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

нахождение центров тяжести треугольника, четырехугольника и т.д.

3 : 1, считая от вершины, отрезок

(n-1) -угольника (cxn-1,cyn-1),
то при делении отрезка в данном отношении

получаем координаты:

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;

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;
}

//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;

представлено 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

слагаемых, не превосходящих 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).

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

из свойств рассмотренной зависимости, выделяются два базовых случая:
при n=1     R(n,k)=1,
при k=1     R(n,k)=1.

составляют декомпозиционные отношения.
при n=k     R(n,k)=R(n,n-1)+1,
при nk

    R(n,k)=R(n-k,k)+R(n,k-1).

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);
}

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

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

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);
}