не будет работать корректно. Алгоритм М с Р = М также даст ожидаемый результат. Алгоритм М с Р = Q приведет к ому, что многочлен (Р) <- многочлен (Р), умноженный

на (H-<i)(H-«г) ..• (! + <*), если II = <i +<2 Н-----\-tk (хотя это не так уж и очевидно). Если

М = Q, ашгоритм М также даст ожидаемый результат, многочлен (Q) 4- многочлен (Q) + многочлен (Q) х многочлен (Р), за исключением случая, когда постоянный член многочлена (Р) равен -1 (тогда алгоритм не будет корректно работать).

10. Никакие (Единственное возможное отличие можно внести на шаге М2, а именно - удашение проверки переполнения каждого из полей А, В и С. Эти проверки не были указаны, поскольку предполагалось, что они не нужны.) Алгоритмы в этом разделе могут рассматриваться как операции над многочленами типа /(i** ,х,х), а не многочленами типа f{x,y,z).

11. Читателю предлагается самостоятельно изучить этот код.

12. Пусть скопированный многочлен имеет р членов. Для выполнения программы А потребуется время, равное (29р + 13)и, причем для более корректного сравнения к нему следует добавить время создания нулевого многочлена, например 18и для программы из упр. 14. А для выполнения программы из упр. 11 потребуется время (21р--31)и, что почти в I раза меньше.

13. ERASE STJ 9F

Перейти к шагу М2, если ABC (М) > 0. Восстановить значения переключателей.

Возврат.

Новое значение переключателя SW1.

гХ <- COEF(P) X COEF(M). АВС(Р)

+ АВС(М), если АВС(Р) > 0. Переместить в поле О 3 из г А. Сохранить гХ для SW2 и SW3.

Новые значения SW2 и SW3. Обычное значение SW1. Обычное значение SW2 и SW3. Временное хранилище

16. Пусть г - количество членов многочлена (М). Для выполнения этой подпрогра.ммы потребуется 21рг + 38г + 29 + 27 Е +18 Е " + 27 Е Р + 8 Е условных единиц времени, где суммирование проводится по соответствующим величинам во время г активизаций программы А. Количество членов многочлена (Q) возрастает пар-т при каждой активизации программы А. Для вполне разумного предположения т = О и р = ар, где О < а < 1, получим, что соответствующие суммы равны О, (1 - а)рг, арг и rqo + ap{r(r - 1)/2), где qo есть значение q во время первой итерации Общая сумма равна 4арг + 40рг + 4арг + 8qor + 38г -t- 29. Из анашиза следует, что в многочлене (М) желательно и.меть меньше членов, чем в многочлене (Р), так как при этом в многочлене (Q) придется чаще пропускать члены, которым нет подобных. (Более быстрый гилгоритм описывается в упр. 5.2.3-29.)

17. На самом деле отличие невелико: операции сложения и умножения для списков любого типа будут практически одинаковы. По-видимому, преимущество циклического списка заметно проявится только при выполнении процедуры ERASE (см. упр. 13).

18. Пусть в поле связи узла х, содержится значение LOC(a;,+i) ®LOC(a:, i), где символ "ф" обозначает операцию "исключающее или", хотя здесь может использоваться любая другая обратимая операция, например сложение или вычитание по модулю размера поля связи. Для упрощения процедуры запуска в циклическом списке удобно использовать два смежных заголовка списка. (Происхождение этого хитроумного метода остается неизвестным.)

РАЗДЕЛ 2.2.5

1. Вставить Y слева: Р <= AVAIL; INFO(P) <- Y; LLINK (Р) <- Л; RLINK (Р) 4- LEFT; если LEFT / Л, то LLINK (LEFT) 4- Р, в противном случае RIGHT 4- Р: LEFT 4- Р. Установить Y в крайнее слева положение и удалить: если LEFT = Л, то UNDERFLOW; Р 4- LEFT; LEFT 4-RLINK(P), если LEFT = Л, то RIGHT 4- Л, в противном случае LLINK (LEFT) 4- Л, Y 4- INFO(P); AVAIL <t= P

2. Рассмотрим случай с несколькими последовательными удалениями с одного конца. После каждого удаления необходимо знать, какой элемент нужно удалить следующим. Поэтому связи в списке должны быть направлены от этого конца списка. При удалении с

обоих концов списка предполагается, что связи должны быть направлены в обе стороны. В то же время в упр. 2.2.4-18 описывается, как можно представить две связи с помощью одного поля связи Поступив подобным образом, можно организовать такие действия для дека общего типа.

3. Чтобы показать независимость переменной CALLUP от переменной CALLDOWN, заметьте, к примеру, что в табл. 1 лифт не останавливается на этаже 2 или 3 в моменты 0393-0444, хотя там его ожидают люди. Они нажали кнопку CALLDOWN, но если бы они нажали кнопку CALLUP, лифт остановился бы там

Чтобы показать независимость переменной CALLCAR от других переменных, обратите внимание на то, что в табл. 1, когда двери начинают открываться в момент 1378, лифт уже принял решение о движении вверх (GOINGUP). Eto состояние должно быть нейтральным (NEUTRAL) в этой точке, если CALLCAR [1] = CALLCAR [2] = CALLCAR [3] = CALLCAR [4] = О в соответствии с шагом Е2, но на самом деле для переменных CALLCAR [2] и CALLCAR [3] задано значение 1 пассажирами лифта 7 и 9. (Если вообразить ту же ситуацию, в которой номера всех этажей увеличены на единицу, состояние STATE = NEUTRAL или STATE = GOINGUP при открытых дверях лифта приведет к тому, что лифт, вероятно, продолжит движение вниз либо безусловно двинется вверх.)

4. Если десять или более человек выходит на одном этаже, состояние может оставаться нейтрашьным все это время; и когда шаг Е9 вызовет подпрограмму DECISION, это может привести к заданию нового состояния до того, как кто-то войдет в кабину лифта. На самом деле такое случается очень редко (и, несомненно, это было бы самое загадочное явление, которое автор наблюдаш во время экспериментов с лифтом.)

5. Со времени открытия дверей лифта в момент 1063 и до момента 1183, когда человек 7 вошел в него, состояние лифта нейтрашьно, так как никаких вызовов с этажа О не поступило и в кабине лифта никого нет. Тогда пользователь 7 установит CALLCAR [2] 4- 1, и состояние лифта соответственно станет равным GOINGUP.

6. Нужно добавить условие "если OUT < IN, то STATE / GOINGUP; если OUT > IN, то STATE / GOINGDOWN" к условию "FLOOR = IN" на шагах U2 и U4. На шаге Е4 следует взять пассажиров из очереди QUEUE [FLOOR] , если они направляются в ту же сторону, что и лифт; при этом лифт не должен находиться в нейтрашьном состоянии STATE = NEUTRAL, иначе будут взяты все пассажиры.

[В здании факультета математики в Станфорде установлен именно такой лифт, но его пользователи на самом деле не обращают никакого внимания на внешние индикаторы, т. е. они входят в кабину независимо от направления движения. Почему бы конструкторам лифта не учесть этот факт и определить логику работы лифта без переменных CALLUP и CALLDOWN? Тогда работа лифта в целом ускорилась бы, так как он не останавливался бы так часто.]

7. В строке 227 предполагается, что этот человек находится в списке WAIT. Переход к шагу U4A подтверждает, что такое предположение является верным. Предполагается, что значение GIVEUPTIME положительно и действительно равно 100 или даже больше.

8. Читателю предлагается самостоятельно изучить этот код.

577 Е8 DEC4 1

578 ENTA 61

279 JMP HOLDC

280 LDA CALL,4(3:5)

281 JAP IF

282 ENTl -2.4

283 JIZ 2F