-













































:

:

1

2

3

4

5

6


1

, :

3 , :

xyz

x|z

x|y

x V y V z

(x|z)( x|y)

f

000 1 1 0 1 0
001 1 1 1 1 0
010 1 1 1 1 0
011 1 1 1 1 0
100 1 1 1 1 0
101 0 1 1 0 0
110 1 0 1 0 0
111 0 0 1 0 0

0 x,y,z. .

2

:


xyz f
000 0
001 1
010 1
011 0
100 0
101 0
110 1
111 0

:

:

:

3

:

:

xyz xy

f
000 0 1 0
001 0 0 1
010 0 1 0
011 0 0 1
100 0 1 0
101 0 0 1
110 1 1 1
111 1 0 0

( ) ( ):

():

():

4

:

:

zt 00 01 11 10
xy
00 1 1 0 0
01 1 0 0 0
11 1 0 0 1
10 0 0 1 0

:

( ):

( ):

5

( ). , ( )

:

1 2 3 4 5
1 0 1 1 0 0
2 0 0 1 1 0
3 0 0 0 1 1
4 0 0 0 0 1
5 0 0 0 0 0

1 4:

1.  1-3-4

2.  1-2-4

6

14 ( , 1 20). , 1 8 . .


//---------------------------------------------------------------------------

#include <clx.h>

#pragma hdrstop

//---------------------------------------------------------------------------

#pragma argsused

//

// ( ).

// S T.

#include <iostream.h>

#define MaxNodes 14

#define B 1000 // .

// .

typedef struct Zveno *svqz;

struct Zveno

{

int Element;

svqz Sled;

};

class Spisok

{

private:

int A[MaxNodes][MaxNodes]; // .

int D[MaxNodes]; //

// .

svqz Stack; // .

void UDALENIE (svqz *, int *);

void W_S (svqz *, int);

int Pusto_Q (int *);

public:

Spisok() {Stack = NULL;}

void Vvod_Ves();

void Reshenie ();

};

void main ()

{

Spisok A;

A.Vvod_Ves();

A.Reshenie();

}

int Spisok::Pusto_Q (int *Q)

{

for (int i=0;i<MaxNodes;i++)

if ( *(Q+i)!=0 ) return 0; // - !

return 1; // - !

}

void Spisok::Reshenie ()

{

int S; // ().

int T; // .

int u,v,Min;

int i,j,k;

svqz UkZv;

int Q[MaxNodes];

cout << "input source : ";

cin >> S; S--;

//.

for (i=0;i<MaxNodes;i++) { D[i] = A[S][i]; Q[i] = 0; }

D[S] = 0;

for (i=0;i<MaxNodes;i++) Q[i] = 1;

Q[S] = 0;

//

// .

while (!Pusto_Q(&Q[0])) // Q .

{

Min = B;

for (i=0;i<MaxNodes;i++)

if (Q[i]==1 && D[i]<Min) { Min = D[i]; u = i; }

Q[u] = 0;

for (i=0;i<MaxNodes;i++)

if (Q[i] == 1)

if ( D[i] > D[u]+A[u][i] ) D[i] = D[u] + A[u][i];

}

//

// .

cout << "matrix of distanses: \n";

for (i=0;i<MaxNodes;i++) cout << D[i] << " ";

cout << endl;

// -----------------------------------------------------

// S T

// .

// -----------------------------------------------------

cout << "Inpute finish node: ";

cin >> T; T--;

W_S (&Stack,T); v = T;

while ( v!=S )

{

for (i=0;i<MaxNodes;i++)

if ( D[v]==D[i]+A[i][v] ) u = i;

W_S (&Stack,u);

v = u;

}

// .

cout << "Minimal path: ";

UkZv = Stack;

while ( UkZv != NULL )

{ cout << (UkZv->Element+1) << " ";

UkZv = UkZv->Sled; }

cout << endl;

}

void Spisok::Vvod_Ves()

// .

{

cout << "Inppute the elements of edge matrix by strings:\n";

for (int i=0;i<MaxNodes;i++)

for (int j=0;j<MaxNodes;j++)

{

cout << "Inpute A[" << (i+1) << "," << (j+1) << "]: ";

cin >> A[i][j];

if ( A[i][j]==0 ) A[i][j] = B;

}

}

void Spisok::W_S (svqz *stk, int Elem)

// Elem stk.

{

svqz q=new (Zveno);

(*q).Element = Elem;

(*q).Sled = *stk; *stk = q;

}

void Spisok::UDALENIE (svqz *stk, int *Klad)

// , *stk.

// -

// Klad.

{

svqz q;

if (*stk==NULL) cout<<"try to select from the empty stack!\n";

else

{ *Klad = (**stk).Element;

q = *stk; *stk = (**stk).Sled; delete q; }

}

:

//---------------------------------------------------------------------------


#include <clx.h>

#pragma hdrstop

//---------------------------------------------------------------------------

#pragma argsused

#include <iostream.h>

#define TRUE 1

#define FALSE 0

typedef int Boolean;

typedef unsigned int SubInt;

typedef struct Uzel *Ref;

struct Uzel

{

SubInt X; // .

SubInt Y; //

int Pay; // .

Ref Left; // .

Ref Right;// .

};

typedef struct zveno *svqz;

struct zveno

{

unsigned int Element[256];

svqz Sled;

zveno();

};


zveno::zveno()

{

for(int k=0;k<256;Element[k++]=0);

}

class Spisok

{

private:

Ref Root;

void Search (int, int, int, Ref *);

void Poisk (svqz, SubInt, svqz *);

void Postroenie (svqz *);

void Udalenie (svqz *, svqz);

public:

Spisok() { Root = NULL;} // .

void Reshenie();

void Postr();

};

void Spisok::Search (int A, int B, int C, Ref *p)

// , A,B,C, *p.

{

if ( (*p) == NULL )

{

(*p) = new (Uzel); (**p).X = A; (**p).Y = B; (**p).Pay = C;

(**p).Left = (**p).Right = NULL;

}

else

if ( C<=(**p).Pay ) Search (A,B,C,&((**p).Left));

else

if ( C>(**p).Pay ) Search (A,B,C,&((**p).Right));

}

void Spisok::Postroenie (svqz *UkStr)

//p p

// , .

{

svqz UkZv;

int el;

(*UkStr) = new (zveno);

UkZv = (*UkStr); UkZv->Sled = NULL;

cout << "Input nodes: \n";

cin >> el;

while ( el!=0 )

{

UkZv->Sled = new (zveno); UkZv = UkZv->Sled;

UkZv->Element[el] = 1; UkZv->Sled = NULL;

cin >> el;

}

}

void Spisok::Postr()

//p p, .

{

int A,B,C;

cout << "For every nodes input input start and finish\n";

cout << "node and cost of edge:\n";

cin >> A >> B >> C;

while ( A!=0 )

{ Search (A,B,C,&Root);

cin >> A >> B >> C;

}

}

void Spisok::Poisk (svqz st, SubInt MENT, svqz *Res)

{

svqz q;

(*Res) = NULL; q = st->Sled;

while ( q != NULL && (*Res) == NULL )

{

if ( q->Element[MENT]==1 ) (*Res) = q;

else q = q->Sled;

}

}

void Spisok::Udalenie (svqz *zv, svqz UkStr)

// p

//, zv.

{

svqz Z; //"p" .

svqz UkZv1; //"H" .

if ( (*zv)->Sled != NULL ) (**zv) = *((**zv).Sled);

else

{ Z = UkStr; UkZv1 = UkStr->Sled;

while (UkZv1 != (*zv))

{ Z = UkZv1; UkZv1 = UkZv1->Sled; }

Z->Sled = NULL; delete UkZv1;

}

}

void Spisok::Reshenie()

{

svqz UkStr; // .

Ref UkUzel; // .

Ref UkUzel1; // .

SubInt T1,T2;

svqz Res1,Res2;

// .

Postroenie (&UkStr);

cout <<"Edges with minimsl cost: ";

while ( UkStr->Sled->Sled != NULL )

{

UkUzel1 = Root; //"" .

UkUzel = Root->Left; //"" .

if ( UkUzel== NULL )

{ // ...

T1 = Root->X; T2 = Root->Y;

//... .

Root = Root->Right; delete UkUzel1;

}

else

{ // ...

while ( UkUzel->Left != NULL )

{

UkUzel1 = UkUzel1->Left;

UkUzel = UkUzel->Left;

}

T1 = UkUzel->X; T2 = UkUzel->Y;

//... .

UkUzel1->Left = UkUzel->Right;

delete UkUzel;

}

// v w

// W1 W2 VS ...

Res1 = Res2 = NULL;

Poisk (UkStr,T1,&Res1);

Poisk (UkStr,T2,&Res2);

if ( Res1!=Res2 )

for (int k=0;k<256;k++)

}

}

void main ()

{

Spisok Tree;

Tree.Postr();

Tree.Reshenie();

}


 

1.  .., .. / . ., 1992.

2.  . . . .: , 1978.

3.  . . .: , 1977.

4.  .. .1974


2012 , .