AOP_Tom1 (1021736), страница 155
Текст из файла (страница 155)
(Если вообразить ту же ситуацию, в которой номера всех этажей увеличены на единицу, состояние БТАТЕ = МЕОТНАР или БТАТЕ = С01МСОР при открытых дверях лифта приведет к тому, что лифт, вероятно, продолжит движение вниз либо безусловно двинется вверх.) 4. Если десять или более человек выходит на одном этаже, состояние может оставаться нейтральным все это время; и когда шаг ЕБ вызовет подпрограмму РЕСТБХОИ, это может привести к заданию нового состояния до того, как кто-то войдет в кабину лифта. На самом деле такое случается очень редко [и, несомненно, это было бы самое загадочное явление, которое автор наблюдал во время экспериментов с лифтом.) б.
Со времени открытия дверей лифта в момент 1063 и до момента 1183, когда человек 7 вошел в него, состояние лифта нейтрально, так как никаких вызовов с этажа О не поступило и в кабине лифта никого нет. Тогда пользователь 7 установит САЕЕСАН[21 ( — 1„и состояние лифта соответственно станет равным СОТМСОР. 6. Нужно добавить условие "если СОТ < 18, то БТАТЕ ф СОТИСОР; если ООТ ) 1И, то БТАТЕ ф 001МСРОМИ" к условию "Р[.ООН = 1И" на шагах [12 и 114. На шаге Е4 следует взять пассажиров из очереди ООЕОЕ [РРООН), если они направляются в ту же сторону, что и лифт; при этом лифт не должен находиться в нейтральном состоянии БТАТЕ = ИЕОТНА1., иначе будут взяты все пассажиры.
1В здании факультета математики в Станфорде установлен именно такой лифт, но его пользователи на самом деле не обращают никакого внимания на внешние индикаторы, т. е. они входят в кабину независимо от направления движения. Почему бы конструкторам лифта не учесть этот факт и определить логику работы лифта без переменных САШ1Р и САШ10987 Тогда работа лифта в целом ускорилась бы, так как он не останавливался бы так часто.] 7.
В строке 227 предполагается, что этот человек находится в списке ИА1т. Переход к шагу 04А подтвервсдает, что такое предположение является верным. Предполагается, что значение 01ТЕОРТ1МЕ положительно и действительно равно 100 или даже больше. 8. Читателю предлагается самостоятельно изучить этот код, 877 Е8 РЕС4 1 278 ЕМТА 01 879 ОМР МОРОС 880 РРА САЬ[.,4(3:Б) 881 ЗАР 1Р 888 ЕМТ1 -2,4 288 112 2Р 2ВЛ БОА 2ВБ ЛАЕ 2Вб 2Н БОА 227 АОО ЯВВ АОО 299 АОО 290 ЛАМЕ 291 1Н ЕМТА 292 ЛНГ Са.1, Ц1:1) ЕБ СА1.1.-1- 4 СА11-2,4 САБЕ-З,4 САБЬ-4.4 Е8 23 Е2А Установить .1 +- 2. [)4.
Изменение состояи я Л = Г1.008 не допускается в общем случае. 1)5. Ли т в состоянии ж анссяг Совершить переход, если лифт не на шаге Е1 нлн 1 = 2. В протнвном случае запланировать Вб. Ожидать в течение 20 еднннц. Сохранить г)6. 21 25 8Н Яб 27 ЯВ Я9 ЭО 8Н 21 9Н ЕМТЗ Е6 ЕМТА 20 БТБ 8Г(О:2) ЕМТБ Е.ЕЧ1 БТЗ 2,6(МЕХТТМБТ) ЛМР НОТР ЕМТБ с ЛНР Установить МЕХТХМБТ для шага ЕЗ нлн Еб.
Запланировать действия. Восстановить г[6. Выйти нз подпрограммы. А 11. Пусть сначала БХМК[?с) = О, 1 < )с < и, и НЕАО = — 1, На шаге изменения Ч[?с) следует сообщить об ошибке, если БТМК [)с) ф 0', в противном случае установить БТМК [)с) +- НЕАО, НЕАО +- )с и определить для МЕНТ[)с] новые значения Ч[1с]. После каждого этапа моделирования установить )с +- НЕАО, НЕАР с — — 1 н несколько раз (нлн нн разу) выполнять следующие действия до тех пор, пока не получим?с < 0: установить Ч[)с) с — МЕМЧ[)с), 1 +- 11мк[А), 11мк[А) + О, й с- с.' Ясно, что этот метод легко адаптируется для переменных, произвольным образом разбросанных в памяти, если включить поля МЕМЧ и 11МК в каждый узел переменной Ч. 9.
01 ОЕСТБЛОМ 02 09 04 05 05 07 0В 09 1Н 10 11 12 1Н 1Э 11 15 15 17 1В 2Н 19 20 21 22 ЯЭ БТЛ 9Г Сохранить адрес хранилища. ЛБМЕ 9Г В1. Н жио лн п унять ешеиие? )Л)Х ЕХЕЧ1+2(МЕХТТМБТ) ОЕСХ Е1 Л)2. Сле ет отк ыть ве и лн та? ЛХМЕ 1Г Совершить переход, БОА СА(Л.+2 если лифт не в состоянии Е). ЕМТЗ ЕЗ Подготовнться к шагу ЕЗ, ЛАМЕ БГ если есть вызов на этаж 2. ЕМТ1 -4 ВЭ. Есть ли вызовы? ЮА САБЕ+4,1 Поиск ненулевого значения ЛАМЕ 2Г переменной вызова.
ТМС1 1 гП шЛ вЂ” 4. Л1МГ с-3 БОА 9Г(0:2) Равны нулю все СААБ[1),.1 ~ Н.СОН. РЕСА ЕБН Равен лн адрес выхода строке 250? ЛАМЕ 9Г ЕМТ1 "2 ЕМТБ 4,1 ОЕСБ 0,4 БТАТЕ с- 1 — ГБООН. ЛБМЕ с+2 ЛАМЕ 18 ЛХМЕ 9Г ЛБЕ 9Г 12. В списке МА1Т операции удаления выполняются слева направо, а операции вставки— справа налево (так как поиск будет, скорее всего, выполнен именно с этой стороны). Кроме того, узлы удаляются из всех трех списков в нескольких местах, когда узел-предшественник и узел-наследник удаляемого узла неизвестны. Только список ЕЬЕТАТОВ можно преобразовать в односвязный список без существенного снижения эффективности. Замечание.
В дискретном моделировании для сокращения времени сортировки было бы предпочтительнее применить нелинейный список типа МА1Т. В разделе 5.2.3 рассматривается общая проблема обработки очередей по приоритету или списков наподобие "наименьший входит — первый выходит". Известно несколько способов, в которых для вставки или удаления в списке и элементов потребуется выполнить только 0(1о8 и) операций, хотя такой причудливый способ вряд ли стоит применять для малых и.
РАЗДЕЛ 2.2.6 1. (Здесь индексы находятся в диапазоне от 1 до и, а не от 0 до и, как в (6).) ЬОС(А[1,К)) = ЬОС(А[0,0)) + 2иу+ 2К, где предполагается, что А[0,0) на самом деле не существует. Если установить 1 = К = 1, получим ЬОС(А [1, 1) ) =(ОС(А [0,0) ) +2и+2, а потому ответ можно представить несколькими способами. Тот факт, что значение ЬОС(А[0,0)) может быть отрицательным, часто приводит к появлению ошибок в работе компиляторов и процедур загрузки.
2. ЬОС(А[1ю...,[ь)) = ЬОС(А[0, .О)) + ~,<„< а,1, = ЬОС(АП1,...,Ы) + 2',«,„а,1, — 2',«„„а,(„где а, = сп„,< (и. -1. 4. 1). Замечание. Обобщение для структур, которые встречаются в таких языках программирования, как С, и простой алгоритм для вычисления соответствующих констант можно найти в работе Р. Репе!, САСМ 9 (1966), 344-347. 3. 1 < А < 1 < и тогда и только тогда, когда 0 < )с — 1 < 1' — 1 < и — 1. Поэтому заменим )с, 1, и значениями )с — 1, 1 — 1, и — 1 соответственно во всех формулах для нижней границы, равной нулю.
4. ЬОС(А[1,К)) = 10С(А[0,0) ) + и) — 1(1 — 1)/2+ К. 5. Пусть АО = ЬОС(А [0,0) ) . Тогда существует по крайней мере два следующих решения (в которых предполагается, что 1 находится в регистре гП, а К вЂ” в регистре г12); (1) 'ЬОА ТА2, 1: 7", где по адРесУ 712+1 хРанитсЯ команда "МОР 2 ь1*172+А0,2"; (й) "ЬОА С1,7: 2", где по адресу С1 хранится команда "МОР ТА, 1: 7", а по адресу ТА+1' — команда "МОР 1+1ь)/2+40". В последнем случае потребуется выполнить на один цикл больше, но при этом таблица не будет связана с индексным регистром 2. В.
(а) ЬОС(А[1,1,К)) =ЬОС(А[0,0.01) + ( ) + ( ) + ( ) (Ь) 10С(В[1,1,К)) = 100(В[0,0,0)) (и+ 3) (и+ 3 — 1) (и+ 2 — 1) (и+ 2 — 1) Следовательно, в данном случае можно получить аналогичное выражение для адреса произвольного элемента массива. г 1 г + )с — г т 7. ЬОС(А[11,...,1ь]) =ЬОС(А[0,...,0))-Ь ~ ( ). См. упр.
1.2.6-56. )+А — г 1«ь 8. (Решение П. Нэша.) Пусть элементы массива 1[1,1,К] определены для 0 < 1 < и, 0 < 1 < п+ 1, 0 < К < и+ 2. Тогда А[1,1,К) = 1[1,1,К): В[1,3,К) = 1[1,1+1,К); С [1, 1, К) = Х [1, К, 1+ 1); О [1, 1, К) = Х [1, К, 1+ 2]; Е [1, 1, К) = Х [К, 1 + 1, 1+ 1); Р [1, 1, К) = К[К,1+ 1,1+ 2). Эта схема наиболее удобна, поскольку позволяет без накладок упаковать (и+ 1)(и+ 2)(и+ 3) элементов шести тетраэдрических массивов в последовательном порядке. Доказательство< А и В заполняют все ячейки 1[<,),)с] с )с = ш<п(<,),)с); С и 0 заполняют все ячейки с 1 = ппп(<, /, )с) ф )с, Е и Р заполняют все ячейки < = ш<п(<> 1, А) ф д А.
(Данную схему можно-(<бобщить до т размерностей, если только потребуется упаковать т! элементов обобщеннь<х тетраздрическнх массивов с помощью (и + 1) х (и+ 2)... (и т т) последовательных позиций. Для этого следует связать перестановку а<аз... ам с каждым массивом и сохранить его элементы в массиве 1[1„+ В<, 1, + Вс,...,1, + В,„), где В<В<...В, — таблица инверсии для а<а<...а„„которая определена в упр. 5.1.1 — Т.) 9. С1. Задать для Р1, Р2, РЗ, Р4, РБ, Рб значения, указывающие на первые ячейки списков РЕНАЕЕ, А21, А22, А23, ВЬОМО, ВУЗЕ соответственно, Положим в дальнейшем, что концом каждого списка является связь Л, которая гораздо меньше любой другой связи.
Если Рб = Л, прекратить выполнение алгоритма (список, к сожалению, пуст). С2. (Обход списков может вь<полняться по-разному, например сначала обрабатывается список ЕТЕБ, затем — НА1В и АОЕ и наконец БЕХ.) Установить Рб <- НА1В(РБ) несколько раз, пока не выполнится условие Р5 < Рб (если оно уже выполняется, это может и не потребоваться). Если теперь Р5 < Рб.перейти к шагу С5.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
