1003: 1001 1 1 1004: 1005 1 7 1005: 1006 1 7 1006: 1008 7 7 1007: 1002 7 1 1008: 1003 7 2

и с rll = 1, rI2 = 2. Найдем 1000,7,7 = 1001,7,7,7 = 1004,7,1,7,7 = 1005,1,7,1,7,7 = 1006,7,1,7,7 = 1008,7,7,1,7,7 = 1003,7,2,7,1,7,7 = 1001,1,1,2,7,1,7,7 = 1002,1,2,7,1,7,7 = 1003,2,7,1,7,7 = 1005,7,1,7,7 = 1006,1,7,1,7,7 = 1007,7,1,7,7 = 1002,7,1,1,7,7 = 1002,2,2,1,1,7,7 = 1004,2,1,1,7,7 = 1006,1,1,7,7 = 1007,1,7,7 = 1008,7,7 = 1003,7,2,7 = 1001,1,1,2,7 = 1002,1,2,7 = 1003,2,7 = 1005,7 = 1006,1,7 = 1007,7 = 1002,7,1 = 1002,2,2,1 = 1004,2,1 = 1006,1 = 1007. (Более быстрый способ выполнения этих выкладок вручную заключается в последовательной оценке адресов, указанных в позициях 1002, 1003, 1007, 1008, 1005, 1006, 1004, 1001, 1000 в этом порядке. Но компьютеру, очевидно, придется выполнить эту же оценку именно в заданном порядке.) Автор попытался применить несколько необычных схем изменения содержимого памяти во время оценки адреса с полным восстановлением исходного состояния после вычисления окончательного адреса. Аналогичные алгоритмы рассматриваются в разделе 2.3.5. Однако эти попытки были бесплодными и, похоже, для сохранения всей необходимой информации просто не хватит места.

(Ь, с) Пусть Н и С являются вспомогательными регистрами, а N - счетчик. Для получения адреса М для команды в ячейке L необходимо сделать следующее.

А1. [Инициализация.] Установить Н 4- О, С L, N 4- 0. (В этом алгоритме С является "текущей" ячейкой, Н используется для сложения содержимого различных индексных регистров, а N является мерой глубины косвенной адресации.)

А2. [Проверка адреса.] Установить М ADDRESS (С). Если Ii(C) = J, 1 < J < 6, то М <- М + rlj. Если 12 (С) = j, 1 < j < б, то Н <- Н -I- rlj. Если Ii (С) = I2 (С) = 7, то N<-N + l, Н<-0.

A3. [Косвенная адресация?] Если Ii(C) или 12(C) равно 7, то С 4- М, и перейти к шагу А2. В противном случае М М -I- Н, Н 4- 0.

А4. [Сокращение глубины.] Если N > О, то С 4- М, N 4- N - 1, и перейти к шагу А2. В противном случае М является искомым значением.

Этот алгоритм можно корректно использовать в любой ситуации, за исключением случаев, когда Ii = 7и1<12<би когда во время оценки адреса в поле ADDRESS возникает случай II = I2 = 7. Результат будет таков, как если бы значение I2 было равно нулю. Для разъяснения принципа действия алгоритма А рассмотрим принятые в п. (а) обозначения. Состояние L,7,1,2,5,2,7,7,7,7 представляется с помощью С или М = L, N = 4 (количество замыкающих семерок) и Н = гИ-I-г12-I-г15 + г12 (постндексирование). В решении для п. (Ь) этого упражнения значение счетчика N всегда будет равно либо О, либо 1.

6. (с) приведет к переполнению (OVERFLOW), (е) приведет к недостатку (UNDERFLOW), а если выполнение программы будет продолжено, то в дальнейшем приведет к переполнению (OVERFLOW) для заключительного I2.

7. Нет, так как ТОР [г] должно быть больше, чем OLDTOP [г].

8. При работе со стеком полезная информация вставляется или удаляется с одной стороны, а свободная позиция-с другой:

А ВС

Здесь А = BASE [j] , В = ТОР£j] , С = BASE Lj + 1]. При работе с очередью или деком полезная информация вставляется или удаляется на концах, а свободная позиция в середине:

А В CD

Или наоборот: информация вставляется или удаляется в середине, а свободное место - на концах:

АС В D

Здесь А - BASE[j], В = REAREj] , С = FRONT [j], D = BASE[j -i-1]. Для непустой очереди эти два случая отличаются условиями В < С и В > С соответственно. Или, если известно, что очередь не переполнена, эти условия будут иметь вид В < С и В > С соответственно. Очевидно, что алгоритмы необходимо модифицировать таким образом, чтобы можно было расширять или сокращать пустые промежутки. (Таким образом, в случае переполнения, когда В = С, свободное пространство между В и С можно создать, перемещая только одну часть, а не обе сразу.) При вычислении SUM и D[j] на шаге G2 следует учесть, что каждая очередь занимает на одну ячейку больше, чем ей действительно требуется (см. упр. 1).

9. Для любой заданной последовательности действий а\,а2, ,ат для каждой пары {j, к), где j < к aa-i > ак, необходима одна операция перемещения, (Такая пара называется инверсией (inversion); см. раздел 5.1.1.) Следовательно, количество таких пар и является количеством необходимых перемещений. Теперь представим все п" записанных действий и для каждой из () пар (j,k) с j < к подсчитаем количество пар, для которых а > ак-Очевидно, что оно равно (j), т. е. количеству вариантов выбора и а*,, умноженному на п"~, или количеству способов заполнения остальных мест. Значит, общее количество перемещений равно Для получения среднего количества перемещений, т. е.

формулы (14), эту величину нужно разделить на п"".

10. Используя такой же метод подсчета, как в упр. 9, получим

(з) Е № = (")((Р.+ -+Рп)-(Р? + ---+Р))

l<j<*:<n

В данной модели эта величина абсолютно не зависит от относительного расположения списков! (Поразмыслив, можно понять, почему это так: если рассмотреть все возможные перестановки заданной последовательности ai,... ,ат, можно обнаружить, что общее количество перемещений для всех перестановок зависит только от количества пар различных элементов Oj ф Ок.)

11. Вычисляя среднее количество перемещений, как и прежде, получим

0<s<m г>(

Здесь S представляет j - 1 в обозначениях из предыдущего ответа, а г - количество элементов последовательности ai,аг,...,а, которое равно Uj. Эту формулу можно упрощать с помощью ее производящих функций до тех пор, пока

1 ft-l + k\fm-t-k\f 1\*+1

Существует ли более простой способ решения этой задачи? По-видимому, нет, поскольку производящая функция для заданных тг и i выглядит так.

h ~ 2п {l-zr\n-{n-l)zJ

12. Если т = 2к, среднее значение равно 2~*, умноженному на

и эта сумма равна

Аналогичный аргумент можно использовать для т = 2к + 1. Ответ в этом случае будет таким:

тп тп

2 2

13. А. Ч Яо доказал, что

{[т/2\)-

Emax(fci,fc2) = \т + (27г(1 - 2р)У+ O{m-{logmf)

для больших т при р < . [SICOMP 10 (1981), 398-403.] А Ф. П. М. Флажоле расширил этот анализ, в частности показав, что среднее количество асимптотически стремится к am прир= , где

ly sin{n/2)cosHn/2) Q g53 g33

п>1

Более того, при р > окончательное распределение величины ki стремится к равномерному при т -> оо, так что Emax(fci, fca) ~ fm. [См. Lecture Notes in Сотр. Sci. 233 (1986), 325-340.]

14. Пусть kj = n/m + -пху (Эта идея принадлежит Н. Г. де Брейну.) По формуле Стирлинга получим

= (ч/2)-"п"/= ( + max(xb ..., х„))

X exp (-(х? + . . + 4)) (v)- (1 + о(-)) ,

где к\-\-----\-кп = m и значения х равномерно ограничены Их сумма по всем неотрицательным значениям к\,... ,кп, которые удовлетворяют этим условиям, является приближением интеграла Римана. А ее асимптотическое приближение будет равно an(m/n)--Cn\/m-l-0(l)i где

а„ = (ч/2)-"п"/=/ expf-(x? + -- + x)) dx2...dx„,

с„ = (\/27г)~"тг"/ тах(ж1,--,2:п)ехр (-(ж?-!--•--Ьж)) д.хг...д.Хп,