1626435694-d107b4090667f8488e7fa1ea1b3d0faa (844295), страница 33
Текст из файла (страница 33)
БАнОническОе РАспРеделение НАмяти 155 жества А. После того как мы обнаружим, что в Т попадает некоторый оператору, принадлежащий А, мы должны найти аргумент этого оператора, которому сопоставлена величина Б[р+11, и объединить текущую компоненту связности этого аргумента с компонентой связности 1-го результата. Вспомним ($2.2), что в общем случае таких аргументов у оператора может быть несколько, хотя в исходной схеме такие случаи следует считать весьма редкими.
Поскольку величина Б[р + -1- 11 и оператор у, воспринимающий В[11, нам даны, поиск аргументов, т. е. таких й, чтобы У[я[ = у, а Ыя 1 = Б [р + 11, может быть осуществлен просмотром аргументной части вектора Б. Если бы аргументам каждого оператора сопоставлялись всегда разные величины, то тогда для аргументного множества А можно было бы иметь второй вектор цел массив а[1: п[, в котором а[11 было бы равно аргументу й оператора 1, для которого Ь[1«1 = Б!р + 11.
Такой вектор в«он<- но построить при подготовке. Это тем более соблаапительно, что такая ситуация будет встречаться наиболее часто. 'Тем не менее мы не можем игнорировать общий случай, когда оператор имеет сколько угодно (вплоть до р) аргументов с одной и гой же величиной.
Мы, однако, имеем возможность путем некоторых ухищрений объединить выгодность формирования списка аргументов а с общностью алгоритма. Для этого мы будем в аргументном множестве А различать операторы с однократным восприятием величины Х [р +. 11 и с многократным. Это будет делаться так, что при отнесении оператора к аргументному множеству единица в нужную компоненту вектора А будет не ставиться, а добавляться. Это произойдет столько раз, сколько раз величина Б[р + 11 оказалась сопоставленной аргументам этого оператора. Если оператор воспринимает велйчину многократно, в список аргументов адля определенности будет помещаться первый по порядку аргупент. Остальные же аргументы будут искаться в векторе Ь.
Сигналом для этого будет признак принадлежности оператора множеству А, равный не единице, а большему числу. Итак (12) ТРАНЗАМ 1-ГО РЕЗУПБТАТА: (цез массивы Я, Т, Л, А, а[1: п[; ПОДГОТОВКА; ДВИЖЕНИЕ ВДОДЬ ДУГ /22! ) лрим ПОДГОТОВКА ~п, р, д, [г, Ь, 1, Я, Т, Л, А, ад Осмыслим способы задания множеств Я, Т, Л, А, а.
Множество Я содержит единственный оператор У[р + 11. Множество Т пусто. Множества Л и А — это своего рода «линии уровня», т. е. мно«кества тех оператороз, которые в р«определении полюсов сопоставлены полюсам, имеющим своей величиной Гл. «. Ркализлция Ь[р + 11. Мола«о вообразить способ их получения. Двигаясь вдоль вектора Ь, мы будем узнавать среди его компонент нужное значение Ь1р + 1] и по номеру компоненты | извлекать нужный оператор У[/], помечая единицей в векторе В компоненту с номером У[|]и добавляя единицу к аналогичной компоненте вектора А. Остальные компоненты векторов А и В должны быть нулевыми. Таким образом, прежде чем проиаводить содержательное формирование множеств 3, В, А и а, нам их все (а также, естественно, и Т) надо «обнулить».
Итак (13) ПОДГОТОВКА: (ИНИЦИАЛИЗАЦИЯ; ЗАПОЛНЕНИЕ /15/) (14) ИНИЦИАЛИЗАЦИЯ: (цел |; для /: = 1 гааг 1 до п цикл Т[/'] « = 3[/1: = В[|]: = А [|]: = а[/): = О) (15) ЗАПОЛНЕНИЕ /13/: (ЯУ[1+ р1]:=1; ЗАПОЛНЕНИЕ ОСТАЛЬНОГО) (16) ЗАПОЛНЕНИЕ ОСТАЛЬНОГО: (ЗАПОЛНЕНИЕ В; ЗАПОЛНЕНИЕ А /19/) прим ЗАПОЛНЕНИЕ В /и, р, а, У, Ь, /, В/. В соответствии со сказанным в (13) мы будем двигаться вдоль вектора Ь (более точно, вдоль той его части, которая относится к результатам: |.[р + 1: р + а] и, пользуясь вектором У, находить нужный оператор. Итак (17) ЗАПОЛНЕНИЕ В: (цел /; для |: = 1 гааг 1 до Ч цикл ПРОВЕРКА ОЧЕРЕДНОГО РЕЗУЛЬТАТА) (18) ПРОВЕРКА ОЧЕРЕДНОГО РЕЗУЛЬТА ТА: если Ь1р + |]= Ь[р + «1 то В1У[р + |11: = 1 прим ЗАПОЛНЕНИЕ А/(16) и, р, У, Ь, «, А, а/ делаешься аналогично заполнению В с тем отличием, что мы движемся вдоль аргументной части вектора Ь, а такя«е заполняем указанным в (12) способом мноя«ество аргументных полюсов а.
Итак (19) ЗАПОЛНЕНИЕ А: (цел /; для |: = 1 «паг 1 до р цикл если Ь[|] = Ыр -[- 1] то ЗАГРУЗКА КОМПОНЕНТБ|) прим ЗАГРУЗКА КОМПОНЕНТЫ /У, А, а, |/ делается по рваному, в зависимости от того, в первый или не в первый раз обнаружен нужный аргумент. Если оператор У[|1 уже содержится во множестве А, то кратность аргумента увеличивается на единицу.
Если же оператор У]/) еще не попал в А, то тогда он не только отмечается в нем, но и соответствующий аргумент заносится в а. Итак % ь4. каноничиское РАспгкделвние памят!г 157 (20) ЗАГРУЗКА КОМПОНЕНТЬ1: если А [У[/[) = 0 то ЗАНЕСЕНИЕ В А иначе А [У[/[[: = А[У[/)1+ 1 (21) ЗАНЕСЕНИЕ В А: (а[У[/) ): = у: А ['с'[/) [: = 1) прим ДВИЖЕНИЕ ВДОЛЬ ДУГ/(12) и, С, ЬК, 1, Я, Т, Н, А1. В соответствии с правилами построения транзитивного замыкания (э 3.1) стимулом к продвижению вдоль дуг является непустота стартового множества. Условие непустоты множества, изображаемого логической шкалой некоторой длины, мы оформим в виде логической процедуры-функции, так как такие проверки у нас будут встречаться неоднократно. После построения всей программы мы определим надлежащий уровень локализации этой процедуры с тем, чтобы ее описание было бы доступно всем вызовам.
Итак (22) ДВИЖЕНИЕ ВДОЛЬ ДУГ: (цел у; /: = 0; для у: = / + 1 пока НЕПУСТО (Я, и) цикл ДВИЖЕНИЕ ХХ СОГЛАСОВАНИЕ /28/) прим НЕПУСТО /Я, и/. В рамках структурированного программирования поиск первой отличной от нуля компоненты в логической шкале требует небольших ухищрений, связанных с отсутствием меток (свойство структурированного программирования). Для этого дэнн<ение вдоль шкалы мы запрограммируем циклом, в процедуру введем локальную величину, запоминающую факт обнаружения ненулевой компоненты, а после выхода из цикла в зависимости от значения величины, будем определять результат процедуры.
Итак (23) лог проц НЕПУСТО (А, т); знач т; цел т; цел массив А[1: т[; ТЕЛО НЕПУСТО (24) ТЕЛО НЕПУСТО/А, т/: (лог р; р: = встнпа; ПРОВЕРКА» (25) ПРОВЕРКА: (ПРОСМОТР А; ПРОБА Р /2//) (26) ПРОСМОТР А: (цел /; /:= 0; для' 1: = /+ 1 пока 1( пйр цикл р:. = А [11 = О) (27) ПРОБА Р /25/: НЕПУСТО: --)р прим ДВИЖЕНИЕ ХХ СОГЛАСОВАНИЕ Ц22) и, С, ЬК, 1, Я, Т, В, А/.
Вспомним алгоритм построения областей действия в з 3.1. Разберемся более подробно с шагом индукции. По ста ртовому множеству Ямы находим Г($), которое в нашем представлении будет логической суммой (1 ~/ 1 = 0 )/ 1 = = 1 )/ 0 = 1; 0 )/ 0 = О) всех строк матрицы С с номерами, соответствующими ненулевым компонентам вектора $. Для накопления Г($) нам потребуется локальный вектор цел массив Г[1: и), которому должно быть задано начальное пустое значение. После получения Г мы прибавляем его к Гл. а РеАлизАция пополняемому множеству Т и по ходу дела проверяем, не попадает ли очередной элемент Г в аргументное множество А. При таком попадании необходимо будет проверить с помощью вектора ЬК, отнесены ли 1-й результат и соответствующий аргумент оператора из А к одной н той же текущей компоненте, сливая их в одну, если это не так.
В этом же цикле дви;кения вдоль вектора Г мы можем извлечь из него элементы следующего стартового множества: элемент из Г входит в следующее Я только в том случае, если он не входит в предыдущее Т и не вырабатывает Ь [Р + 1], т. е. Ие входит в Н. Итак (28) ДВИЖЕНИЕ И СОГЛАСОВАНИЕ: (цел массив Г[1: и]; НАХОЖДЕНИЕ ГЯ; ИСПОЛЬЗОВАНИЕ ГЯ /35/) (29) НАХОЖДЕНИЕ ГЯ /и, С, Я, Г!: (ФОРМИРОВАНИЕ ГЯ; СУММИРОВАНИЕ ГЯ /31/) (30) ФОРМИРОВАНИЕ ГЯ: (цел [; для [: = 1 шаг 1 до и цикл Г[[]: = О) (31) СУММИРОВАНИЕ ГЯ /(29) и, С, Я, Г/: (цел [; для 1: = 1 1паг 1 до и цикл ПРОВЕРКА Я/) (32) ПРОВЕРКА Я1: если Я[]] =Д 0 то ДОБАВЛЕНИЕ С/ (33) ДОБАВЛЕНИЕ С1 /и, С, Г, [/: (цел /; для /: = 1 гяаг 1 до я цикл ДОБАВЛЕНИЕ С1л) (34) ДОБАВЛЕНИЕ С/./: если С[/, /1 = 1 то Г[/']' = 1 прим ИСПОЛЬЗОВАНИЕ ГЯ/(28) и, ЬК, [, Я, Т, К, А/ — это, преягде всего, цикл поочередного использования его элементов.
Итак (35) ИСПОЛЬЗОВАНИЕ ГЯ: (цел /; для /: =- 1 шаг 1 до п цикл РАБОТА С ОЧЕРЕДНЫМ ЭЛЕМЕНТОМ) (Зо) РАБОТА С ОЧЕРЕДНЬ/М ЭЛЕМЕНТОМ: (ПЕРЕСЧЕТ СТАРТОВОГО; ДОБАВЛЕНИЕ К ПОПОЛНЯЕМОМУ !38/) прим ПЕРЕСЧЕТ СТАРТОВОГО /я, Я, Т, Н, Г, )/. Согласно $ 3.1 оператор не входит в Я, если он не входит в Г.
Если же оператор входит в Г, то исключается случай, когда он принадлежит Т или К. Итак (37) ПЕРЕСЧЕТ СТАРТОВОГО: если Г[(] = 0 то Я[/]: = 0 иначе если Т [/] -'- 0 ~/ К [/] ч~ 0 то Я [1]: = 0 иначе Я[/]: = 1 прим ДОБАВЛЕНИЕ К ПОПОЛНЯЕМОМУ /(36), п, р, У, Ь, $, Т, А, а, у/ прежде всего зависит от того, входит ли оператор / в Г. Итак $ аа КАноничзснон Распгкднлегпгн пАмяти |59 (38) ДОБАВЛЕНИЕ К ПОПОЛНЯЕМОМУ: если Г[у'! ча 0 то РАБОТА С ЭЛЕМЕНТОМ Г (39) РАБОТА С ЭЛЕМЕНТОМ Г: (Т[у]: = 1; ВОЗМОЖНОЕ СОГЛАСОВАНИЕ) прим ВОЗМОЖНОЕ СОГЛАСОВАНИЕ Уп, р, Р, Б, У, Т, А, а, 1| начинается с проверки принадлежности оператора у аргументному множеству.
Итак (40) ВОЗМОЖНОЕ СОГЛАСОВАНИЕ: если А[у] та 0 то СОГДА СОВАНИЕ дрим СОГЛАСОВАНИЕ Ур, [г, Б, У, А, а, у|. В силу сказанного в (12) СОГЛАСОВАНИЕ проводится в два приема: для первого аргумента оператора у и для возможных остальных. Первый аргумент извлекается нз множества аргументных полюсов а, а остальные, если они есть, ищутся в аргументной части множества Б. Сказанное означает, что слияние текущих компонент связности [-го результата и найденного аргумента будет выполняться в двух местах программы, в связи с чем слияние целесообразно программировать как процедуру с двумя формальными параметрами: результат г и аргумент а. Итак (41) СОГЛАСОВАНИЕ: (проц СЛИЯНИЕ (г, а); знач г, а; цел г, а; ТЕЛО СЛИЯНИЯ; ПЕРВЫЙ А РГУМЕНТ !46у; ОСТАЛЬНБ1Е АРГУМЕНТЫ /471) прим ТЕЛО СЛИЯНИЯ Ур, д, ЪК, г, аУ. Если г и а относятся к одной компоненте, т.
е. если БК 1р -[- г] = БК[а], то ЪК остается без изменений. В противном случае происходит выравнивание значений: все вхождения МАХ(БК[р + г], ЪК[а]) в вектор ЪК заменяются на М1|)У(ЪК[р + г], ЬК[а 1). Итар (42) ТЕЛО СЛИЯНИЯ: (если ЪК[р + г1 ч~ БК [а 1 то ВБ1РАВНИВАНИЕ) (43) ВБ1РАВНИВАНИЕ: (цел туп, тах; НАХОЖДЕНИЕ М|Н МАХ; ЗАМЕНА МАХ НА М1Н) (44) НАХОЖДЕНИЕ М1Н МАХ: если 1К[р + г1( БК[а! то (т[п: = ЪК[р + г1; тах: = ХЕ[а!у иначе (трп БК[а]; тах: = БК]р + г1) (45) ЗАМЕНА МАХ НА М|Н: (цел У; для й = 1 гааг 1 до р + 4 цикл если БКВ1 = тах то БК[|1: = т[п) (46) ПЕРВБ1Й АРГУМЕНТ !4[l: СЛИЯНИЕ (а[у1, |) (47) ОСТАЛЬНБ1Е АРГУМЕНТЪ| 14гу: если А]у]) т то ПРОСМОТР АРГУМЕНТОВ гл. 4.
Рвалнэлция прим ПРОСМОТР АРГУМЕНТОВ /р, г', Б, У, А, а, у/ состоит в последовательном просмотре аргументной части множества полюсов. Так как а(у] хранит первый нужный аргумент, просмотр естественно начинать с номера а]у! + 1. При обнаружении аргумента Уг, для которого Б(/г] = Ь! р+ 1], дополнительно проверяется, не относится ли он к рассматриваемому оператору у. В этом случае й вместе с у отправляется на процедуру слияния их текущих компонент связности. Итак (48) ПРОСМОТР АРГУМЕНТОВ: (цел й; для Ус: = аП] + 1 гааг 1 до р цикл если Ь(/г] = Ир+ 1]ЙУ]/г!.= у то СЛИЯНИЕ (Уг, 1)) э 4.5.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
