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

МИНИСТЕРСТВО ОБРАЗОВАНИЯ РФ

НГТУ

КАФЕДРА ПРИКЛАДНОЙ МАТЕМАТИКИ

КУРСОВАЯ РАБОТА

ПО ДИСЦИПЛИНЕ:

СТРУКТУРЫ ДАННЫХ И АЛГОРИТМЫ

ФПМИ

ГРУППА: ПМ-21

СТУДЕНТ: Воронов А.С.

ПРЕПОДАВАТЕЛЬ: Шапошникова Т. А.

НОВОСИБИРСК 2003 г.

1. Условие задачи:

Найдите n-материальных точек, центр масс, которых наиболее близок к началу координат.

2. Анализ задачи

Дано: (x_i,y_i,z_i) m_i – где x_i,y_i и z_i – координаты точки в трехмерном пространстве, а m_i – масса этой точки. n-число необходимых точек.

Результат: (x_i,y_i,z_i) m_i i=1,n

Метод решения: Задача решается полным перебором всех точек с нахождением минимального расстояния.

Пусть всего к точек.

Вычислим расстояние до центра у первых n точек (точки перебора). Примем его за минимальное.

а=n

1.Затем a -ю точку из  точек перебора заменим на а+1 и вычислим длину до центра и сравним ее с минимальной и запомним в (множество искомых точек) (будем повторять пока а≠k).

2.Затем извлекаем точку из множества точек перебора (повторяем пока точки в множестве перебора идут в том же порядке что в множестве поиска (минимум 2 раза))

Пусть номер последней изъятой точки b

3.Дополняем множество точек перебора до n штук b+1,b+2… точками если такие имеются и повторяем 1-3 иначе заканчиваем поиск.

Ответом является множество искомых точек.

3. Структура данных

typedef struct points {float x,y,z,mas; points *next;}; - структура хранящая все точки

typedef struct stek {points *point; stek *next;}; - структура используемая при переборе

4. Функции и их прототипы

points *input (FILE *f,int *k) Функция ввода данных из файла

void print_points (points *p) Функция вывода на экран

stek *put_on_stek (stek *s,points *p) Функция добавления в стек

points *get_from_stek (stek **s) Функция возврата информации из стека

int length_stek (stek *s) Функция подсчета количаства элементов стека

float length (stek *s) Функция подсчета расстояния до начала координат

points *copy_from_stek (stek *s) функция копирования точек из стека

points *search (points *p,int n,float *Mr) Функция поиска n-го количества точек перебором

5. Алгоритм решения

6. Текст программы

Файл библиотеки: funk.cpp

// Структура хранящая все точки

typedef struct points {float x,y,z,mas; points *next;};

// Структура используемая при переборе

typedef struct stek {points *point; stek *next;};

// Функция ввода данных из файла

points *input (FILE *f,int *k)

{

char c='y',a;

points *p,*q;

p=q=new points;

*k=0;

while (fscanf(f,"\n%c",&a)!=EOF)

{

q=q->next=new points;

q->next=NULL;

fscanf(f,"%f",&q->x);

fgetc(f);

fscanf (f,"%f",&q->y);

fgetc(f);

fscanf (f,"%f",&q->z);

fgetc(f);

fscanf (f,"%f",&q->mas);

while (q->mas<=0||c=='n'||c=='N')  // Проверка на допустимость массы

{

printf ("\nНе верные исходные данные (масса <= 0)");

printf ("\nХотите ввести исправленные данные? (Y)es/(N)o ");

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

if (c=='Y'||c=='y')

{

printf ("Введите массу ");

scanf ("%f",&q->mas);

}

else {return NULL; (*k)=0;}

}

(*k)++;

}

return p->next;

}

// Функция вывода на экран

void print_points (points *p)

{

int i=0;

while (p!=NULL)

{

printf ("\n(%6.2f,%6.2f,%6.2f)  Масса %3.3f",p->x,p->y,p->z,p->mas);

p=p->next;

i++;

if (i>21)

{

printf ("\nНажмите любую клавишу для продолжения ");

getch();

i=0;

}

}

}

// Функция добавления в стек

stek *put_on_stek (stek *s,points *p)

{

stek *a;

a=NULL;

if (p!=NULL)

{a=new stek;

a->point=p;

a->next=s;

}

return a;

}

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

points *get_from_stek (stek **s)

{

points *a;

if ((*s)!=NULL)

{

a=(*s)->point;

*s=(*s)->next;

} else return NULL;

return a;

}

// Функция подсчета количаства элементов стека

int length_stek (stek *s)

{

int i=0;

while (s!=NULL)

{

s=s->next;

i++;

}

return i;

}

// Функчия подсчета расстояния до начала координат

float length (stek *s)

{

float Sx=0,Sy=0,Sz=0,Smas=0,Mx=0,My=0,Mz=0;

while (s!=NULL)

{

Sx=Sx+(s->point->x)*(s->point->mas);