Структуры данных и алгоритмы., страница 2

Sy=Sy+(s->point->y)*(s->point->mas);

Sz=Sz+(s->point->z)*(s->point->mas);

Smas=Smas+s->point->mas;

s=s->next;

}

Mx=Sx/Smas;

My=Sy/Smas;

Mz=Sz/Smas;

return sqrt(Mx*Mx+My*My+Mz*Mz);

}

// функция копирования точек из стека

points *copy_from_stek (stek *s)

{

points *p,*q;

if (s!=NULL)

{

p=new points;

p->x=s->point->x;

p->y=s->point->y;

p->z=s->point->z;

p->mas=s->point->mas;

q=p;

s=s->next;

while (s!=NULL)

{

q=q->next=new points;

q->x=s->point->x;

q->y=s->point->y;

q->z=s->point->z;

q->mas=s->point->mas;

s=s->next;

}

q->next=NULL;

}

return p;

}

// Функция поиска n-го количества точек перебором

points *search (points *p,int n,float *Mr)

{

stek *s;     // s - стек перебора

points *q,*p2;

int i=1,k=1;

float r;

s=NULL;

s=put_on_stek (s,p);

p=p->next;

while (i<n) // Занесение в стек n начальных значений.

{

s=put_on_stek (s,p);

p=p->next;

i++;

}

*Mr=length (s);

p2=copy_from_stek (s);

// Цикл перебора

while (length_stek(s)==n)  // Пока кол-во элементов стека равно кол-ву искомых точек

{

r=length (s);

if (*Mr>r)

{*Mr=r;

p2=copy_from_stek (s);

}

while (p->next!=NULL)      // Пока не достигнута последняя точка при переборе

{

k++;

p=get_from_stek (&s);

p=p->next;

s=put_on_stek (s,p);

if (*Mr>r) {*Mr=r;

p2=copy_from_stek (s);

}

}

p=get_from_stek (&s);

do                   // изятие уже перебранных элементов

{

q=p;

p=get_from_stek (&s);

}

while ((p->next==q)&&s!=NULL);

if (p!=NULL)

while ((length_stek(s)<n)&&(p->next!=NULL)) // сдвиг элементов более глубоких уровней

{

p=p->next;

s=put_on_stek (s,p);

}

}

return p2;

}

Файл программы: main.cpp

#include <stdio.h>

#include <conio.h>

#include <math.h>

#include "funk.cpp"

void main ()

{

int n,k;

float r;

points *p,*p2;

FILE *f;

clrscr();

f=fopen ("input.txt","r");

if (f!=NULL)

{

p=input (f,&k);

fclose (f);

printf ("Все точки");

print_points (p);

printf ("\nВсего точек %d",k);

if (k==0) printf ("\nИзначальные данные не верны");

else

{

printf ("\nВведите необходимое количество точек ");

scanf ("\n%d",&n);

while (n>k)

{

printf ("Неверное значение!\a\nОбщее количество точек меньше необходимого");

printf ("\nВведите необходимое количество точек ");

scanf ("\n%d",&n);

}

if (n==k) printf ("Все точки удовлетворяют условию задачи\n");

p2=search(p,n,&r);

printf ("Искомые точки");

print_points (p2);

printf ("\nРасстояне от центра масс до начала координат %f",r);

}

}

else printf ("Файл input.txt ненайден");

getch();

}

7. Набор тестов

Все точки	Необходимое кол-во	Найденные точки
(21,0,3)0.9 (25,0,0)5.65 (48,-22,0)2.1 (0,0,45)1.9 (-99,-99,-99)0.02 (54,98,42)5 (-57,-62,-9)5 (-48,26,-57)12 (12,-12,56)2 (99,99,99)0.01	1	(21,0,3)0.9
(21,0,3)0.9 (25,0,0)5.65 (48,-22,0)2.1 (0,0,45)1.9 (-99,-99,-99)0.02 (54,98,42)5 (-57,-62,-9)5 (-48,26,-57)12 (12,-12,56)2 (99,99,99)0.01	5	(-99,-99,-99)0.02 (54,98,42)5 (-57,-62,-9)5 (21,0,3)0.9
(21,0,3)0.9 (25,0,0)5.65 (48,-22,0)2.1 (0,0,45)1.9 (-99,-99,-99)0.02 (54,98,42)5 (-57,-62,-9)5 (-48,26,-57)12 (12,-12,56)2 (99,99,99)0.01	10	(21,0,3)0.9 (25,0,0)5.65 (48,-22,0)2.1 (0,0,45)1.9 (-99,-99,-99)0.02 (54,98,42)5 (-57,-62,-9)5 (-48,26,-57)12 (12,-12,56)2 (99,99,99)0.01
(21,0,3)0.9 (25,0,0)5.65 (48,-22,0)2.1 (0,0,45)1.9 (-99,-99,-99)0.02 (54,98,42)5 (-57,-62,-9)5 (-48,26,-57)12 (12,-12,56)2 (99,99,99)0.01	11	Т. к. кол-во необходимых точек больше чем общее кол-во точек, то надо ввести новое кол-во искомых точек