книги из ГПНТБ / Алферова, З. В. Математическое обеспечение экономических расчетов с использованием теории графов

кон;

библ

('ВВОДЗ',

'Г,

А);

Т 2 : = '

';

Т2[элем 30:71] : ^ ' Р Е З У Л Ь Т А Т Ы ОБСЛЕДОВАНИЯ ПОТОКОВ ИН­

ФОРМАЦИИ';

библ

('АЦПУГ,

Т2);

К М : = — 0 ;

Ц :

Т И : = '

'; Т П : = '

' ; Т Р : = '

' ; В Н П : = '

'; Т2 : = '

';

Т2Гэлем_ 30:63] : = ' — ' ;

библ

('АЦПУГ, Т2);

ТИГэлем

1 0 : 4 4 ] : = ' И С Х О Д Н Ы М И

ЯВЛЯЮТСЯ

ДОКУМЕНТЫ НО­

М Е Р : ' ;

ТП[элем

10:49] : = ' П Р О М Е Ж У Т О Ч Н Ы М И

ЯВЛЯЮТСЯ

ДОКУМЕНТЫ

Н О М Е Р : ' ;

TP [элем

10:48] : = ' Р Е З У Л Ь Т А Т Н Ы М И

ЯВЛЯЮТСЯ

ДОКУМЕНТЫ

Н О М Е Р : ' ;

ВНП[элем

3 0 : 6 3 ] : = ' : Н О М Е Р

ДОКУМЕНТА

: П О Р Я Д О К

ДОКУМЕН ­

ТА:';

К : = 5 1 ; М : = 5 1 ; Р 1 : = 5 1 ; Н : = 5 3 ; Л : = 5 3 ; П : = 5 3 ; С : = 0 ;

библ

('АЦПУГ,

ВНП);

библ

('АЦПУГ,

Т2);

Т 2 : = '

'; В : = 0 ; Н Д : = 1;

БЛЗ:

С Ч : = 0 ; И : = 1;

то на

Б Л 4 :

если

А[И

элем

2 6 : 3 7 ] = Н Д

БЛ8;

если

А[И

элем

14:25] =И=0

то _на_ БЛ7;

Ы : = Н Д ;

ВЫВ (Ы, Р ) ; ТЩэлем

К:Н] : = Р [ э л е м

8:10];

К : = К + 3 ;

Н : = Н + 3 ;

если

К5&120

то

на

МЗГ,

АА:

Т2[элем

54:55] : = С [элем

30:37];

Т2[элем

41:43] : = Р [ э л е м

8:10];

для Я : =30, 46, 63, цикл Т2[элем Я] : = ' : ' ;

библ

('АЦПУГ,

Т2);

на

БЛ14;

Б Л 7: С Ч : = С Ч + 1 ;

Б Л 8 :

И: = И + 1;

если А [ И ] ^ К М то_на_БЛ4;

если

С Ч = 1 ,

то

на_ БЛ13;

если СЧ = 0 то_на_БЛ15; Ы: = Н Д ;

ВЫВ

(Ы, Р ) ;

ТП[элем

М : Л ] : = Р [ э л е м

8:10];

М : = М + 3 ;

Л : = Л + 3 ;

если

М > 1 2 0

то

на

М П ;

БЛ14:

Н Д : = Н Д + 1 ;

на

БЛЗ;

Б Л 1 3 :

Ы : = Н Д ;

ВЫВ (Ы, Р ) ; TP [элем

Р 1 : П ] = Р [ э л е м

8:10];

П : = П + 3 ;

Р 1 : = Р 1 + 3 ;

если

П ^ 1 2 0

_то

_н_а

М21;

на

БЛ14;

Б Л 1 5 : И : = 1; Ж : = 1; П С : = 0 ;

БЛ18:

Н Д : = — А [ И ] ; И : = И + 1 ;

С: = 1;

Б Л 2 1 :

если

А[И

элем

14:25] ФО

то

на_

БЛ28;

БЛ22:

И : = И + 1 ;

если А[И] ^ 0 то

на_ БЛ21; если

А [ И ] = ^ К М то на

БЛ21;

БЛ25:

Ы : = Н Д [ э л е м

26:37];

ВЫВ

(Ы,

Р ) ;

Т2[элем

41:43]: = Р [ э л е м 8:10];

Т2[элем

64

: 55] : = В [ э л е м

34:37];

для Я : =30,46,63 цикл Т2[элем

Я] : = ' : ' ;

библ

('АЦПУГ, Т2); Н В [ Ж

элем

14:25] : = Н Д ;

Н В [ Ж

элем

26:37]:= В;

Ж : = Ж + 1 ;

если

П С < В

то

на_ БЛ18;

П С : = В ;

на_

БЛ18;

БЛ28:

если

А [И] < 0

то на

БЛ25;

Г : = И ;

БЛ30:

С : = С + 1 ;

Ш Д : = — А [ И ] ;

И : = 1;

Б Л 33:

если

А [ И ] = Ш Д

то на

БЛ35;

И : = И + 1 ;

на

БЛЗЗ;

Б Л 3 5 :

И : = И + 1 ;

если

А [ И ] < 0

то

на

БЛ38;

если

А [И

элем

14:25] = 0

то на

БЛЗО;

на

БЛ35;

БЛ38:

если

А [ И ] = К М

то

на

БЛ40;

И : = Т + 1 ;

на

БЛ41;

Б Л40:

Т 2 : = ' — ' ;

библ

('АЦПУГ,

Т2);

библ

('АЦПУГ,

ТИ);

библ

('АЦПУГ,

ТП);

библ

('АЦПУГ,

Т Р ) ^

на

БЛ44;

Б Л 4 1 :

если

С < В

то

на

БЛ43;

В : = С ;

БЛ43:

С: = 1; на БЛ21;

М П :

библ

('АЦПУГ,

ТП);

М : = 5 1 ;

Л : =53;

на

БЛ14;

М21:

библ

('АЦПУГ,

TP);

P I : =51;

П: =53;

на

БЛ14;

М31:

б_ибл

('АЦПУГ,

ТИ);

К: =51;

Н : = 5 3 ;

на

АА;

БЛ44:

ТИ [элем

30:66]:='—';

библ ('АЦПУГ,

ТИ);

Т И : = '

' ;

библ

('АЦПУГ,

ТИ);

ТЩэлем

3 0 : 6 6 ] : = ' : Н О М Е Р

ДОКУМЕНТА

:НОМЕР

ТАКТА ГАШЕ­

Н И Я : ' ;

библ

('АЦПУГ,

ТИ);

ТИ[элем 30:60]:='—'; библ ('АЦПУГ,

ТИ);

Н Д : = 1;

БЛ45:

Т Г : = 0 ; И: = 1;

БЛ47:

если

А [ И ] > 0

то

на

БЛ54;

Г : = И ;

БЛ49:

И : = И + 1 ;

если

А[И]=^КМ _ го на БЛ47;

Н Д : = Н Д + 1 ;

если

Т Г = 0

то

_н_а КОН;

Н : = Н Д ;

ВЫВ(Ы,

Р ) ;

ТИ [элем

37:39] : = Р [элем 8:10];

Ы : = Т Г ;

ВЫВ

(Ы, Р ) ;

для

Я : =30, 46, 66

цикл

ТЩэлем

Я]

: = ' : ' ;

ТИ [элем

58 : 60]: = Р [ э л е м

8:10] ;

библ

('АЦПУГ,

ТИ); _на БЛ45;

БЛ54:

если

А [И

элем

14:25] ^ Н Д _ т о _на

БЛ58;

Ж : = Ж + 1 ;

БЛ56:

если

НВ[Ж

элем

14:25]= А [Г элем

26:37]

то

на

БЛ58;

Ж : = Ж + 1 ;

_на

БЛ56;

БЛ58:

если

Т Г > Н В

[Ж

элем

26:37]

_го

на

БЛ49;

КОН:

кощ

§

7. 3.

ОПРЕДЕЛЕНИЕ ОБЪЕМОВ ИНФОРМАЦИИ

нач цел мае Т[3], 3[3, 10], АЦ[2,10], А1[7], А2[8], А3[18], А4[22],

А5[28],

А6[30],

А7[16],

А8[12],

А9[10],

А10[17];

цел

Л,

К,

A3,

Ц З ,

AT,

ЦТ,

03,

ОТ;

процедура

ДОКУМЕНТ

(Д,

Р,

KB,

OA,

О Ц ) ; значение

Р, KB;

цел

Р,

KB,

OA,

ОЦ;

цел

мае

Д;

нач

цел

И, Ж , ОД, РО, P I ,

Р2, ВХОД,

ВЫХОД,

Б, ПА,

ПЦ;

Р 2 : = К В + 1 ; Р 1 : = К В + 2 ; Р О : = К В + 3 ; Б : = Д [ К В ] ;

ВЫХОД: = Б [элем

1:13]; О А : = 0 ;

О Ц : = 0 ; для

И : = Р 2 : Р

цикл

нач

Б : = Д [ И ] ;

если

Б [элем

1 : 13] ^Р2 _ то _ на

МЗ;

ВХОД: = Б [элем

14 : 25];

для

Ж : = Р 2 : Р

цикл

нач

Б : = Д [ Ж ] ;

если

Б [элем

14:25] = В Х О Д Л Б

[элем

1:13]

= Р 1

то

на

M l ;

если

Б [элем

14:25] = В Х О Д Л Б [элем

1:13] = Р О

то

на

М2;

на

М7;

M l :

ПА: = Б [ э л е м 26:37]; _на

М7;

М2:

П Ц : = Б [ э л е м

26:37];

М7:

кон;

Мб:

для

Ж: = 1 : KB—1 цикл

нач

Б : = Д [ Ж ] ;

если

Б [элем

1:13] ^ ВХОД

то_ на_ М4;

П А : = П А х Б

[элем

26:37];

П Ц : = П Ц х Б [ э л е м

26:37];

если

Б [элем

14:25] =ВЬ1ХОД_го_на М5;

ВХОД: = Б [элем

14:25]; на Мб;

М 5 :

О А : = О А + П А ;

О Ц : = О Ц + П Ц ;

_на

МЗ;

М4:

кон;

МЗ:

кощ

О Д : = О А + О Ц ;

П А : = О А ;

П Ц : = О Ц ;

библ

('ВЫВОДГ,

'11 Г,

ПА,

ПЦ,

О Д ) ;

кон;

библ

('ВВОДЗ*, Т ,

А1); ДОКУМЕНТ (А1, 7, 3, АЦ[1, 1], АЦ[2, 1]);

библ

('ВВОДЗ',

'Г,

А2);

ДОКУМЕНТ

(А2,

8, 4, А Ц [ 1 , 2 ] , А Ц [ 2 , 2 ] ) ;

библ

('ВВОДЗ',

'Г,

A3);

ДОКУМЕНТ

(A3,

18,

8,

А Щ 1 . 3 ] ,

А Ц [ 2 , 3 ] ) ;

библ

('ВВОДЗ',

'Г,

А4);

ДОКУМЕНТ

(А4,

22,

15, А Щ 1 . 4 ] ,

АЦ[2,4]);

библ

('ВВОДЗ', Т , А5); ДОКУМЕНТ

(А5,

2, 15,

А Ц [ 1 , 5 ] ,

А Ц [ 2 , 5 ] ) ;

библ

('ВВОДЗ',

'Г,

А6);

ДОКУМЕНТ

(А6,

30,

20,

А Ц [ 1 , 6 ] ,

А Щ 2 . 6 ] ) ;

библ

('ВВОДЗ',

'Г,

А7);

ДОКУМЕНТ

(А7,

16,

9,

АЦ[1,

7],

АЦ[2,

7 ] ) ;

библ

('ВВОДЗ', Т , А8); ДОКУМЕНТ

(А8,

12,

5,

АЦ[1,

8],

АЦ[2,

8 ] ) ;

библ

('ВВОДЗ',

'Г,

А9);

ДОКУМЕНТ

(А9,

10,

6,

А Ц [ 1 , 9 ] ,

А Ц [ 2 , 9 ] ) ;

библ

('ВВОДЗ',

'Г, А10); ДОКУМЕНТ

(А10,

17,

7, А Ц [ 1 , 10], АЦ[2, 10]);

библ

('ВВОДЗ',

'Г,

Т); библ

('ВВОДЗ', ' 1 ' , 3 ) ;

А Т : = 0 ;

Ц Т : = 0 ; ^ л я

Л : = 1:3

цикл

нач

А3 = 0;

Ц 3 : = 0 ; _ д л я

К: = 1 : Ю

цикл

нач

если

3

[Л, К ] = 0

то на

Ф4;

Ц З : = Ц З + 3 [ Л , К ] Х А Ц [ 2 , К ] ; А З : = А З + 3 [ Л , К ] Х А Ц [ 1 , К ] ;

Ф4:

кон;

Р З : = Ц З + А З ; библ ('ВЫВОДГ,

'111%

A3, ЦЗ, О З ) ;

А Т : = А Т + А З Х Т [ Л ] ;

ЦТ: = Ц Т + Ц З Х Т [ Л ] ;

кон;

О Т : = А Т + Ц Т ;

библ

('ВЫВОДГ,

'111%

AT,

ЦТ,

ОТ);

кон;

§ 7. 4. ОЦЕНКА СЛОЖНОСТИ АЛГОРИТМОВ

Исходной информацией

для определения

оценки

сложности

является

граф

алгоритма,

представленный

в виде

соответствую­

щей матрицы смежности.

Блок-схема

построения

матрицы смежности

приведена на

рис.

37.

В блок-схеме приняты следующие условные

обозначения:

а

и Ь — элементы матрицы и вектора соответственно;

сто круглых скобок используются

минусы.

Процесс построения

матрицы состоит в заполнении именующих

строки и столбца матрицы, установлении

взаимосвязи элементов

вектора и перенесении этих связей в матрицу.

АЛГЭК-программа построения матрицы смежности по графу

может быть представлена следующим образом:

_нач

цел

мае

В [ 1 : Р ] ,

А[1:П,

1:Т];

цел

X, i , Т, П,

Р,

j ;

библ

('ВВОДЗ',

Т ,

В);

МЗ:

для

] : = 1:Т

цикл

нач

если

B [ X ] = a [ l , j ]

то_

на

M l ;

кон;

j : = T ;

a[i,

1 ] : = В [ Х ] ;

a[i,

j ] : = B [ X ] ;

M l :

T : = j ;

П : = 1 ;

i : = i + l ;

j : = j + l ;

X : = X + 1 ;

если

В [ Х ] = 0 _ т о

«а

M2;'_на

МЗ;

M2:

j

: =

l ;

i : =

l ;

X: =

l ;

M9:

если

B [ X ] < 0

то

на

М4;

Мб:

если

B [ X ] = a [ l , j ]

_то

на

М5;

i : = i + l ;

_на_

Мб;

М 5 :

a[i,- j ] : =

l

на

М7;

М4:

если

В[Х] = a [ i , 1]

_то

та

М7;

i : = i +

l ;

на_

М4;

М7:

Х : = Х + 1 ;

_еслл

В [ Х ] = 0 _ т о на М8; на

М9;

М 8 :

библ

('ВЫВОДГ,

'Г,

А);

~

кон;

На рис. 38

приведена блок-схема алгоритма оценки С Л О Ж Н О С Т И

по операциям,

где:

С Начало

А.

ввод

Организация цинла

ло I

дойных

Чистно ячеек

C(L)

±

~ ~

Организация

цинла

(^У*

Конец

цинла по Н

по

Ж

Вычисление

шага

Т*©

у

/

Печать

^

Q

Конец

J

/7 ••=/?•* ГРЛФ[иЖ)\

U •

=М

Конец

цинла по Ж

т

Рис. 38. Блок-схема оценки сложности

алгоритма

«ач цел В, Р, Н,

С, СС,

Л, Ф,

A l , А2, А, Б, К, И;

цел мае ННГ8.71, АА[4,25], Е[25], Ж [4,25], М[25],

Д[25], ГГ251-

библ

('ВВОДЗ',

411 Г,

НН,

АА,

Е,

Ж ) ;

В : = 0 ;

А : = 0 ;

АА1:

A " = A + 1 ; Б : = 0 ;

P : = 0 ;

M l : '

Б:' = Б + 1 ; ' если

Н Н [ А , Б ] ' = 0

то

на

М2;

Р : = Р + 1 ; если Б = 7

то на М2;

на M l ;

М2:

Н : = 0 ;

Б : = 0 ;

АA3:

Б : = Б + 1 ; И : = Н Н [ А , Б ] ;

если

( Р — Б ) < 0

то

на

МЗ;

НАП:

С : = 0 ;

С С : = 0 ;

Л : = 0 ;

К : = 0 j

К : = К + 1 ;

А1 : = К + 1 ;

если

А А [ А 1 , И ] = 0 _ г о

на

М4;

С: = Е[И] Х Ж [ К , И ] ;

Л: = Л + 1 ;

на_ МЕ2;

М4:

если

И = 1

то на

КФН;

С: = Е [ И ] Х Ж [ К , И ] ;

Л : = Л + 1 ;

И : = А А [ К , И ] 5

•на М Е 1 ;

М Е 1 :

К : = 0 ; К: = К + 1 ; А 1 : = , К + 1 ;

если

АА[А1, И ] = 0 _ т о

на

М5; на МЕЗ;

М 5 :

если

И = 1

то

на

МЕ6;

С: = С х Ж [ К , И ] ;

Л : = Л + 1 ; И : = А А [ К , И ] ;

на МЕ1;

М Е З :

К : = 0 ; К : = К + 1 ;

если

М [ И ] = 0

то

на

МЕ5;

Мб:

если

А А [ К , И ] = М [ И ]

то

на

МЕ5;

К : = К + 1 ;

на

Мб;

М Е 5 :

С : = С Х Ж [ К , И ] ; Л : = Л + 1;

МЕ2:

М [ И ] : = А А [ К , И ] ;

Д [ И ] : = Л ?

Г [ И ] : = С ;

И : = М [ И ] ;

на

МЕ1;

МЕ6:

И : = И + 1 ;

если

М [ И ] = 0

то на

М7;

на

МЕ7;

М 7 :

если

И = 2 5 _то

на

МЕ9;

на_

МЕ6;

МЕ7:

если

Л > = СС _то _н_а

М8; _на

МЕ8;

М 8 :

С С : = Л }

Ф : = С ;

МЕ8:

К : = 0 ;

М9:

К : = К + 1 ;

если

АА|К, И] = М [ И ]

то _н_а

М10;

на

М9;

М10:

А 1 : = К + 1 ; если

АА[А1,

И] = 0

то_на_М11;

М [ И ] : =АА[А1,

И ] ;

Л : = Д [ И ] ;

С: = Г [ И ] ;

И : = М [ И ] ;

яа_ МЕ1;

М П :

М [ И ] : = 0 ;

М12:

если

И = НН[А, Б]

то

на

МЕ9;

И : = И + 1 ; если

М [ И ] = 0 _го

на М13;

на МЕ8;

М13:

Если

И = 2 5 _то

на

МЕ9;

на_

М12;

МЕ9:

А 2 : = И ; библ

('ВЫВОДГ,

'111', А2,

Ф,

СС);

Н : = Ф + Н ; _ н а

АA3;

МЗ:

если

А = 8

_то

на

М14;

В : = Н + В ;

библ

('ВЫВОДГ,

'Г,

Н ) ;

_на

АА1;

М14:

В : = В + Н ;

библ

('ВЫВОДГ,

Ч Г ,

В,

Н ) ;

на

КФН;

К Ф Н :

кон;

Алгоритм синтеза можно разделить на две

составные

части:

1) сложение матриц с выделением равных и неравных

частей;

2) корректировка итоговой матрицы с целью

получения мат­

рицы составного алгоритма.

Рассмотрим каждую из частей более детально.

именующих строк объединяемых матриц А и В. Если ацФЬх\,

то

значение индекса х увеличивается на единицу, и так до тех

пор,

Появление х=п

означает,

что элемент

an не имеет

равных в

именующей строке

матрицы

В.

Из

таких

элементов

создаются

дополнительные

массивы Ьщ

и

ЬЩ, в которых указываются зна­

чения элемента

an и все его

связи. После этого индекс i увеличи­

вается на единицу, если элемент an не был последним.

Если элемент an

был последним,

т. е. i = n, то производится

После

завершения

формирования дополнительных

массивов

элементы

из

них переносятся в матрицу С. Элемент из

массива

L R j ставится

в массив

С на место, имеющее координаты

z, 1, пос­