2.3. Примеры разработки рекурсивной триады - Обработки данных

2.3. Примеры разработки рекурсивной триады - Обработки данных

^ 2.3. Примеры разработки рекурсивной триады
Пример 1. Задачка о разрезании прямоугольника на квадраты.

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

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

Параметризация 2.3. Примеры разработки рекурсивной триады - Обработки данных: m, n – натуральные числа, надлежащие размерам прямоугольника.

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

Декомпозиция: если m  n, то вероятны два 2.3. Примеры разработки рекурсивной триады - Обработки данных варианта m < n либо m > n. Отрежем от прямоугольника больший по площади квадрат с натуральными сторонами. Длина стороны такового квадрата равна меньшей из сторон прямоугольника. После того, как квадрат будет отрезан, размеры прямоугольника станут последующие: большая 2.3. Примеры разработки рекурсивной триады - Обработки данных сторона уменьшится на длину стороны квадрата, а наименьшая не поменяется. Число разыскиваемых квадратов будет рассчитываться как число квадратов, на которые будет разрезан приобретенный прямоугольник, плюс один (отрезанный квадрат). К получившемуся прямоугольнику применим подобные 2.3. Примеры разработки рекурсивной триады - Обработки данных рассуждения: проверим на соответствие базе либо перейдем к декомпозиции (рис. 2).




Рис. 2. Пример разрезания прямоугольника 135 на квадраты


#include "stdafx.h"

#include

using namespace std;

int kv(int m,int n);


int _tmain(int argc 2.3. Примеры разработки рекурсивной триады - Обработки данных, _TCHAR* argv[]) {

int a,b,k;

printf("Введите стороны прямоугольника->");

scanf("%d%d",&a,&b);

k = kv(a,b);

printf("Прямоугольник со сторонами %d и %d можно

разрезать на %d квадратов 2.3. Примеры разработки рекурсивной триады - Обработки данных",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 2.3. Примеры разработки рекурсивной триады - Обработки данных>n

return 1+kv(m,n-m); //декомпозиция для m
}


Оптимальнее декомпозицию можно оформить так:

if(m>n) return m/n+kv(n,m%n); //декомпозиция для m>n

return n/m+kv(m,n%m 2.3. Примеры разработки рекурсивной триады - Обработки данных); //декомпозиция для m

Чертами рассматриваемого способа оценки метода будут последующие величины (рис. 3).

D = (13, 5)

D = (m, n), m ≥ n, худший случай





















Рис. 3. Пример полного дерева рекурсии для разрезания прямоугольника 135

на квадраты


Пример 2. Задачка о нахождении центра масс выпуклого 2.3. Примеры разработки рекурсивной триады - Обработки данных многоугольника.

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

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

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

^ База рекурсии: для в качестве многоугольника рассматривается отрезок, центром масс которого является его середина (рис. 4А). При всем этом середина 2.3. Примеры разработки рекурсивной триады - Обработки данных разделяет отрезок в отношении 1 : 1. Если координаты концов отрезка заданы как и , то координаты середины рассчитываются по формуле:

, .

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

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

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














А

В

С


Рис. 4. Примеры построения центров тяжести многоугольников


Таким макаром, для нахождения центра масс n 2.3. Примеры разработки рекурсивной триады - Обработки данных-угольника нужно поделить в отношении  : 1, считая от верхушки, отрезок: он образован центром масс -угольника и n-ой верхушкой рассматриваемого многоугольника. Если концы отрезка заданы координатами верхушки и центра масс -угольника , то при делении отрезка 2.3. Примеры разработки рекурсивной триады - Обработки данных в данном отношении получаем координаты:

, .


#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 2.3. Примеры разработки рекурсивной триады - Обработки данных[]){

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 max ) //вырожденный многоугольник

printf ("Вырожденный многоугольник");

else {

float *px 2.3. Примеры разработки рекурсивной триады - Обработки данных,*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 2.3. Примеры разработки рекурсивной триады - Обработки данных[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 2.3. Примеры разработки рекурсивной триады - Обработки данных, 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 2.3. Примеры разработки рекурсивной триады - Обработки данных[n-1] + (n-1)*c[0])/n;

c[1]= (y[n-1] + (n-1)*c[1])/n;

}

}


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



D = 4

D = n


















Но в этом случае для более достоверной оценки нужно учесть емкостные 2.3. Примеры разработки рекурсивной триады - Обработки данных свойства метода.


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

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

Разбиение предполагает представление натурального числа в виде суммы натуральных слагаемых, при всем этом суммы 2.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

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

Если в сумме все слагаемые не превосходят 1, то такое представление единственно, другими словами .

Если рассматриваемое число равно 1, то при любом натуральном 2.3. Примеры разработки рекурсивной триады - Обработки данных значении второго параметра разбиение также единственно: .

Если 2-ой параметр превосходи значение первого , то имеет место равенство , потому что для представления натурального числа в сумму не могут заходить числа, превосходящие его.

Если в сумму заходит 2.3. Примеры разработки рекурсивной триады - Обработки данных слагаемое, равное первому параметру, то такое представление также единственно (содержит только это слагаемое), потому имеет место равенство: .

Осталось разглядеть случай . Разобьем все представления числа n на непересекающиеся разложения: в одни непременно 2.3. Примеры разработки рекурсивной триады - Обработки данных будет заходить слагаемое k, а другие суммы не содержат k. 1-ая группа сумм, содержащая k, эквивалентна зависимости , что следует после вычитания числа k из каждой суммы. 2-ая группа сумм содержит разбиение числа 2.3. Примеры разработки рекурсивной триады - Обработки данных n на слагаемые, каждое из которых не превосходит , другими словами число таких представлений равно . Потому что обе группы сумм не пересекаются, то .

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

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

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

при ,

при .

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

при ,

при ,

при .


#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 2.3. Примеры разработки рекурсивной триады - Обработки данных int number, max,num;

printf ("\nВведите натуральное число: ");

scanf ("%d", &number);

printf ("Введите наибольшее натуральное слагаемое в

сумме: ");

scanf ("%d", &max);

num=Razbienie(number,max);

printf ("Число %d можно представить в 2.3. Примеры разработки рекурсивной триады - Обработки данных виде суммы с

наибольшим слагаемым %d.", number, max);

printf ("\nКоличество разбиений равно %d",num);

system("pause");

return 0;

}


unsigned long int Razbienie(unsigned long int n,

unsigned long int k) k==1) return 1;

if(n<=k 2.3. Примеры разработки рекурсивной триады - Обработки данных) return Razbienie(n,n-1)+1;

return Razbienie(n,k-1)+Razbienie(n-k,k);



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

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

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

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

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

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


#include "stdafx.h"

#include

using namespace std;

#define maxline 50

void perevod( unsigned long n, unsigned int p,FILE 2.3. Примеры разработки рекурсивной триады - Обработки данных *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Введите число в десятичной системе 2.3. Примеры разработки рекурсивной триады - Обработки данных: ");

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, number 2.3. Примеры разработки рекурсивной триады - Обработки данных16);

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 2.3. Примеры разработки рекурсивной триады - Обработки данных;

c=r < 10 ? char (r+48) : char (r+55);

putc(c, pf);

}



23-polnomochiya-prokurora-v-nadzornoj-instancii-po-grazhdanskim-delam-naya-rabota-prokurorskij-nadzor-za-zashitoj.html
23-popitki-probudit-osoznanie-v-snovidenii-kniga-posvyashena-dalnejshemu-razvitiyu-idej-i-metodov-sovremennogo.html
23-poryadok-privlecheniya-k-grazhdansko-pravovoj-otvetstvennosti-za-vred-prichinennij-nezakonnimi-dejstviyami-organami-doznaniya-prokuraturi-i-suda.html