AOP_Tom1 (1021736), страница 97
Текст из файла (страница 97)
В противиом случае, если 1МРО(Ц) = О, установить АЧА10».= Ц и Ц +- Ц1; ииаче — установить Ц »- ТКЕЕ("+",Ц1,Ц). 01РР(53: (Операция " †".) Если 1НРО(Ц) = О, установить АЧА1Е »- Ц и Ц +- Ц1. В противном случае, если 1ИРО(Ц1) =О, установить АЧА1Е~ Ц1 и Ц»-ТКЕЕ("пей",Ц); иначе — -установить Ц» — ТКЕЕ(" — ",Ц1,Ц). 01РР(6]: (Операция 'х".) Если 1ИРО(Ц1) ф О, установить Ц1»- МК.Т(Ц1, СОРТ(Р2)). Затем, если 1НРО(Ц) ф О, установить Ц +- МО!Т(СОРУ(Р1),Ц). После э»о»о перейти к выполиепию программы 01РР(43. Здесь И05Т(О,Ч) является новой функцией, которая создает дерево для 0 х Ч и проверяет, не равны ли 0 Йли Ч единице: если 1ИРО(0) = 1 и ТУРЕ(0) = О, установить АЧА15 с= 0 и МО5Т(У,Ч) е- Ч; если 1ИРО(Ч) = 1 и ТУРЕ(7) = О, установить АЧА11.
с= Ч и МОЕТ(О,Ч) ч — 0; в противном случае установить ЖЛ.Т(О,Ч) +- ТВЕЕ("х",О,Ч). 01РР[73: (Операция "/".) Если 1ИРО(Ц1) ЭА О, установить Ц1 + — ТЛЕ("/",Ц1,СОРТ(Р2)). Затем, если 1ИРО(Ц) эб О, установить Ц +- ТНЕЕ(в/",ИШ Т(СОРУ(Р1),Ц),ТВЕЕ("Т"', СОРТ(Р2),ТНЕЕ(2))). После этого перейти к выполнению программы 01РР [53, 01РР [83: (Операция "Т".) Сьь упр. 12. В заключение настоящего раздела продемонстрируем применение этих операций в компьютерной программе на основе только внутреннего языка компьютера И1Х. Программа 1) (Дифференцирование).
Приведенная ниже программа на языке М1ХАЕ реализует алгоритм П с такими значениями регистров г?1 = Р, г?3 х— а Р2, г?4 = Р1, г?5 = Ц, г?6 = Ц1. Для удобства порядок вычислений немного изменен. 001 е ДИФФЕРЕНЦИРОВАНИЕ В ПРАВОПРОШИТОМ ДЕРЕВЕ 002 ШМК ЕЦО 4:5 Определение полей, см. (10). ООЯ МЕТИМ ЕЦО 1:2 001 Н51ИКТ ЕЦО О."2 ООЯ ТЧРЕ ЕЦО 3:3 ООВ уп~ьВляаья и ОГРьниь Р~~.
Рх 007 01 ЯТЯ 9Р Эта программа рассматривается как подпрограмма. 008 504 У(551ИК) Р1 +- ььТМК(Т),приготовиться к поиску Та 009 1Н ЕИТ2 0,4 Р < — Р1. 010 2Н 504 0,2(ьь1ИК) Р1 +- ШМК(Р) 011 1402 1В Если Р1 Р Л, повторвть. 012 02 501 0,2(ТУРЕ) ?)2. н е ен и ование. 01 Я ЛМР ее1„1 Переход к 01РР[ТТРЕ(Р)]. 018 ЯМР СОИЯТАИТ Переход к элементу таблицы 01РР[03. 015 ЯМР ЧАН1АВЕЕ 01РР[П. 018 ЯМР ЕИ 01РР [2] . 017 ЯМР ИЕО 01ГГ[33.
018 ЯМР АОО 0199[4] ° 019 ЯМР ЯОВ 01РР [53. 020 ЗМР М7Л 01РР [63 . 021 ЯИР 01Ч 01РР [73 022 ЭМР РМВ 01РР [83. 02Я 03 ЯТЗ 0,4(В51ИК) ?)3. Восстаноатенне связи. 21.1ИК(Р1) +- Р2. 021 04 ЕИТЗ 0,2 В4. П> внжение к Ра Р2+- Р. 025 502 0,2(511ИКТ) Р +- МьТМКТ(Р). 028 12И 1Р Переход, если КТАО(Р) = 1; 027 ЯТ5 0,3(Ы.1ИК) в противном случае установить Кь1ИК(Р2) < — О. 028 ЯИР 2В Обратите внимание, что узел ИООЕ(ре) — концевой. 029 1Н ЕИИ2 0,2 Функция ТЕЕЕ(гА.гХ,г11) .
Ы.1ИК(гХ) +- г11, АТАС(гХ) +- О Установить 1Л.1ИК дли узла следующего за корнем, г11 ~ АЧАТ(. 050 2Н 056 054 055 056 057 056 101 АЧА11. 512 ОЧЕЕРЕОЫ ЕОХ 0,1(111ИК) БТХ АЧА11. БТА а+1(0:2) МОЧЕ ь(2) ОЕС1 2 Копировать корень в новый узел. Переустановить г11, чтобы он указывал на новый корень. Выход из функции ТЕЕЕ, г11 указывает на новое дерево.
СОРТ(Р1), особый вход в СОРТ. 050 9Н 060 СОРУР1 061 060 СОРУР2 065 СОРУ ЕИТ1 0,4 ЛЯЗ СОРУ ЕИТ1 0,3 БТЮ 9Р СОРУ(Р2), особый вход в СОРУ. Функция СОРТ(гП). (См. упр. 13 ) Выход из СОРТ, гП указывает на новое дерево. Узел, представляющий "0". ЮМР 104 9Н 105 СОМО 106 107 СОИ 1 СОИ 0 СОН 0 СОИ 0 Узел, представляющий "1' . 050 Об ЕИТ1 -У,2 061 104 Ь,2(ЕЕ1ИК) ОУЕ 1.06 0,4(Н11ИК) 058 51НЕ 02 054 ЯТЗ ОУ(Е11ИК) 065 ЕИИА ОУ 086 БТА 0,5(НЫТИКУ) Е(.1ИК(О) +- ОУ, АТАС(О) +- 1.
057 9Н ЗМР Выход из программы дифференцирования. е В следующей части программы содержатся основные подпрограммы ТНЕЕ и СОРУ. Первая имеет три входа: ТВЕЕО, ТВЕЕ1 и ТНЕЕ2, в соответствии с количеством под- деревьев создаваемого дерева. Независимо от того'., какой вход в подпрограмму используется, регистр гА будет содержать особую константу, которая указывает тнп узла-корня конструируемого дерева.
Эти особые константы представлены в строках 105-124. 056 а ОСНОВНЫЕ ПОДПРОГРАММЫ КОНСТРУИРОВАНИЯ ДЕРЕВА 050 ТНЕЕО БТЛ 9Р Функция ТАЕЕ(гА) . 040 ЛМР 2Р 041 ТНЕЕ1 БТ1 ЗР(0:2) Функция ТЕЕЕ(гА,гП). 040 ЗБЛ 1Р 045 ТНЕЕ2 БТХ ЗР(0:2) 044 ЗН БТ1 а(НПИКТ) 045 1Н ЯТЗ 9Р 046 ЕОХИ АЧА11.
047 ЗХХ ОЧЕНР10Ы 046 БТХ 0,1(Е11ИКТ) И.1ИК(гП) +- АЧА11, АТАС(г11) +- 1. 040 ЮХ ЗВ(0: 2) 050 ЯТА а+1(0.'2) 051 ЯТХ а(111ИК) Узел, представляющий "!и Узел, представляющий "пеЕ" Узел, представляющий "- Узел, представляющий "/ Оставшаяся часть программы соответствует программам дифференцирования 01РР [0), 01РР [Ц,...; зти программы задуманы так, что после обработки бинарного оператора они возвращают управление шагу [)3, а в противном случае — шагу Р4. 195 е ЛРОГРАММЫ ДИФФЕРЕНЦИРОВАНИЯ О +- адрес нового дерева. Возврат к управляющей программе г1 1 а- ТИЕЕ ( "/", О, г)1) .
О е- г11, возврат к управляющей программе г11 а — ТЕЕЕ("пой", О) . О +- г11, возврат к управляющей програгаме Возврат к управляющей программе, бинарный оператор. 19В !09 СОК2 Цо ЦТ 100 ПЕ 1!8 КЕООР 1Ц Цв Р1ОЯ 115 П7 М1КОЯ цв 119 ТТМЕЯ 199 191 ВПАЯН 199 198 ОРАННОН Щ 195 УАНТАВЕЕ 197 198 199 189 СОКЯТАМТ 181 189 1Н 188 184 2Н )85 1М 185 187 )88 189 ЦО Ц1 Цв КЕО Цв 1Ц Ц5 Цб Ц7 ЦВ АОО Ц9 150 ЗН 15! 159 158 154 1Н СОК СОК 0 Узел, представляющий "2" СОК 2 СОИ 2(ТУРЕ) АЕР 1К СОИ З(ТУРЕ) АЕР КЕС СОК 4(ТУРЕ) Узел, представляющий "+" А1Р + СОК 5(ТУРЕ) АЕР СОК 6(ТУРЕ) Узел, представляющий "х" А|Р СОК 7(ТУРЕ) А|Р / СОК 8(ТУРЕ) Узел, представляющий "Т". АЕР ! ЕОХ 1,2 ЕКТА СОК1 СНРХ 2Р Верно ли, что 1ИРО(Р) = "1"7 .)Е а+2 Если верно, вызвать функцию ТЕЕЕ(1).
ЕКТА СОМО Вызвать функцию ТИНЕ(0) . ЗМР ТЕЕЕО ЕИТ5 0,1 ЗМР 04 АЕР Х 10А 1,5 ЗАХ 04 Возврат к управляющей программе, ЗМР СОРТР1 если 1ИРОСФ) = 0; в противном случае ЕНТХ 0,5 установить г11 +- СОРТ(Р!). ЕМТА ВПАЯН ЗНР ТВЕЕ2 ЗМР 18 10А 1,5 ЗАХ 04 Если 1ИРО(О) = О, возврат. ЕКТА КЕООР ЕКТ1 0,5 ЗМР ТНЕЕ1 ЗМР 1В 1.0А 1,6 ЗАКЗ 1Р Переход, если не выполняется 1ИРО(01) = О.
ЕОА АУА10 АЧА11 ~ 01. ЯТА 0,6(1.11КК) ЯТ6 АУА1Е ЭМР 03 10А 1,5 ЛАНЕ 1Р ЮА АТАП. БТА 0,5(1.11МК) гП +- МШ.Т(СОРТ (Р1) А) Ц г- гП 192 198 191 195 196 197 198 199 200 201 202 208 201 205 Н1Л.Т 1Н 1Н ЫА 0,2(ТТРЕ) ЛАЗ 2Р ЫА 1,1 РЕСА 1 ЛАНЕ 1Р ЬОА 0,1(ТТРЕ) ЛАМЕ 1Р 155 156 157 158 159 160 161 162 168 16( 165 166 167 168 169 170 171 172 178 171 175 176 177 178 179 180 181 182 188 Щ 185 186 187 188 189 190 191 2Н 1Н 4Н БОВ 1Н НШ. 1Н БТБ 'АТАП ЕМТБ О,б ЛНР ОЗ ЕМТА РЫБ ЕМТХ О,б ЕМТ1 0,5 ЛНР ТВЕЕ2 ЕМТБ 0,1 ЛМР ОЗ ЫА 1,5 ЛАЗ 2В ЫА 1,8 ЛАНЕ 1Р ЕМТА НЕСОР ЕМТ1 0,5 ЛИР ТЕЕЕ1 ЕМТБ 0,1 ЛНР ЗВ ЕМТА М1МУБ ЛМР 4В 1ОА 1,8 ЛАЗ 1Р ЛМР СОРТ2 ЕМТА О,б ЛНР НЖТ ЕНТО 0,1 Ы)А 1,5 ЛАЗ АОО ЛНР СОРТР1 ЕМТА 0,1 ЕМТ1 О,б ЛМР НОЬТ ЕМТБ 0,1 ЛМР АОР БТЛ 9Р БТА 1Р(0:2) БТ2 ОР(0:2) ЕНТ2 а ЖА 1,2 ВЕСА 1 ЛАМЕ 1Р Переход, если не выполняется 1ИРО(Ц) = 0 АТА11 ~ Ц Цэ-01 Возврат к управляющей программе Подготовиться к вызову ТИЕЕ("+" А1.0) Ц +- ТЕЕЕ( "к",Ц1 А) Возврат к управляющей программе Переход, если 1ИРООЦ) = О.
Переход, если не выполняется 1ИРО(Ц1) = 0 Ц +- ТЕЕЕ( "веЕ" А) АТАТЕ ~ Ц1 и возврат. Подготовиться к вызову ТИЕЕ(" —" А1 А) Переход, если 1ИРО(01) = О, в противном случае гП г — СОРТ(Р2) гП <- ВП.Т(Ц1,СОРТ(Р2)). Ц1 г-гП Переход, если 1ИРО(Ц) = О, в противном случае гП +- СОРТ(Р1). Подпрограмма И!Л.Т(гА, гП) . Пусть гА из О, гП ы Т Сохранить г12 г(г +- О Проверить, верно ли,что ХИРО(О) = 1, и верно ли, что ТТРЕ(О) = 0 Если не верно, проверить, верно ли 1ИРО(Т) = 1 и верно ли, что ПРИ(Т) = О. Если верно, выполнить обмен Н ФЛ Ч. Аут. ~ и.
В результате цалучнм У. В результате получим ТАБЕ("х",Ч,У). Восстановить г12. Выход из НШ.Т с результатом в г!1. $ Две другие программы 01Ч и РИН выглядят аналогично, н читателю предлагается самостоятельно создать их в качестве упражнения (см. упр. 15 и 1б). УПРАЖНЕНИЯ 1. [20] В этом разделе приводилось формальное определение бинарного дерева В(Г), соответствующего лесу К Дайте формальное определение с обратным смыслом, т.
е. опре- делите лес Р(В), который соответствует бинарному дереву В, 2. [20) Обозначение дерева в десятичной системе обозначений Дьюи дано в разделе 2.3, а обозначение бинарных деревьев — в упр. 2.3.1 — 5. Таким образом, узел лУ' в (1) представлен в виде "2.2.1", а в эквивалентном бинарном дереве (3) — в виде "11010". Если это возмоясно, предложите правило, которое непосредственно выражает естественное соответствие между деревьями и бинарными деревьями на основе десятичной системы обозначений Дьюи. 3.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
