Разработка алгоритмов и программ выполнения операций над последовательными и связанными представлениями структур данных (стр. 2 из 3)
При прогоне программы мы получаем значения функции, которые можно изобразить на графике как функцию f(NX,NY,NZ). Данные точки показывают характер кривой. Для аппроксимации этого облака точек в своей курсовой работе я использовал метод наименьших квадратов.
Анализ по методу наименьших квадратов заключается в определении параметров кривой, описывающих связь между некоторым числом N пар значений Xi, Yi (в данном случае n и t соответственно), обеспечивая при этом наименьшую среднеквадратичную погрешность. Графически эту задачу можно представить следующим образом – в облаке точек Xi, Yi плоскости XY (смотри рисунок) требуется провести прямую так, чтобы величина всех отклонений отвечала условию:
N
F =
K=1
Где
В моём случае T(NX,NY,NZ)=O(NX*(NY+NZ) =>
T(NX,NY,NZ)=C1*NX*(NY+NZ)+C2*(NY+NZ)+C3*(NY)+C4*(NZ)
Следовательно для моего примера мы получим:
Для того чтобы получить значение функции на K-том эксперименте, мы засекаем значение времени перед вызовом функции, которая реализует алгоритм, вставим оператор вида:
TikTak=clock();
Где функция clock() даёт время с точностью до нескольких миллисекунд (в языке С++ она описана в заголовочном файле time.h). После выполнения процедуры, реализует алгоритм, мы находим разность времени
TikTak=cloc() - TikTak;
После всех проделанных манипуляций нужно прировнять к нулю все частные производные. Это будет выглядеть, в общем виде, примерно так:
После раскрытия скобок и замены T(n)= T(n)=(c,t(n))= 
получим
Положим Аij=(ti, tj) и B=(ti,TikTak) => мы получили систему уравнений AX=B, где Х=С. Формирование в матрице столбцов А и столбцов В записывается очень легко используя любой алгоритмический язык. После заполнения матрицы её остаётся решить и вывести решения этой задачи. Решение производиться методом Жордана.
Априорная временная оценка процедур.
Процедура вывода графа на экран в последовательном представлении:
Void prin3(Array *X, int N1, int N)
X – граф в связаном представлении
N – количество вершин графа.
N1 – количество дуг в графе Х
O(N,N1)=N*N1
Процедура вывода графа на экран в связаном представлении:
Void print3(Spisok **X, int N)
X – граф в связаном представлении
N – количество дуг в графе.
O(N)=N
Процедура вычисления разности графов с возвращающим значением последовательного графа:
Array * RaznostZ(int n, int &n1, Array *X, Spisok **Y,Array *Z)
N - количество дуг графа
N1 – количество вершин в графе Х
X – грав в последовательном представлении
Y - грав в связаном представлении
Z – грав в последовательном представлении
O(N,N1)=N1*N*k=N1*N2
N2 – количество вершин в графе Y
Процедура вычисления разности графов с возвращающим значением последовательного графа:
Spisok * RaznostY(int n, int &n1, Array *X, Spisok **Y)
N - количество дуг графа
N1 – количество вершин в графе Х
X – грав в последовательном представлении
Y - грав в связаном представлении
O(N,N1)=N1*N*(k+l)=N1*(N3+N2)
N2 – количество вершин в графе Y
N3 – количество вершин в графе Z – возвращаемом.
Процедура ввода графов в последовательном представлении:
Spisok **ReadFileY( Spisok **Y, char *st)
St – указатель на строку с именем файла из которого будет происходить ввод
Y - грав в связаном представлении
O(N,N1)=N+N2
N2 – количество вершин в графе Y
Процедура ввода графов в последовательном представлении:
Array *ReadFileY( Array *X, char *st)
St – указатель на строку с именем файла из которого будет происходить ввод
X – грав в последовательном представлении
O(N,N1)=N2
N2 – количество вершин в графе X
Текст программы.
# include<iostream.h>
# include<time.h>
# include<stdlib.h>
# include<fstream.h>
# include<conio.h>
# include <math.h>
///////////////////////////////////////////////////////////////////////////////////////////////////////
struct Spisok //Связанное представление графа
{ int index; //Содержвтельная "ячейка"
Spisok *next; //Следуюцая "дуга"
};
///////////////////////////////////////////////////////////////////////////////////////////////////////
struct Array //Последовательное представление графа
{ int I; //из какой вершины
int J; //в какую вершину
};
///////////////////////////////////////////////////////////////////////////////////////////////////////
inline double fun1(double N_X,double N_Y,double N_Z){ return N_X*(N_Y+N_Z);}
inline double fun2(double N_X,double N_Y,double N_Z){ return N_X+N_Y;}
inline double fun3(double N_X,double N_Y,double N_Z){ return N_X;}
inline double fun4(double N_X,double N_Y,double N_Z){ return N_Y;}
inline double fun5(double N_X,double N_Y,double N_Z){ return N_Z;}
inline double fun6(double N_X,double N_Y,double N_Z){ return 1;}
///////////////////////////////////////////////////////////////////////////////////////////////////////
const int N = 6, M = N+1;
double A[N][M];
double B[N][M];
typedef double(*MENU1)(double,double,double);
MENU1 MyMenu[6] = { fun1,fun2,fun3,fun4, fun5,fun6 };
////////////////////////////////////////////////////////////////////////////////
int gordanA(int n, int m)
{ int i, j, k, ir;
double s, c;
for (j = 0; j < n; j++){
for (s = 0, i = 0; i < (n - j); i++)if (fabs(A[i][j]) > fabs(s)) s = A[ir = i][j];
if(s==0)return -1;
for (k = j + 1; k < m; k++){
c = A[ir][k]/s;
for (i = 0; i < ir; i++)A[i][k] -= c * A[i][j];
for (i = ir + 1; i < n; i++)A[i - 1][k] = A[i][k] - c * A[i][j];
A[n - 1][k] = c;
}
}
return 0;
}
///////////////////////////////////////////////////////////////////////////////
long double Stp(int a, int n)
{
long double c,bi;
int k;
c=1;
k=n;
bi=a;
while(k>0){
if(k%2==1)c*=bi;
bi*=bi;
k/=2;
}
return c;
}
///////////////////////////////////////////////////////////////////////////////////////////////////////
void CursorOff(void)
{asm{
mov ah,1
mov ch,0x20
int 0x10
}
}
///////////////////////////////////////////////////////////////////////////////////////////////////////
Spisok **GenSeY(int Mas_y,int & Counter)
{ Counter=0;
Spisok **Y = new Spisok* [Mas_y];
for (int i = 0; i< Mas_y; i++){
int m = 0;
int *Pro = new int [Mas_y];
Spisok *beg = NULL, *end = NULL ;
for (int j = 0; j< Mas_y; j++){
int k = random(Mas_y);
int flag = 0;
for (int j = 0; j< m; j++)if (k==Pro[j]) flag = 1;
if (k != 0 && flag == 0){
Pro[m] = k;
m++;
if ((beg==NULL) && (end==NULL)){
end=new(Spisok);
if (end == NULL) {cout << "Lack of memory";exit (1);}
beg=end;
}
else{
end=end->next=new (Spisok);
if (end==NULL) {cout <<"L a c k of m e m o r y !"; exit (1);}
}
end->next=NULL;
end->index = k;
Counter++;
}
}
Y [i] = beg;
delete [] Pro;
}
return Y;
}
////////////////////////////////////////////////////////////////////////////////
Array *GenSeX(int Mas_y,int & Counter)
{ Counter=0;
Array *X = new Array[Mas_y*Mas_y];
if(X==NULL){cout<<"\n net u mena stolko pamaty!!!\n";exit(1);}
randomize();
for (int i = 0; i< Mas_y; i++){
int m = 0;
int *Pro = new int [Mas_y];
for (int j = 0; j< Mas_y; j++){
int k = random(Mas_y);
int flag = 0;
for (int j = 0; j< m; j++)if (k==Pro[j]) flag = 1;
if (k != 0 && flag == 0){
X[Counter].I=i;
X[Counter].J=k;
Pro[m] = k;
m++;
Counter++;
}
}
delete [] Pro;
}
return X;
}
////////////////////////////////////////////////////////////////////////////
int Number(int & kol2,char *st )
{ int N;
ifstream file;
int kol1 = 0; kol2 = 0;
file.open(st);
if (!file) cerr <<"Can not open file!!!!!";
else
{file >> N;
file.get();
for( int i = 0; i <2*N ; i++)
{char *string = new char[3*N];
file.getline(string,3*N,'\n');
for( int j = 0; string[j] != '0' ; j++ )
{if (string[j] == ' ')
//{if((j%2!=0)||(j > N*3))
// {cout <<"error in file "<<st;return 0;}
if (i<N) kol1++;
else kol2 ++;
}
delete [] string;
}
}
file.close();
//cout << kol1 <<"\t"<< kol2;
return kol1;
}
////////////////////////////////////////////////////////////////////////////////
Array *ReadFileX(Array *X,char * st )
{
ifstream file;
int n;
file.open(st);
if (!file) cerr <<"Can not open file!!!!!";
else
{file >> n;
file.get();
int k = 0,n1=0;
for(int i=0; i < n; i++){
file >> n1;
while (n1 != 0){
X[k].I = i;
X[k].J = n1-1;
k++;
n1=0;
file >> n1;
//cout << X[k-1].I<< "\t"<<X[k-1].J<<"\n" ;
}
}
}
file.close();
return X;
}
////////////////////////////////////////////////////////////////////////////////
Spisok **ReadFileY(Spisok **Y,char *st )
{
int n;;
ifstream file;
file.open(st);
if (!file) cerr <<"Can not open file!!!!!";
else
{file >> n;
file.get();
for(int i=0; i < n; i++)
{
char *string = new char[580];
if (string == NULL) {cout << "Lack of memory";exit(1);}
file.getline(string,580,'\n');
delete [] string;
}
for(int j=0; j < n; j++)
{
int n1;
file >> n1;
Spisok *beg=NULL,*end = NULL;
while (n1 != 0)
{ if ((beg==NULL) && (end==NULL))
{ end=new(Spisok);
if (end == NULL) {cout << "Lack of memory";exit (1);}
beg=end;}
else
{ end=end->next=new (Spisok);
if (end==NULL) {cout <<"L a c k of m e m o r y !"; exit (1);}}
end->next=NULL;
end->index = n1-1;
file >> n1;
}
//file >> n1;
Y[j] = beg; }
}
file.close();
return Y;
}
////////////////////////////////////////////////////////////////////////////////
void print3(Array *X,int N1,int N)
{
int k = 0;
for ( int i = 0; i< N; i++){
cout <<'\n'<<i<<": ";
for (k=0 ; k < N1 ; k++)if( X[k].I == i)cout << X[k].J<<' ';
}
}
////////////////////////////////////////////////////////////////////////////////
void print2(Spisok **X,int N)
{ for (int i=0;i<N;i++){
cout <<"\n"<<i<<": ";
Spisok *rex = X[i];
while (rex != NULL){
cout << rex -> index << " " ;
rex = rex->next;
}
}
}
////////////////////////////////////////////////////////////////////////////////
void WriteFile(char *st,int Mas_y)
{
ofstream F;
F.open(st);
randomize();
if (!F) cout << "Can not open file "<< st;
F << Mas_y<<"\n";
for (int i = 0; i< 2*Mas_y; i++)
{ int m = 0;
int *Pro = new int [Mas_y];
for (int j = 0; j< Mas_y; j++)
{int k = random(Mas_y+1);
int flag = 0;
for (int j = 0; j< m; j++)
{if (k==Pro[j]) flag = 1;}
if (k != 0 && flag == 0)
F<< k <<" " ;
Pro[m] = k;
m++;
}
delete [] Pro;
F<<"0\n";
}
F.close();
}
////////////////////////////////////////////////////////////////////////////////
///////////////////////////////////////////////////////////////////////////////////////////////////////
int HowMuch(char *FileName)
{//читаем первую строчку файла и узнаём сколько вершин в графе.
ifstream file;
int n=0;
file.open(FileName);
if (!file) cerr <<"Can not open file!!!!!";
else file >> n;