Файл: Алферова, З. В. Математическое обеспечение экономических расчетов с использованием теории графов.pdf

нач цел мае Т[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, пос­