. , , ,

,,,

,

.

-

. ..

:

: ..

: _____________

: _____________

: ..

: 3-2-26

1998

1. .

:

X Y N (X , Y ) . 򠠠 . - , .

:

(X/Y). Z , X .

:

: Array, I ( , ) J ( , ).

Array[_]

I

J

Array[ 1 ]

From

To

Array[ 2 ]

From

To

From

To

Array[ N ]

From

To

N X.

: Spisok index, : index ( , ) Next - Spisok,

Spisok[ _ ]

NEXT

index

next

index

next

Index

Next

Spisok[ 1 ]

To

To

NULL

To

To

NULL

Spisok[ N ]

To

To

NULL

N - Y,Z.

2. .

, :

N

X11 X12 ... X1k1 0

X21 X22 ... X2k2 0

...

XN1 XN2 ... XNkN 0

Y11 Y12 ... Y1k1 0

Y21 Y22 ... Y2k2 0

...

YN1 YN2 ... YNkN 0

N -

Xij - i X (i = 1..N, j=1..ki)

Yij - i Y(i = 1..N, j=1..ki)

- , ( 0 - 2 ). , N .

:

X Y .

.

X ( ):

1 : X11 X12 ... X1k1

2 : X21 X22 ... X2k2

...

N : XN1 XN2 ... XNkN

Y ( ):

1 : Y11 Y12 ... Y1k1

2 : Y21 Y22 ... Y2k2

...

N : YN1 YN2 ... YNkN

Z ( ):

1 : Z11 1,Z12 ... Z1k1

2 : Z21 Z22 ... Z2k2

...

N : ZN1 ZN2 ... ZNkN

X ( ):

1 : X11 X12 ... X1k1

2 : X21 X22 ... X2k2

...

N : XN1 XN2 ... XNkN

- , - X, - Y

- , X Y:

N MX MY T

T - - , X Y

Zij - i Z(i = 1..N, j=1..ki)

MX - - X

MY - - Y

:

, , - , .

:

1.      : ;

2.      : ;

, 30 . 80 , 30 110 110216/3. , int 216. , . , , , 33000 , , .

.

, , - . , ..

.

 

.

 

, , .

.

, . :

1.     

2.      , .

, . N CN2, , , , N.

.

, , .

, . : .

, 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

# include

# include

# include

# include

# include

///////////////////////////////////////////////////////////////////////////////////////////////////////

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 "<

if (i

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"<

}

}

}

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'<

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

cout <<"n"<

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<<"0n";

}

F.close();

}

////////////////////////////////////////////////////////////////////////////////

///////////////////////////////////////////////////////////////////////////////////////////////////////

int HowMuch(char *FileName)

{// .

ifstream file;

int n=0;

file.open(FileName);

if (!file) cerr <<"Can not open file!!!!!";

else file >> n;

return n;

}

///////////////////////////////////////////////////////////////////////////////////////////////////////

Array *RaznostZ(int n,int &n1,Array *X,Spisok **Y,Array *Z)

/*

N - - , N2 - - Y.*/

{float i,j,newn=0;

Array *newX = new Array [n1]; //

//cout<<' ';

for(i=0;i

for(j=0;j

if(X[i].I==j){//cout<<"b"; // ...

Spisok *max=Y[j]; //max Y[j]

int Flag=0; //

while(max!=NULL){ // ""

if(X[i].J==max->index){Flag=1;break;}// ,

max=max->next; //

}

if(Flag==0){ // , ... :

newX[newn].I=X[i].I;

newX[newn].J=X[i].J;

newn++;

}

//cout<<"b|";

}

//cout<<"b/";

}

//cout<<"b b";

n1=newn;

delete [] Z;

return newX;

}

////////////////////////////////////////////////////////////////////////

void DeleteY(Spisok **Z,int n)

{int i=0;

Spisok *rex;

for(i=0;i

rex=Z[i];

while(rex!=NULL){Z[i]=rex->next;delete rex;rex=Z[i];}

delete Z[i];

}

delete [] Z;

}

////////////////////////////////////////////////////////////////////////////////

Spisok** RaznostY(int n,int n1,Array *X, Spisok **Y)

{/* Z=X-Y

Z,Y - , X - .

n - - , n1 - - */

int i,j;

Spisok **Z = new Spisok *[n];//

for (i=0;i

//cout<<' ';

for(i=0;i

for(j=0;j

if(X[i].I==j){//cout<<"b"; // ...

Spisok *max=Y[j]; //max Y[j]

int Flag=0; //

while(max!=NULL){ // ""

if(X[i].J==max->index)Flag=1;// ,

max=max->next; //

}

if(Flag==0){ // , ... :

Spisok *end=Z[j], *beg=Z[j], *pred=Z[j];

while (end !=NULL) {pred = end ;end = end ->next;}

end = pred;

if((beg==NULL)&&(end==NULL))Z[j]=beg=end=new(Spisok);

else end = end -> next = new (Spisok);

end -> next = NULL;

end -> index = X[i].J;

}

//cout<<"b|";

}

//cout<<"b\";

}

//cout<<"b b";

DeleteY(Y,n); // !

return Z;

}

///////////////////////////////////////////////////////////////////////////////////////////////////////

void Demo(void)

/* -

- */

{ int n=4,N2;

clrscr(); //

CursorOff();

cout<<"tt ."<

char st [] ="GrapH.txt"; //

cout<<"tt : "<

WriteFile(st,n); //

n=HowMuch(st); //

int N1 = Number(N2,st); //

Array *X = new Array [N1]; //

X = ReadFileX(X,st); //

cout << "n X ";

print3(X,N1,n); //

Spisok **Y = new Spisok *[n]; //

for (int i=0;i

Y = ReadFileY(Y,st); //

cout << "n Y ";

print2(Y,n); //

Array *Z = new Array[n]; //

int nZ=N1;

Z=RaznostZ(n,nZ,X,Y,Z); // : - ,

// .

cout<<"n Z=X-Y ";

print3(Z,nZ,n); //

//Spisok **Z1 = new Spisok *[n];//

//for (i=0;i

Y=RaznostY(n,N1,X,Y); // Y

cout<<"n Y - "; // - " "

print2(Y,n); //

delete [] X; //

delete [] Z;

DeleteY(Y,n); // !

//DeleteY(Z1,n); // !

cout<<"ntttPress Any Key to continueb"<

getch(); //

}

////////////////////////////////////////////////////////////////////////////////

void TimeOut(int Tik, float TikTak[], int Mas_x[], int Mas_y[],int Mas_z[])

{

clrscr();

int i=0,j=0,k=0,h=0,count=0;

cout<<'n';

for(;i

for (k = 0; k < Tik; k++)

for (i = 0; i < Tik; i++){

for (int j = 0; j < Tik; j++) A[i][j] += (*MyMenu[j])(Mas_x[k],Mas_y[k],Mas_z[k]) * (*MyMenu[i])(Mas_x[k],Mas_y[k],Mas_z[k]);

A[i][N]+=(*MyMenu[i])(Mas_x[k],Mas_y[k],Mas_z[k])*TikTak[k];

}

if(gordanA(N,M))cout<<" !!!"; //N- , M--

//for(i=0;i

cout<<"ttt O(nX,nY,nZ)=C1*nX*(nY+nZ)"<

for(i=0;i

cout<<"nn , "

<<"ntPress any key ."<

getch(); //

TimeOut(Tik,TikTak,Mas_x,Mas_y,Mas_z);//

cout<<"nntt Press Any Key for exit to you system."<

getch(); //

}

///////////////////////////////////////////////////////////////////////////

void main (void)

{

Demo();

TestTime(85);

}

///////////////////////////////////////////////////////////////////////////

 

 

 

 

 

 

 

 

 

 

 

.

, ( 4 ), . , , , .

.

: GrapH.txt

X

0: 2

1: 1 3 0

2: 2 0 3

3: 3 0

Y

0: 1 3

1: 1 0

2: 3 2

3: 2 3 1

Z=X-Y

0: 2

1: 3

2: 0

3: 0

Y -

0: 2

1: 3

2: 0

3: 0

Press Any Key to continue

:

- ...

= 85

RaznostZ... ...

RasnostY... ?! :9

= 90

RaznostZ... ...

RasnostY... ?! :9

= 95

RaznostZ... ...

RasnostY... ?! :9

= 100

RaznostZ... ...

RasnostY... ?! :9

= 105

RaznostZ... ...

RasnostY... ?! :9

= 110

RaznostZ... ...

RasnostY... ?! :9

,

Press any key .

:

O(nX,nY,nZ)=C1*nX*(nY+nZ)

C0=3.894613e-06

C1=1.953171e-06

C2=1.941442e-08

C3=7.187807e-12

C4=3.05476e05

- ՠ - Y - Z 򠠠

70 3028 3045 1120 0.06044 0.058657

75 3507 3531 1289 0.071429 0.074507

80 4032 3978 1471 0.082418 0.082331

85 4488 4577 1608 0.104396 0.103425

90 5136 5061 1898 0.126374 0.125175

95 5692 5638 2075 0.137363 0.138322

Press Any Key for exit to you system.

. .

. - . ..

 

 

 

! , , , .
. , :