так как можно показать, что соответствующие суммы находятся в е-окрестности величин а„ и Сп для любого е.

Известно, что а„ ~ \, так как соответствующая сумма может быть оценена явно. Интеграл в выражении для Сп равен п1\, где

1 = Д+...+х„=0 1 Р (-?( + • • • + ")) • • • a:i>l2.....х„

Сделав подстановку

2:1 = (г/2Н-----ЬУп), Х2=Х1-у2, X3=Xl-J/3, Хп = Xl - Уп,

можно найти II = h/n, где

l2= [ (У2+-+Уп)ехр(-(1у2...с1уп,

•У2,.. .Vn>0

и Q = п(г/2 Н-----1- Уп) - (г/2 + • • • + Уп). Теперь из соображений симметрии получим, что

интеграл I2 равен умноженному на (п-1) тому же интегралу, в котором вместо (j/2+- • +Уп) выполнена подстановка значений у2. Следовательно, I2 = {п - 1)/з, где

3 = / {пу2-{у2 + --+Уп))ехр(-)(1у2...(1уп

= / 6Р(~%) dyi...dyn-

Jya, .уп>0

Здесь Qo равно Q, где j/2 заменены нулями. [Если тг = 2, то /з = 1.] Теперь допустим, что Zj = yj - (уз + • • • + Уп)/{\/2 + ), 3 < j < тп. Тогда Qo = z + • • + z, и можно вывести, что h = /4/п*"~з)/2

/4=/ expf-ii--±) dz3...dzn

•уз... ,Уг.>0 \ /

= а„у" ехр з + -+4 dz3...dzn = an(v)"-

Здесь Q„ - это отнощение "телесного угла" в (п - 2)-мерном пространстве, натянутом на векторы (п + ч/2п. О,..., 0) - (1,1,..., 1), (О, О,..., п + %/2п) - (1, !,...,!), к полному

телесному углу всего этого пространства. Следовательно,

(тг-1)у/ Сп = --п.

Получим аг = 1, Q3 = 5, а4 = тг" arctan л/2 и .304 и

13 1

as = - Н--arctan -;= я .206.

8 47Г \/8

[Хотя рещение этой задачи получено для сз (Robert М. Kozelka , Ляяа/s of Math. Stat. 27 (1956), 507-512), для более высоких значений тг оно, по-видимому, еще не опубликовано.]

16. Нет, если только на очереди не накладываются такие ограничения, при которых для них можно применить примитивный метод на основе правил (4) и (5).

17. Сначала следует показать, что всегда BASECjlg < BASE[j]i. Затем можно заметить, что каждое переполнение стека г в последовательности so{ct), которое необязательно является переполнением в последовательности Si((t), происходит тогда, когда стек i становится

больше, чем когда-либо ранее, однако его новый размер не меньше, чем исходный размер, выделенный для стека i в последовательности si((t).

18. Допустим, что затратьг«ремени на выполнение одной операции вставки равны а плюс bN + СП, если при этом необходимо выполнить переупаковку памяти, где JV - количество занятых ячеек. А затраты на одну операцию удаления равны d. Предположим, что после переупаковки памяти, в результате которой N ячеек остаются занятыми и S = М - N свободными, для каждой операции вставки до следующего перераспределения потребуется a + b+10c+10{b + c)nN/S = 0(1 + па/{1-а)), где а = N/M. Если р операций вставки и q операций удаления происходят до переупаковки памяти, то предполагаемые затраты равны p{a+b+\(ic+lQ{b+c)nNIS)+qd, тогда как реальные затраты составляют pa+6iV--cn--qd < pa +pb + bN + cn + qd. Они меньше предполагаемых затрат, потому что р > .IS/n. Наше предположение о том, что М > п означает, что cS/n + [b + c)JV > 6Л + cn.

19. Можно было бы просто уменьшить все индексы на единицу, но приведенное ниже решение выглядит несколько элегантнее. В исходном состоянии Т = F = R = 0.

Протолкнуть Y в стек X: если Т = М, то OVERFLOW; Х[Т] Y; Т Т -- 1.

Вытолкнуть Y из стека X: если Т = О, то UNDERFLOW; T(-T-l;Y-(-X[T].

Вставить Y в очередь X: X[R] Y; R (R -i- 1) modM; если R = F, то OVERFLOW.

Удалить Y из очереди X: если F = R, то UNDERFLOW; Y X[F]; F (F -Ь 1) modM. Как и прежде, Т-это количество элементов в стеке, а (R-F) mod М- количество элементов в очереди. Но самым верхним элементом стека теперь является X [Т - 1], а не X [Т].

Хотя специалистам в теории информатики почти всегда удобнее начинать отсчет с нуля, весь остальной мир вряд ли когда-нибудь перейдет к использованию нуль-индексирования. Что тут говорить, если даже Эдсгер Дейкстра при игре на фортепиано использует считалку "1-2-3-4 1-2-3-4"!

РАЗДЕЛ 2.2.3

1. Событие OVERFLOW неявно обрабатывается операцией Р

: AVAIL.

Приготовиться ко второму выходу.

Сохранить значение регистра rJ. Сохранить значение гП.

Установить для AVAIL новый адрес.

Увеличить POOLMAX.

Не исчерпан ли объем памяти?. Установить LINK (AVAIL) r- Л. Извлечь значение rJ. Отнять 2.

Сохранить адрес выхода. Восстановить гИ. Возврат. I

5. Вставка с начала очереди очень похожа на основную операцию вставки (8) с дополнительной проверкой опустошения очереди: Р < AVAIL, INFO(P) ч- Y, LINK(P) ч- F, если F = Л, то R ч- Р; F <- Р.

Для удаления элемента с конца очереди можно было бы найти узел, который связан с NODE (R), но данный метод крайне неэффективен, поскольку потребуется проследить весь путь от F. Это можно было бы выполнить так.

a) Если F = Л, то UNDERFLOW, в противном случае установить Р ч- LOC(F).

b) Если LINK(P) ф R, то установить Р ч- LINK(P) и повторять этот этап до тех пор, пока LINK(P) станет равным R.

c) Установить Y <- INFO(R), AVAIL < R, R ч- Р, LINK(P) <- Л.

6. Операцию LINK(P) <- Л можно было бы удалить из (14), если удалить команды F ч- LINK(P) и "если F = Л, то R ч- LOC(F)" из (17), а вместо последней из них вставить "если F = R, toF4-AhR4- LOC(F), в противном случае установить F ч- LINK(P)".

В результате таких изменений поле LINK конечного узла очереди будет содержать бесполезную информацию, которая никогда не будет использована программой Благодаря подобной уловке можно сократить время выполнения программы, что очень полезно на практике. Однако при этом нарушаются основные допущения, принятые для сборки мусора (см. раздел 2.3.5), и ее нельзя использовать в таких алгоритмах.

7. (Убедитесь, что в вашем решении учитывается возможность опустошения списка )

11. Установить Р ч- FIRST, Q ч- Л.

12. Если РА, установить R<-Q, Q<-P, P4-LINK(Q), LINK(Q) -R и повторить этот шаг.

13. Установить FIRST <- Q.

По сути, все узлы сначала удаляются (выталкиваются) из одного стека, а затем вставляются (проталкиваются) в другой стек.

8. LD1 FIRST 1

ENT2 О 1

J1Z 2F 1

1Н ENTA 0,2 п

ENT2 0.1 п

LD1 О,2(LINK) п

STA О,2(LINK) п

/L Р = гП <- FIRST. Q = rI2 ч- Л.

12. Если список пуст, выполнить переход. R = гА <- Q. Q ч- Р.

Р <-LINK(Q). LINK(Q) <- R.