Д. Кнут - Искусство программирования том 1 (1119450), страница 79
Текст из файла (страница 79)
Следовательно, повторное возвращение к шагу Е4 позволяет человеку войти в лифт до закрытия дверей.) Во всех других случаях человек устанавливает САЬЬОР[1М] ~ — 1 или САЬЬООММ[1М] +- 1, а также 00Т > 1И или ООТ ( 1М. Если же 02 = 0 или лифт находится в состоянии "спячки" Е1, то выполняется указанная ниже подпрограмма ОЕС1310И. (Подпрограмма ОЕС1Я10М используется для вывода лифта из нейтрального состояния (МЕОТИАЬ) в некоторые критические моменты.) П3. [Вход в очередь.] Поместить человека в конец линейного списка ООЕОЕ[1И], представляющего людей, которые ожидают лифта на том же этаже.
Теперь человек должен терпеливо ожидать прихода лифта в течение времени 61ЧЕОРТ1МЕ, а точнее — до тех пор, пока на шаге Е4 программы будет совершен переход к шагу П5 и отменен запланированный шаг 114. 114. [Отказ от длительного ожидания.] Если РЬООМ ~ 1М или 01 = О, удалить человека из списка ЦОЕОЕ [1М] и из всей системы моделирования. (Человек решил, что лифт работает очень медленно или что небольшое физическое упражнение в виде ходьбы по лестнице все же лучше, чем езда на лифте.) Если РЬООИ = 1М и 01 ~ О, человек продолжает ждать (зная, что ожидание в этом случае не будет очень долгим во время выхода и входа других людей).
115. [Вход в лифт.] Пользователь покидает список ЦОЕОЕ [1М] и входит в лифт, т. е. список ЕЬЕЧАТОЯ со структурой стека, который представляет людей в кабине лифта. Установить САЬЬСАМ[ООТ] +- 1. Теперь, если ЯТАТЕ = МЕОТИАЬ, установить значение ЯТАТЕ +- 601ИООР или 601И600ММ и перейти к шагу Е5 через 25 единиц времени. (Эта особенность предусмотрена для того, чтобы двери могли закрыться быстрее, чем обычно, если в момент выбора человеком этажа назначения лифт находится в нейтральном состоянии. Такой временной интервал длиной 25 единиц предоставляет воз- можность на шаге Е4 убедиться в том, что значение переменной 01 правильно установлено к моменту выполнения шага Е5, т.
е. когда закрываются двери.) Теперь челйвек ожидает момента перехода к выполнению шага 1]6 по окончании шага Е4, когда лифт достигнет нужного этажа. Пб. [Выход из лифта.] Удалить пользователя из списка НЬЕЧАТОН и из системы моделирования. $ Сопрограмма Е (Лифт). Эта сопрограмма представляет действия лифта; на шаге Е4 также контролируется процесс входа людей в лифт и выхода из него. Е1.
[Ожидание вызова.] (В этом случае лифт находится на этаже 2 с закрытыми дверями в состоянии ожидания.) Если кто-нибудь нажмет кнопку, подпрограмма ОЕС131ОМ совершит переход к шагу ЕЗ или Еб. В противном случае лифт находится в состоянии ожидания. Е2.
[Изменение состояния?[ Если ЯТАТЕ = 001МООР и САЬЬОР[Д = САЬЬООММ1]] = САЬЬСАК(]] = 0 для всех у > РЬООК, то следует установить ЯТАТЕ <- МЕОТКАЬ нлн ЯТАТЕ +- 001МОООММ в зависимости от того, выполняется ли условие САЬЬСАНЦ] = 0 для всех ] < РЬООК, и установить все переменные САЬЬ для текущего этажа равными нулю. Если ЯТАТЕ = 001МОООНМ, то необходимо выполнить те же действия, но в обратном порядке. ЕЗ. [Открытие дверей.[ Задать для 01 и 02 любые ненулевые значения, По прошествии 300 единиц времени независимо выполнить шаг Е9.
(Эти действия могут быть отменены на шаге Еб до того, как они произойдут. Если они уже запланированы и не отменены, они отменяются и перепланируются.) Также независимо следует выполнить действия лифта на шаге Е5 по прошествии 76 единиц времени. Затем следует подождать 20 единиц времени (для моделирования открытия дверей) и перейти к шагу Е4. Е4. [Выход из лифта и вход в него людей.) Если для какнх-то людей из списка ЯЬНЧАТОК выполняется равенство ООТ = РЬООН, то последнему зашедшему в лифт следует перейти к шагу Пб, подождать на протяжении 25 единиц времени и повторить шаг Е4. Если таких людей нет, но список ООЕОЕ (РЬООК] не пуст, самому первому в списке следует немедленно перейти к шагу П5 вместо шага 1)4, подождать в течение 25 единиц и повторить шаг Е4.
А если список ЦОЕОЕ(РЬООН] пуст, установить 01 +- О, установить 05 не равным нулю и подождать, пока какие-нибудь другие действия не вызовут продолжение выполнения алгоритма. (Действия на шаге Е5 перенаправят нас к шагу Еб или действия на шаге Б2 приведут к повторному переходу к шагу Е4.) Е5. [Закрытие дверей.[ Если 01 ф О, подождать в течение 40 единиц и повторить данный шаг (двери при этом могут вздрогнуть„но вернуться в прежнее открытое положение, так как кто-то все еще входит или выходит). В противном случае установить 03 < — 0 и перейти к шагу Еб через 20 единиц времени.
(Так моделируется закрытие дверей после того, как все войдут в лифт или выйдут из него. Но если в ходе этого процесса на площадке перед лифтом на том же этаже появится новый человек, двери вновь откроются, как указано на шаге 1]2.) Еб. [Подготовка к движению.[ Установить переменную САЬЬСАН[РЬООН] равной нулю; установить равной нулю переменную САЬЬОР(РЬООК], если ЯТАТЕ СО1ИСВОМИ, а также установить равной нулю переменную САЬЬВОММ [РЬООК], если ЯТАТЕ ЭА 001МСОР. (Замечание. Если ЯТАТЕ = 001ИСОР, лифт не сбрасывает значение САЬЬВОММ, так как предполагается, что люди, которым нужно ехать вниз, еще не вошли в него; см.
упр. 6.) Теперь следует выполнить подпрограмму ВЕС1310И. Если ЯТАТЕ = ИЕОТКАЬ дажепосле выполнения подпрограммы ВЕС1310И, то следует перейти к шагу Е1. В противном случае, если 02 ~ О, необходимо отменить действия лифта на шаге Е9. Наконец, если ЯТАТЕ = 001ИСОР, подождать в течение 15 единиц времени (чтобы лифт ускорился) и перейти к шагу Е7; если ЯТАТЕ = 001ИСВОИ1, подсаццать в течение 15 единиц времени и перейти к шагу ЕЯ. ЕТ. [Подъем на этаж.] Установить Р1.0ОК е- РЬООК+ 1 и подождать в течение 51 единицы времени. Если теперь САЬЬСАК[РЬООК] = 1 или САЬЬОР[РЬООК] = 1 или если [(РЬООК = 2 или САЬЬВОЫИ[РЬООК] = 1) и САЬЬОР[у] = САЬЬВОММ[у] = САЬЬСАК[у] = 0 для всех у > РЬООК), подождать в течение 14 единиц времени (чтобы лифт притормозил) и перейти к шагу Е2.
В противном случае повторить данный шаг. Е8, [Спуск на этаж.] Этот шаг подобен шагу Е7, если поменять направление движения, а временные интервалы длительностью 51 и 14 единиц заменить интервалами длительностью 61 и 23 единицы соответственно. (На спуск лифту требуется больше времени, чем на подъем.) Е9. [Установка индикатора бездействия.] Установить 02 е- 0 и выполнить подпрограмму ВЕС1310И. (Это независимое действие инициируется на шаге ЕЗ, но оно почти всегда отменяется на шаге Еб. См.
упр, 4.) 1 Подпрограмма 1Э (]?адпрограмма ВЕС1310И). Как указано в приведенных выше сопрограммах, эта подпрограмма выполняется в критические моменты времени, когда должно быть принято решение о выборе направления движения. Ш. [Необходимо ли принять решение?] Если ЯТАТЕ ф ИЕОТКАЬ, выйти нз этой подпрограммы. ТУ2. [Следует ли открыть двери лифта?] Если лифт находится на стадии выполнения действий шага Е1 и если САЬЬОР [2], СА1.1.САК [2] и САЬЬВОМИ [2] не равны нулю, то нужно после паузы длиной 20 единиц времени перейти к шагу ЕЗ, а затем выйти из этой подпрограммы. (Если в данный момент подпрограмма ВЕС1310И вызывается во время выполнения некоторых независимых действий на шаге Е9, то сопрограмма лифта может перейти к шагу' Е1.) ТуЗ. [Есть ли вызовы?] Найти наименьшее значение у ф РЬООК, для которого САЬЬОР[у], САЬЬСАК[у] или САЬЬВОММ [7] не равно нулю, и перейти к шагу [У4.
Но если такое значение ] отсутствует, следует установить у е- 2, если в данный момент подпрограмма ВЕС1310И вызывается на шаге Еб; в противном случае следует выйти из подпрограммы. ]24. [Изменение состояния.] Если РЬООК > у, установить ЯТАТЕ +- 001ИСВОИИ., если РЬООК ( ], установить ЯТАТЕ +- С01ИСОР. В5. [Лифт ожидает?] Если сопрограмма лифта находится на шаге Е1 и у ф 2, то по прошествии 20 единиц времени перевести лифт к шагу Еб. Выйти из подпрограммы. 1 Эта модель работы лифта гораздо сложнее других описанных выше алгоритмов, но взятый из повседневной жизни пример более типичен для задач моделирования, чем любой состряпанный на скорую руку "учебный пример".
Для понимания принципа работы такого лифта рассмотрим табл. 1, которая представляет собой фрагмент одной из многих попыток моделирования. Вероятно, проще всего начать с проверки простого случая, например с момента 4257: лифт находится в состоннин покоя на этаже 2 с закрытыми дверями во время появления человека по имени Дон (в момент 4384). Две секунды спустя двери открываются и Дон входит в кабину лифта еще через две секунды. Нажав кнопку "3", он отправляет лифт вверх и наконец выходит на этаже 3, а лифт возвращается на этаж 2.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
