Д. Кнут - Искусство программирования том 1 (1119450), страница 95
Текст из файла (страница 95)
упр. 12. В заключение настоящего раздела продемонстрируем применение этих операций в компьютерной программе на основе только внутреннего языка компьютера И1Х. Программа ]) [1(пфференцирование). Приведенная ниже программа на языке И1ХА1 реализует алгоритм [) с такими значениями регистров гП = Р, г13 = Р2, г14 = Р1, г[б = Ц, г16 = Ц1. Для удобства порядок вычислений немного изменен. 001 в ДИФФЕРЕНЦИРОВАНИЕ В ПРАВОПРОШИТОИ ДЕРЕВЕ 002 1НМК ЕЦО 4:б Определение полей, см.
(10), 005 ВНИК ЕЦО 1: 2 005 ВНИКТ ЕЦП О:2 005 ТТРЕ ЕЦП 3: 3 ООб упРЙВлввАя пРОГРьимь ~в. в» 007 01 БТЛ 9Р Эта программа рассматривается как подпрограмма. 005 104 Т([.НМК) Р1 +- ЬНМК(Т),приготовиться к поиску Уэ. 005 1Н ЕМТ2 0,4 Р +- Р1. 010 2Н 1.04 0,2(1.ПИК) Р1+- 11.|ИК(Р). 011 54МЗ 1В Если Р1 ЭЕ Ав повторить. 012 02 101 0,2(ТУРЕ) В2. и е еи и оввиие. 015 ]ИР в+1,1 Переход к ОТКР[ТУРЕ(Р)]. ОЦ ЛИР СОМБТАМТ Переход к элементу таблицы 01РР[0]. 015 5МР ЧАВ1АВ1Е 01РР [1] .
01б ЗМР 1М 01РР [2] . 017 ЛМР МЕО 01РР [3] . О!5 5ИР А00 0122[4]. 015 5МР БПВ 01РР [5]. 020 5МР ИЛ. 01РР [б] . 021 ЗИР 01Ч 01РР [7]. 022 )МР РИВ 0122[8]. 025 03 БТЗ 0,4(В11МК) 1)З. Восстановление связи. ВЫМК(Р1) <- Р2. 025 04 ЕИТЗ 0,2 [)4. П вижевие к Ра Р2 < — Р. 025 1.02 0,2(В11МКТ) Р ВЫМКТ(Р).
02б 52М 1Р Переход, если ВТАС(Р) = 1: 027 БТБ 0,3(В[.1МК) в противном случае установить ЯНИК(Р2) с — Ц. 025 ЗИР 2В Обратите внимание, что узел МОВЕ(рэ) — концевой. 025 1Н ЕМИ2 0,2 Функция ТЕЕЕ (гА,гХ, г11) . Е1.1МК(гХ) +- гП, ЕТАС(гХ) +- 0 Установить ШМК для узла следующего за корнем. гП ~ АЧА11. 052 2Н 058 054 055 056 057 056 101 АЧАП. 312 ОЧЕВРЕОЫ ЫХ 0.1(151МК) БТХ АЧАП. БТА эе1(0:2) МОЧЕ а(2) ОЕС1 2 Копировать корень в новый узел. Переустановить гП,чтобы он указывал на новый корень. Выход из функции ТЕЕЕ, гП указывает на новое дерево.
СОРУ(Р1), особый вход в СОРУ. 059 9Н ЛМР 060 СОРУР1 061 062 СОРУР2 068 СОРУ ЕМТ1 0,4 551 СОРУ ЕМТ1 0,3 БТ5 9Р СОРУ(Р2), особый вход в СОРТ. Функция СОРУ(гП). (См. упр. 13 ) Выход из СОРУ, гП указывает на новое дерево. Узел, представляющий "0". 104 9Н ЗМР 105 СОМО 106 107 СОМ1 СОМ 0 СОН 0 СОМ 0 Узел, представляющий "1". 080 05 ЕМТ1 -У,2 081 1.04 0,2(111МК) 082 ЕОб 0,4(ВЕ1МК) 088 51МЕ Й2 084 БТ5 ОУ(151МК) 095 ЕММА ОУ 086 БТА 0,5(В11МКТ) И 1МК(О) г- ОУ, АТАС(О) +- 1. 087 9Н ЗМР ь Выход из программы дифференцирования. $ В следующей части программы содержатся основные подпрограммы ТВЕЕ и СОРУ. Первая имеет три входа: ТВЕЕО, ТВЕЕ1 и ТВЕЕ2, в соответствии с количеством под- деревьев создаваемого дерева.
Независимо от того', какой вход в подпрограмму используется, регистр гА будет содержать особую константу, которая указывает тип узла-корня конструируемого дерева. Эти особые константы представлены в строках 105-124. 086 ь ОСНОВНЫЕ ПОДПРОГРАММЫ КОНСТРУИРОВАНИЯ ДЕРЕВА 089 ТВЕЕО БТЛ 9Р Функция ТЕЕЕ(гА) .
040 )МР 2Р 041 ТКЕЕ1 БТ1 ЗР(0:2) Функция ТЕЕЕ(гА.гП). 042 155 1Р 048 ТВЕЕ2 БТХ ЗР(0:2) 044 ЗН БТ1 е(ВЕ1МКТ) 045 1Н БТ5 9Р 046 ЕОХМ АЧАП. 047 )ХЕ ОЧЕВР|ОЫ 046 БТХ 0,1(В1.1МКТ) йьТМК(гП) г- АЧА1ь, ЕТАС(гП) +- 1. 049 ЕРХ ЗВ(0:2) 050 БТА ьг1(0'.2) 051 БТХ е(111МК) Узел, представляющий Яп" Узел, представляющий Я Р Узел, представляющий "х 125 е ПРОГРАММЫ ДИФФЕРЕНЦИРОВАНИЯ 1ОВ СОМ 1О9 СОНЕ СОН О Узел, представляющий "2". 110 СОН 2 Ш 1.00 СОН 2(ТУРЕ) Ц2 АЕР ЕН 118 НЕСОР СОМ 3(ТУРЕ) Узел, представляющий "пей".
1Ц АЕР МЕС 115 Р(ЛБ СОН 4(ТУРЕ) 115 АЕР + 117 И1МОБ СОН б(ТУРЕ) Узел, представляющий "-". 118 А1.Р 119 Т1ИЕЗ СОН б(ТУРЕ) 120 АЕР 121 31.АБН СОМ ?(ТУРЕ) Узел, представляющий "/". 122 А1.Р / 128 ОРАВВОМ СОМ б(ТУРЕ) Узел, представляющий "?". 12Л АЬР яе ! Оставшаяся часть программы соответствует программам дифференцирования 01РР [О), 01РР [Ц,...; эти программы задуманы так, что после обработки бинарного оператора они возвращают управление шагу [)3, а в противном случае — шагу [)4. 125 УАВ1АВЕЕ 127 128 129 189 СОМЯТАНТ 181 182 1Н 188 181 2Н 985 ЕН 185 187 182 189 ЦО Ц1 Ц2 НЕС Ц8 1Ц Ц5 Цб Ц7 Цо А00 Ц9 159 ЗН 151 152 158 151 1Н С +- адрес нового дерева.
Возврат к управляющей программе гП < — Т"ЕЕ( 1 0 г11). 0 +- г11, возврат к управляющей программе г11 +- ТЕБЕ("пей",О) . 0 < — г11, возврат к управляющей программе Возврат к управляющей программе бинарный оператор. ЕОХ 1,2 ЕМТА СОН1 СМРХ 2Р Верно ли, что 1МГО(Р) = "Х"? ЛЕ я+2 Если верно, вызвать функцию ТАЕЕ(1).
ЕНТА СОМО Вызвать функцию ТАНЕ(0) . ЛМР ТВЕЕО ЕНТЗ 0,1 ЛМР 04 АЬР Х 10А 1,б ЛАЯ 04 Возврат к управляющей программе, ЛИР СОРУР1 если 1ИГО(0) = 0; в противном случае ЕНТХ О,З установить гП +- СОРУ(Р1). ЕМТА ЗЕАЗН ЛМР ТВЕЕ2 ЛМР 1В ЕОА 1,Б ЛАЯ 04 Если 1НГО(0) = О, возврат. ЕМТА МЕСОР ЕМТ1 О,Б ЛИР ТВЕЕ1 ЛМР 1В ЫИ 1,б ЛАКЕ 1Р Переход, если не выполняется 1МГО(01) = О. ЕОА АУА1Е АУА1ь ~ 01. БТА О,б((Л.ТМК) ЯТ6 АУА11.
ЛИР 03 1.0А 1, б 1Р АЧА1 ь 0,5(ьь1МК) гП е-ВЛ,Т(СОРТ(Р1),Ц) Ц <- гП ии.т 1н 192 193 194 195 196 197 198 199 200 О, 2 (ТУРЕ) 2Р 1,1 1 1Р 0,1(ТУРЕ) 1Р 201 202 208 205 205 1Н 155 156 157 158 159 160 161 162 168 161 165 166 167 168 169 170 171 172 178 174 175 176 177 178 179 180 181 182 188 184 185 186 187 188 189 190 191 2Н 1Н 4Н ЯОВ 1Н И(Н. 1Н ЛАМЕ ьОА ятА ятб ЕМТБ ЛИР ЕМТА КМТХ кмт1 ЛИР ЕИТБ Л(Р ьОА ЛАЕ ЫА ЛАМЕ ЕМТА ЕИТ1 ЛИР кмтб ЛИР ЕМТА ЛИР ьОА ЛАЕ ЛИР ЕМТА ЛИР ЕМТб КОА ЛАЕ ЛИР ЕМТА ЕИТ1 ЛИР ЕМТБ ЛНР ятл ЯТА ЯТ2 китг 'ьОА РЕСА ЛАМЕ КОА ЛАЕ ьОА ОКСА ЛАМЕ ьОА ЛАМЕ 'АЧАП. О,б 03 Р(ЛЯ о,б 0„5 ТНЕЕ2 О,1 оэ 1,5 28 1,5 1Р ИЕООР 0,5 тнек1 О,1 зв И1ИОЯ 4в 1,б 1Р СОРУ2 О,б ий.т О,1 1,5 АРО СОРУР1 О,1 О,Б И01.Т 0,1 Аи) 9Р 1Р(о:г) ЯР(0:2) 1,2 1 1Р Переход, если не выполняется 1МРО(Ц) = 0 АЧА1Ь с Ц Ц г — 01 Возврат к управляющей программе Подготовиться к вызову ТАНЕ("+",01 Д) Ц+- ТАЕМ(к~",Ц1Д) Возврат к управляющей программе Переход, если 1МРО(Ц) = О.
Переход, если не выполняется ТМРО(01) = 0 Ц < — ТМЕЕ("пебв,Ц) АЧА11 с Ц1 и возврат. Подготовиться к вызову ТАНЕ(" †",01 Ц) Переход, если 1МРО(Ц1) = О, в противном случае гП < — СОРТ(Р2) гП <- М1Л.Т(01,СОРТ(Р2)). 01 +- гП Переход, если 1МРО(Ц) = О, в противном случае гП <- СОРТ(Р1) . Подпрограмма МО(.Т(гА.г11) .
Пусть гА се О, гП ее Ч Сохранить г12 г12 <- о Проверить, верно ли, что 1ИРО(О) = 1, и верно ли, что ТТРН(0) = 0 Если не верно, проверить, верно ли ТМРО(Ч) = 1 и верно ли, что ТТРЕ(Ч) = О. Если верно, выполнить обмен У ел Ч. АЧАТЕ ~ О. В результате получим Ч. В результате получим ТЕЕЕ("х",О,Ч). Восстановить г12. Выход из И1Л.Т с результатом в гП. 3 Две другие программы 01Ч н РИН выглядят аналогично, н читателю предлагается самостоятельно создать нх в качестве упражнения (см. упр. 15 н 16).
УПРАЖНЕНИЯ 1. [20] В этом разделе приводилось формальное определение бинарного дерева В(Р), соответствующего лесу Р. Дайте формальное определение с обратным сллыслом, т. е. определите лес Г(В), который соответствует бинарному дереву В. 2. [20] Обозначение дерева в десятичной системе обозначений Дьюи дано в разделе 2.3, а обозначение бинарных деревьев — в упр. 2.3.1 — 5. Таким образом, узел "Т' в (1) представлен в виде "2.2.1", а в эквивалентном бинарном дереве (3) — в виде "11010". Если это возможно, предложите правило, которое непосредственно выражает естественное соответствие между деревьями и бинарными деревьями на основе десятичной системы обозначений Дьюи. 3.
[22] Какая существует связь между десятичной системой обозначений Дьюи для узлов леса и прямым и обратным порядками обхода этих узлов? 4. [10] Справедливо ли следующее утверждение: "Концевые узлы дерева встречаются в одних и тех же относительных позициях при обходе как в прямом, так и в обратном порндках"? б. [20] Другое соответствие леса и бинарных деревьев можно определить с помощью ЕЕХИК(Р), который указывает на крайнего справа ребенка узла ИОВЕ(Р), а также с помощью Ы.ХИК(Р), который указывает на крайнего слева ребенка узла. Пусть Г является лесом, который, такил~ образом, соответствует бинарному дереву В.
Какой порядок узлов бинарного дереяа В соотвеэттвует (а) прялюму и (Ь) обратному порядкам обхода кеса Г? 8. [25] Пусть Т является непустым бинарным деревом, в котором каждый узел имеет 0 или 2 детей. Если рассматривать Т как бинарное дерево, оно соответствует (на основе естественного соответствия) другому бинарному дереву Т'. Существует лн какая-либо простая связь между прямым, симметричным н обратным порядками обхода узлов дерева Т (согласно их определениям для бинарных деревьев) и теми же порядками обхода узлов дерева Т ? 7. [М20] Лес макет рассматриваться как частично упорядоченный, если считать, что каждый узел дерева расположен перед его последователями.
Можно ли утверждать, что узлы рассортированы в топологическом порядке (согласно определению в разделе 2.2.3), если они находятся: (а) в прямом порядке, (Ь) в обратнолл порядке, (с) в реверсивном прямому порядке и (Й) в реверсивном обратному порядке? 200 207 200 200 2Н 210 211 212 210 1Н 214 215 210 8Н 217 9Н БТ1 я+2(0:2) ЕИТ1 0,2 ЕИТ2 я ЕОА АЧА11. БТА 0,2(1.1.1ИК) БТ2 АЧА11. 5ИР 8Р ЕИТА Т1ИЕБ ЕИТХ 0,2 ЛИР ТНЕЕ2 ЕИТ2 я 1ИР ь 8. [МОО] В упр.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
