AOP_Tom1 (1021736), страница 161
Текст из файла (страница 161)
Приведенная ниже программа реализует алгоритм 2.3.1С с регистрами гП ы Р, г12 ив а Ц, г!3 = Н и соответствующим образом изменяет условия инициализации и прекращения выполнения. 064 БТЗ БГ(0: 2) Сохранить содержимое регистров г13, г12. Ои ИЧ П:Е ~,~щд~ рр, Обб ЕМТ2 8Г Начать с создания узла МООЕ(О) с 067 1МР 1Г М.1МК(О) = Л.
068 8Н СОИ 0 Нулевая константа инициализации. 069 4Н 101 0,1(ШИК) Установить Р е- Ы1МК(Р) = Рю 070 1Н 103 АЧА1!. Н ~ АЧА11. 071 132 ОЧЕНЬ.ОЧ 078 10А О,З(ШИК) 078 БТА АЧА11 076 БТЗ 0,2(111ИК) ШМК(Ц) з- Н. 076 ЕММА 0,2 076 БТА О,З(81.1МКТ) Н11МК(Н) +- Ц, НТАИН) е — 1.
077 1МСА 88 гА +- !.ОС(исходный узел) — Ц, 078 ЕИТ2 0,3 Установить Ц +- Н = Цю 079 112 СЗ Перейти к шагу СЗ впервые. 080 С2 ЕОА 0,1 2. Есть ли зел сп ава? 081 1АМ СЗ Если НТАО(Р) = 1, выполнить переход. 088 ЕОЗ АЧА11 Н ~ АЧА11.. 088 132 ОЧЕНГЕОЧ 084 10А 0,3(111МК) 086 БТА АГАП. 086 ЕОА 0,2(Н11МКТ) 087 БТА 0,3(НЕТИКТ) 088 БТЗ 0,2(Н11МКТ) 086 СЗ ЕОА 1,1 090 БТА 1,2 Поле 1МГО скопировано, 091 1ЦА 0,1(ТУРЕ) ОГЕ БТА 0,2(ТУРЕ) 008 С4 ЕОА 0,1(111ИК) 094 ЗАМЕ 48 005 БТЕ 0,2(ШИК) 1.1.1МК(Ц) +- Л. ~,Е~~ ) И,акккк,1 -~ВЧ(Е. 097 Е01 О, 1(Ы.1МК) Р +- 31.1МК(Р) .
098 12Р СБ Если НТАС(Ц) равно 1, то совершить переход. 099 ЕИИ2 0,2 Ц +- — Ц. 100 СБ 12МЕ С2 С . П ове ка заве шения. 101 Ы1 66(ЕЫИК) гП +- адрес первого созданного узла. 102 6Н ЕМТЗ е Восстановить индексные регистры. 108 ТН ЕИТ2 * ! 14. Пусть а — количество скопированных неконцевых узлов (т. е. узлов с операторами). Попыток выполнения разных строк из предыдущей программы будет столько: 064-067, 1; 069,а; 070-079, а + 1; 080-081, и — 1; 082-088, и — 1 — а; 089-094, и; 096, и — а; 096-098, и + 1; 099 †1, и — а; 101-103, 1.
Общее время равняется (Зби + 22)и, при этом около 20% времени уходит на поиск свободных узлов, около 40% †обход и около 40% †копирование данных из полей 1МРО и 11МК, 16. Читателю предлагается в качестве упражнения самостоятельно изучить этот код. 218 ЭХУ ЕОА 1,6 282 1Н ЕМТХ е 219 1АЕ 1Р 288 ЭИР ТНЕЕ2 220 )ИР СОРУР2 284 БТ1 1Р(0:2) 221 ЕМТА БАБАЯН 285 1НР СОРУР1 222 ЕИТХ 0,6 286 ЕИТА 0,1 228 1НР ТНЕЕ2 287 ЕИТ1 0,6 224 ЕМТБ 0,1 288 1МР %П.Т 225 1Н ЕОА 1,6 289 ЕМТХ 0,1 22б )АЕ 303 240 1Н ЕИТ1 е 227 )НР СОРУР2 241 ЕМТА 31АЯН 228 БТ1 1Р(О:2) 242 1МР ТНЕЕЯ 229 ЕИТА СОМ2 248 ЕМТБ 0,1 280 )ИР ТНЕЕО йД 1НР БОМ 1 281 ЕМТА ОРАННОМ 16. Читателю предлагается в качестве упражнения самостоятельно изучить этот код.
245 РМН ЕОА 1, б 268 )МР ТНЕЕО 281 ЕМТА КОС 245 )АЕ 4Г 254 1Н ЕМТХ к ЯВЯ 1НР ТНЕЕ1 247 )МР СОРУР1 265 ЕМТА И1ИОБ 288 ЕМТА 0,1 218 ЯТ1 Н(0:2) Ябб )НР ТНЕЕ2 284 ЕМТ1 0,6 249 ЕОА 0 3(ТУРЕ) 267 БН СОХ Н(0'2) 285 1НР МШ.Т 250 ЗАМЕ 2Р 258 ЕМТА БРАННОМ 286 ЯТ1 1Р(0:2) 251 ЬРА 1,3 258 1ИР ТНЕЕ2 287 1МР СОРХР1 252 ОЕСА 2 270 БТ1 Н(0:2) 288 БТ1 2Р(0:2) 258 1АЕ ЗР 271 ЗН 1МР СОРУР2 289 ЗМР СОРУР2 254 ХИСА 1 272 ЕМТА 0,1 290 2Н ЕИТХ е 255 БТА СОМО+1 278 Н ЕИТ1 е Я91 ЕМТА ОРАРНОМ 25б ЕМТА СОМО 274 1НР НОЕТ 282 )ИР ТНЕЕ2 257 )НР ТНЕЕО Я75 ЕМТА О,б ЯВВ 1Н ЕМТХ е 258 БТЕ СОМО+1 275 ЗИР НЛ.Т 294 ЕМТА Т1НЕБ 259 1НР 6Г 277 ЕМТб 0,1 295 ЗИР ТНЕЕ2 ЯбО 2Н 1ИР СОРУР2 Я78 4Н ЕОА 1,Б 296 ЕМТБ 0,1 261 ЯТ1 1Р(0:2) 279 )АЕ АОО 297 )НР АОО Я Я62 ЕМТА СОМ1 ЯВО 1ИР СОРУР1 17.
Ссылки на более ранние работы по этой теме можно найти в обзоре Ю. ЯапппеС, САСМ 9 (1966), 555-569. 18. Сначала следует таким образом установить ШИК[]] +- В[1ИК[]] +- ] для всех 1] чтобы каждый узел находился в пиклическом списке длиной 1. Тогда для ] = и, и — 1, ..., 1 (в таком порядке), если РАВЕИТ [Я = О, установить т +- ), в противном случае вставить циклический список, начиная с 1, в циклический список, начиная с РАВЕИТ []], в следующем порядке: )с с- РАВЕИТ[]], ! +- В11ИК[/с], с с- ШИК[]], ШИК[1] с- )с, В11ИК[)с] с — !] ШИК [!] +- с, В11ИК Н] +- !. Этот алгоритм корректен, так как (а) каждый некорневой узел всегда располагается перед своим родителем или последователем своего родителя; (Ь) узлы каждого семейства располагаются в списке родителя в порядке их следования; (с) прямой порядок является единственным порядком, который удовлетворяет условиям (а) и (Ь).
20. Если и является предком узла и, то по индукции автоматически следует, что узел и предшествует узлу и в прямом порядке обхода и следует за узлолс и в обратном порядке. И наоборот, если узел и предшествует узлу и в прямом порядке и следует за узлом и в обратном порядке, то докажем, что узел и является предком узла и. Это утверждение очевидно, если узел и является корнем первого дерева. Если и не является корнем первого дерева, то и узел и не будет корневым, так как и следует за узлом и в обратном порядке; далее доказательство выполняется по индукпии. Аналогично, если и не принадлежит первому дереву, то и узел и не принадлежит ему, так как узел и предшествует узлу и в прямом порядке.
(Результат этого упражнения также следует из результата упр. 3. Значит, можно получить быстрый способ проверки прародства, зная расположение каждого узла в прямом и обратном порядках обхода.) 21. Если узел ИООЕ(Р) является бинарным оператором„то указателями двух его операндов будут Р1 = ШИК(Р) и Р2 = Ж.ХИК(Р1) = эр. В алгоритме [) используется тот факт, что Р2с = Р, так что ВЬ1ИК(Р1) можно заменить указателем Ц1, т. е. указателем на производную узла ИООЕ(Р1), а затем вновь переустановить В51ИК(Р1) на шаге [)3. При обработке тернарных операций получим, что Р1 = 151ИК(Р), Р2 = ВЬ1ИК(Р1), РЗ = М.1ИК(Р2) = сР, а потому обобщить обработку бинарных операций довольно трудно.
После вычисления производной Ц1 можно временно установить В11ИК(Р1) +- Ц1, а затем после вычисления следующей производной Ц2 установить В11ИК(Ц2) с — ц1 и В51ИК(Р2) с — Ц2 и переустановить В1.1ИК(Р1) с — Р2. Но такое решение вряд ли можно считать элегантным, а с возрастанием степени операторов оно становится все более неуклюжим. Следовательно, способ на основе временного изменения ВНИК(Р1) в алгоритме Р может рассматриваться всего лишь как раовка, но никак не как общий меспод решения подобных задач. Новее эстетичный способ управления процессом дифференцирования основан на алгоритлсе 2.З.ЗР (см.
упр. 2.3.3 — 3), потому что он сформулирован в более общем виде так, что его можно применять для операторов с более высокими степенями и не прибегать к каким-либо трюкам. 22. Из данного определения сразу же следует,что такое отношение является транзитивным, т. е. если Т С Т' и Т С Т~~, то Т С Т". (На самом деле легко видеть, что это отношение является частичным упорядочением.) Если допустить, что 1 может отобразить каждый узел на себя, то ясно, что !(Т) С Т и т(Т) С Т.
Следовательно, если Т С ((Т"! или Т С т(Т'), то обязательно Т С Т'. Предположим, что ]с и ], являются функциями, для которых выполняются отношения !(Т) С !(Т') и т(Т) С т(Т ) соответственно. Пусть 1(и) = ]с(и), если и принадлежит ((Т), 1(и) = корень дерева Т', если и является корнем дерева Т, а в противном случае 1(и) = 1 (и), Тогда для такой функции ! выполняется отношение Т С Т . Например, пусть т'(Т) обозначает т(Т) )корень дерева Т. Тогда получим следующее: прямой порядок дерева Т = корень дерева Т прялсой порядок дерева (!(Т)) прямой порядок дерева (т'(Т)), а прямой порядок дерева Т' = 1(корень дерева Т) прямой порядок дерева (1(Т')) прямой порядок дерева (г'(Т')). Обратное утверждение не верно: рассмотрите подлеревья с корнями Ь и Ь' на рис. 25.
РАЗДЕЛ 2.3.3 1. Да, их можно восстановить точно так, как (3) можно вывести из (4), но заменяя ЬТАО и НТАО, а также 511ИК и НЬТИК и используя очередь вместо стека. 2. В алгоритм Р внесем следующие изменения. На шаге Р1 фразу "Р пусть указывает на первый узел леса в обратном порядке" заменим фразой "Р пусть указывает на последний узел леса в прямом порядке". На шаге Р2 в двух местах заменим фрагмент 1(га),, /(г~)" фрагментом "1(х~),, 1(гэ)". На шаге Р4 выполним такие действия: "Если Р указывает на первый узел в прямом порядке, то прекратить выполнение алгоритма. (Тогда стек в направлении сверху вниз будет содержать элементы )(корень(Т~)), 1(корень(Т )), где Т,,..., Т вЂ” деревья данного леса по направлению слева направо.) В противном случае установить Р указывающим на его предшественника в прямом порядке (Р е — Р— с для данного представления) и вернуться к шагу Р2".
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
