Д. Кнут - Искусство программирования том 1 (1119450), страница 81
Текст из файла (страница 81)
В строках 101 — 114 создается узел для этого нового человека и записываются этажи входа (1И) и выхода (СОТ). Стек АЧА11. является одиосвязным по полю ЕХ.ХИКХ каждого узла. Обратите внимание, что в строках 101 — 108 действие "С с.= АЧАХЕ" выполняется с полщщью метода РООЕМАХ, 2.2.3 — (7); при этом вряд ли здесь понадобится проверка события переполнения (ОЧЕЕРЮЧ), так как общий размер пула (количество людей в данной модели работы лифта в произвольный момент времени) едва ли превышает 10 узлов (40 слов). Возврат узла в стек АЧА1Е представлен в строках 156-158.
Во всей этой программе индексный регистр 4 равен переменной РЕООМ, а индексный регистр 5 положителен, отрицателен или равен нулю в зависимости от текущего состояния, т. е. при выполнении условия БТАТЕ = С01ИСОР. БТАТЕ = СО1ИСООЧИ или БТАТЕ = ИКОТКАМИ соответствеиио. Переменные САХ.Х.ОР[1], СКАХ,САМ[1) и САХ.ЕЮОЧИ[11 занимают соответственно поля (1:1),(3:3) и (5:5) ячеек СА11 + 1'. 097 э СОПРОГРАННА О 098 01 Л(Р ЧА1ЛЕЗ 099 ХОА 1МТЕМТХНЕ 100 1НР НОЕО 101 196 АЧАП. 102 16Р 1Р 108 106 РООХНАХ(0:2) 104 ХМСб 4 С л — РООХМАХ+ 4.
07б 2Н Ы2 077 БТ2 078 БТ1 079 5Т6 080 516 081 9Н 1НР 082 Рехетеч 511 088 191 084 102 088 5Т1 ОВб БТ2 087 9Н Л(Р 088 стс151 Бтэ 089 1НР 090 НОЫС ЗТ1 091 Л(Р 092 СТСХЕ ьРБ 098 ХОА 094 БТА 098 1НР 09б 1НР 0,1(Ы.ХМК1) 0.6(КХХМК1) 0,6(ШМК1) 0.1(51.1МК1) 0,2(ШМК1) 9Р 0.6(ХЛ.ХМК1) 0,6(И.ХМК1) 0,2(ШМК1) 0,1(КУ.ХМК1) 2.6(МЕХТ1МЗТ) стс1.е 2,6(МЕХТ1МБТ) НОй) ЧАХТ(К(.ХМК1) 1,6 11НЕ ОН.ЕТЕЧ 2,6 Повторять до тех пор, пока МЕХТТ1НЕ(С) > МЕХТТХНЕ(Р). О < — М(.ХМК1(Р). Ы.ХМК1(С) +- О.
11.1МК1(С) +- Р. 51.1МК1(Р) +- С. ШНК1(О) +- С Выйти из подпрограммы. Удалить МООЕ(С) из списка ЧА1Т. (Такой же код, как в строках 058-063, ио ШМК1 и 511МК1 используются вместо ШНК2 и К(.ХМК2.) Установить МЕХТ1МБТ(С) +- г1, Вставить МООЕ(С) в список ЧАХТ с задержкой гЛ. Установить текущий узел С +- КХХМК10.ОСОХА1Т) ' (11. Вх в систем ожн ание сле гю его человека.
Вычислить ХМ, ООТ, СХЧЕОРТХНЕ, 1МТЕКТХНЕ ХМТЕКТХНЕ вычисляется подпрограммой ЧА1ОЕБ Разместить МООЕ(С) в списке ЧА1Т с задержкой 1МТЕКТ1НЕ. С л- АЧАХХ. Если АТАГИ Эл Л, совершить переход 105 105 107 108 ЛОУ ЦО ЛИ ЗТО РООЕНАХ(0:2) ЛНР «+3 Т.ПА 0,6(И.1МН1) ЗТА АЧАТЬ Ы1 1ИРСООН ЗТ1 0.6(1М) С02 ОПТРСООН 1Н 112 118 ЛЦ 115 572 3,6(ООТ) НИТА 39 БТА 2,6 ЕИТА 0.4 02 ЗН ТИ(С) — Р1.СОН. 11б 117 Цб 119 ИО 121 122 128 124 125 12б 127 128 12У 1Я0 1Я1 182 188 184 185 Иб И7 ИЯ ИУ 140 Ц1 Ц2 ЦЯ Ц4 Ц5 Цб 147 ЦЯ ЦУ 150 151 152 4Н 2Н ОЗ 04А 04 ПЕСА 0,1 ЗТб ТЕИР ЛАМЕ 2Р ЕМТб Е1.ЕЧ1 ЕПА 2,6(ИЕХТ1ИЗТ) ПЕСА Еб ЛАНЕ ЗР ЕИТА ЕЗ ЗТА 2,6(МЕХТТМЗТ) Л(Р ПП.ЕТЕИ ЛМР 4Р ЕПА ПЗ ЛАЗ 2Р БТЗ 01 БТ2 ПЗ Л(Р 1ИИЕП ЛМР 03 ПЕС2 0,1 ЕМТА 1 ЛЯР «+3 БТА САПЕ,1(б:б) ЛНР «+2 БТА САН.,1(1:1) ЫА 02 ЛАХ «+3 ЕПА ЕСЕЧ1«2(ИЕХТТМЗТ) ПЕСА Е1 ЛАЗ ПЕС1510И 106 ТЕИР 001 0,6(ТИ) ЕИТ1 ОПЕОЕ,1 ЛМР 1МЗЕНТ СПА С1ЧЕОРТ1НЕ ЛИР Н010С 10А 0,6(1И) ПЕСА 0,4 ЛАЯХ «+3 РООЕНАХ +- С.
Предполагается. что переполнение ие происходит. АЧА11 «- НСТИК1(АЧА1Ы, гП +- ТМРЕООН (вычисляется подпрограммой ЧАШЕЯ). 1М(С) +- гП. г12 «- ПОТИ.ООН (вычисляется подпрограммой ЧА|ОЕЗ). ООТ(С) +- г12. Поместить константу 39 (код операции ЛНР) в третье слово структуры (6). ()2. Пол челне сигнала и ожг ание. Установить гА +- Р10ОН. РСООН вЂ” 1И. Сохранить значение С. Совершить переход, если Р1,00Н ~ ТИ. Установить С «- 1ОС(Е1.ЕЧ1). Находится ли лифт иа шаге Е67 Если да, перейти к шагу ЕЗ. Удалить его из списка МА1Т и повторно вставить в начало списка ИА1Т.
Совершить переход, если 03 = О. В противном случае присвоить 01 ненулевое значение. Установить 03 «- О. Вставить П.ЕЧ1 в начало списка МА1Т. (гП и г12 изменены.) г12 +- ОПТ вЂ” ХМ. Совершить переход, если лифт направляется вверх. Установить СА1100ИИ (1М) +- 1.
Установить САШ)Р(ТИ) < — 1. Если 02 = О, вызвать подпрограмму ПЕСТЗТОИ. Если лифт находится иа шаге Е1, вызнать подпрограмму ПЕС1510И. ~«з. в гП +- ЕОС(ПОБОЕ [1И] ) Вставить ИОПЕ(С) с правого конца ООЕОЕПИ). Подождать 01ЧЕОРТ1МЕ единиц времени. ()4. Отказ от кительного ожн ануя. РЬООН = 1И(С), См.
упр, 7. ~««.В .ЮИ««« из ЦОЕОЕ или ЕЬЕЧАТОН. АЧА1ь с С. Код сопрограммы Е представляет собой очень прямолинейную реализацию приведенного выше полуформального описания. Вероятно, наиболее интересная его часть связана с подготовкой независимых действий лифта на шаге ЕЗ и поиском в списках ЕЕЕЧАТОН и ООЕОЕ на шаге Е4. 178 в СООРОГРАННА Е 175 Е1А 1НР СТСьЕ1 175 Е1 ЕОО 176 Е2А )НР НОьОС 177 Е2 15И 1Р 178 ЬОА САБЕ+1,4 179 А00 САьь+2,4 180 А00 САьЬ+3,4 181 АОО САБЕ+4,4 188 1АР ЕЗ 188 ьОА СА11.-1,4(3:3) 184 АОО ОА11-2,4(3:3) 185 А00 САЬЬ-3,4(3:3) 186 АОО САьь-4,4(3:3) 187 )НР 2Р 188 1Н ЬОА САУЛ.-1,4 189 АОО САьь-2,4 Установить МЕЕТ1МЗТ +- Е1,перейти к СТСьЕ. Е1. Ожи ание вызова. (Никаких действий.) ЕЕ.
Изменение состояния? Движение вверх (001МООР). Есть ли вызовы на верхние этажит Если нет, посылали ли пассажиры лифта запрос для перехода к нижним этажам? Движение вниз 001ИОООММ. Действия те же, что и в строках 178 — 186. 196 А00 САБЕ+4,4(3«3) 197 2Н ЕИМБ 0,5 198 ЗТЕ САьь,4 199 )АИЕ ЕЗ ЕОО ЕИТБ 0 158 ьОА 154 1АИЕ 155 ОБ )НР 156 ьОА 157 БТА 158 ЗТ6 159 1НР 160 ОБ 1ИР 161 ЕИТ1 168 Л1Р 168 ЕМТА 164 ь02 165 БТА 166 15МЕ 167 ОЕС2 168 ЕИТ5 169 ЕМТБ 170 1НР 171 ЕМТА 178 1НР 01 04А ОЕЬЕТЕ АЧА1ь 0,6(НЬ1651) АЧА15 СТСьЕ ОЕьЕТЕ ЕЬЕЧАТОН 1ИЗЕНТ 1 3,6(ООТ) СА11.,2(3:3) СТСЬЕ 0.4 0,2 ЕьЕЧЕ ОЕьЕТЕМ 25 ЕБА Продолжить моделирование. ««««. «*««е «в«<«« из ООЕОЕ. Вставить его с правой стороны списка ЕЬЕЧАТОН.
Установить САЬЬСАН[ООТ(С)) ~- 1. Совершить переход, если БТАТЕ ~ МЕОТНАь г12 - ООТ(С) - РЬООН. Установить направление движения для БТАТЕ Установить С < — 1.ОС(П.ЕЧ2). Удалить шаг ЕБ из списка МА1т Повторить шаг ЕБ спустя 25 единиц времени. $ Изменить направление движения в БТАТЕ. Установить переменные САьь равными нулю.
Совершить переход при вызове обратного направления; в противном случае установить ЗТАТЕ +- ИЕОТНАь. ЕЗ. Отк ытпе ве й. ЕЗ ЕМТб 10А ЛАМЕ ЕМТА ЛНР ЕМТб ЕМТА Л(Р БТ6 БТб ЕМТА Е4А ЕМТб ЕБА ЛИР Еб 10А ЛАЗ ЕМТА Е5А 03 Е1.571 20 Н010С 240 241 242 248 244 ЛИР БТХ ЕМТб ЕМТА ЛИР 245 246 247 к+2 СА11,4(1:3) к+2 Еб ЛБМ БТХ ЛБР САь1,4(3:5) 248 572 201 202 208 204 205 206 207 208 209 210 211 212 218 214 215 216 217 218 219 220 221 222 228 224 225 226 227 228 229 280 281 282 288 284 285 286 287 288 289 Е4 1Н 1Н 2Н 1Н ЛНР НИТА БЕА ЕМТб 106 СИРС ЛЕ СИРА ЛИЕ ЕМТА ЛНР 106 СМРб ЛЕ ЛИР ЕМТА БТА ЛИР ЕМТА ЛИР 5ТХ БТб ЛИР Н.ЕТЗ 0,6 ОЕЕЕТЕМ 300 Н01.0 ЕЕЕТ2 76 Н010 02 01 20 е~.ет1 НОЕОС 0,4 4 НЕНАЧАТОЕ З,б(111МКг) ЕЕЕЧАТОН 1Р З,б(ООТ) 10 06 2Р ОСЕОЕ+3, 4 (М.1ИК2) 3.600.1МХ2) 1Р ОЕЕЕТЕМ 05 2,6(ИЕХТ1МБТ) 1ИИЕО 25 Е4А 01 03 СТОЕК НОВАС 01 «+3 40 Если шаг Е9 уже заплапп(юван, удалить его из списка МА1Т, Запланировать шаг Е9 спустя 300 единиц времени.
Запланировать шаг Е5 спустя 76 единиц времени. Установить 02 не равной нулю. Установить 01 не равной нулю. Е4. Выхо из ли та и вхо в него. Ввести значение РЕООЕ в поле ООТ регистра гА. с +- 1.0с(БГ.НТАХОЕ). С +- ШМК2(С). Поиск в списке ЕЕЕМАТОК справа налево. Если С = 1ОС(ЕЕЕТАТОЕ), завершить поиск.
Сравнить ООТ(С) с РЕООК. Если они не равны, продолжить поиск; в противном случае приготовиться к переходу человека к шагу ()6. Установить С <- М.1МК2(КОС(ЦОЕОЕгРЬООК))). Верно ли, что С = КЕ1МК2(С)? Если верно, то очередь пуста. Если неверно, отменить шаг ()4 для этого человека. Подготовиться к замене шага ()4 шагом ()5.
Установить МЕХТ1И5Т(С). Поместить человека в начало списка МА1Т. Подождать 25 единиц времени и повторить шаг Е4 Установить 01 <- О. Установить 03 не равной нулю. Вернуться к моделированию других событий. Е5. Зак ытпе е ей. Верно ли, что 01 = О? Если неверно, значит, люди все еще входят или выходят. Подождать 40 единиц времени и повторить шаг Е5. Если 01 = О, установить 03 +- О. Подождать 20 единиц времени, затем перейти к шагу Еб. Еб. П готовка к впженпю. Если БТАТЕ ф С01ИСООМИ, то сбросить значения СА(Л.ОР и СА1Л.САН для этого этажа. Если ~ 001МСОР, сбросить САььСАН и СА(ЛЛОММ Выполнить подпрограмму ОЕС131ОИ.
Если ЗТАТЕ = МЕОТИАь, перейти к шагу Е1 и подождать. В противном случае, если 02 ~ О, отменить шаг ЕУ (см. строку 202). Поцождать 15 единиц времени. Если ЗТАТЕ = 001МОООИМ,перейти к шагу Е8. ЕТ П Есть ли вызовы на верхние этажи? Пора остановить лифт, Подождать в течение 14 единиц времени и перейти к шагу Е2. (См. упр, 8.) 292 1НР Е2А 298 ЕУ ЗТ2 О,б 2У4 3Т2 02 295 1НР ОЕС131ОМ 296 )нР стсье Подпрограмма ОЕС1Б10М здесь не рассматривается (см.
упр. 9)., как и подпрограмма ЧА[ЛЕБ, которая применяется для указания запросов лифта. В самом конце программы приводится следующий код: ВЕО1И ЕМТ4 2 В начале РьООИ = 2 ЕМТБ О и ЗТАТЕ = ИЕОТЕАь. 1НР С?С[.Е Начать моделирование. РООЕМАХ МОР РОСЕ РО01. ЕИО ВЕО1М Вслед за пулом располагаются литералы, временное хранилище. 5 Приведенная выше программа прекрасно моделирует работу лифта, но выполнять ее бесполезно, поскольку она не выводит никаких выходных данных! На самом деле автор добавил в нее подпрограмму РЯ1МТ, которая вызывалась в наиболее 249 152 250 Е53 152 251 ьОА 252 1А2 256 ЕИТб 254 1НР 255 371 256 ЕМТ5 257 ЕИТА 256 153 259 Е7Я 1ИР 260 Е? 1МС4 261 ЕМТА 262 1НР 265 10А 264 1АР 265 ЕМТ1 266 112 267 10А 266 1АЗ 269 2Н ьОА 270 АОЭ 271 АОО 272 АОО 276 1АИЗ 274 1Н ЕИТА 275 1МР 276 ЕВА 1МР ОЕС1310И Е1А 02 и+4 ЕШ~3 ОЕЬЕТЕИ ЕьЕЧЗ ЕьЕТ1 15 Е8А НОьОС 1 51 НОЫС САЫ.,4(1:3) 1Р "2,4 2Р САП..4(5;5) Е7 СА11.+1,4 САьь+2,4 САьь+3,4 САьь+4,4 Е7 14 Е2А НОьОС Подождать в течение 51 единицы времени.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
