11. Пусть сначала LINK [А;] = О, 1 < А; < п, и HEAD = - 1. На шаге изменения V[A;3 следует сообщить об ошибке, если LINK [А;] / 0; в противном случае установить LINK [А;] 4-HEAD, HEAD 4- А; и определить для NEWV[A;] новые значения V[A;]. После каждого этапа

моделирования установить А; 4- HEAD, HEAD <--1 и несколько раз (или ни разу) выполнять

следующие действия до тех пор, пока не получим А; < 0: установить V[A;] 4- NEWVCA;], t 4- LINKCA;], LINK [A;] 4- 0, A; 4- «.

Ясно, что этот метод легко адаптируется для переменных, произвольным образом разбросанных в памяти, если включить поля NEWV и LINK в каждый узел переменной V.

12. В списке WAIT операции уашения выполняются слева направо, а операции вставки - справа нашево (так как поиск будет, скорее всего, выполнен именно с этой стороны). Кроме того, узлы удаляются из всех трех списков в нескольких местах, когда узел-предшественник и узел-наследник удаляемого узла неизвестны. Только список ELEVATOR можно преобразовать в односвязный список без сушественного снижения эффективности.

Замечание. В дискретном моделировании для сокрашения времени сортировки было бы предпочтительнее применить нелинейный список типа WAIT. В разделе 5.2.3 рассматривается обшая "проблема обработки очередей по приоритету или списков наподобие "наименьший входит-первый выходит". Известно несколько способов, в которых для вставки или удашения в списке п элементов потребуется выполнить только ©(log тг) операций, хотя такой причудливый способ вряд ли стоит применять для малых п.

РАЗДЕЛ 2.2.6

1. (Здесь индексы находятся в диапазоне от 1 до п, а не от О до п, как в (6).) LOC(A[J,K]) = LOC(A[0,0]) + 2nJ + 2К, где предполагается, что А[0,0] на самом деле не сушествует. Если установить J = K=1, получим LOG (А [1,1]) =LOC(A[0,0]) +2п+2, а потому ответ можно представить несколькими способами. Тот факт, что значение LOG (А [0,0]) может быть отрицательным, часто приводит к появлению ошибок в работе компиляторов и процедур загрузки.

2. LOC(A[Ii.....Ifc]) = LOC(A[0.....0]) + Ei<r</c «I- = LOC(A[Zi .....«*]) +

Ei<r</c arlr - Ei<r<t rlr, где ar = cn,<,<,t(w. -ls + 1).

Замечание. Обобшение для структур, которые встречаются в таких языках программирования, как с, и простой ашгоритм для вычисления соответствуюших констант можно найти в работе Р. Deuel, САСМ 9 (1966), 344-347.

3. 1 < к < j < п тогда и только тогда, когда 0<А; - l<j - 1<п - 1. Поэтому заменим к, j, п значениями к - I, j - I, п-1 соответственно во всех формулах для нижней границы, равной нулю.

4. LOC(A[J,K]) =LOC(A[0.0]) + nJ - J(J - 1)/2 + К.

5. Пусть АО = LOC(A[0,0]). Тогда сушествует по крайней мере два следующих решения (в которых предполагается, что J находится в регистре гП, а К -в регистре г12): (i) "LDA ТА2,1:7", где по адресу TA2+J хранится команда "NOP j+l*j/2+A0,2"; (ii) "LDA 01,7:2", где по адресу Cl хранится команда "NOP ТА,1:7", апо адресу TA+j-команда "NOP j+l*j/2+A0". В последнем случае потребуется выполнить на один цикл больше, но при этом таблица не будет связана с индексным регистром 2.

6. (а) LOC(A[I.J,K]) =LOC(A[0.0.0]) + 3 ) + (" 2 ) + (i) (b) LOC(B[I.J,K]) = LOC(B[0,0,0])

Следовательно, в данном случае можно получить анашогичное выражение для адреса произвольного элемента массива.

7. LOC(A[Ii. ... ,It]) =LOC(A[0,...,0]) + E Cl+kir) См. упр. 1.2.6-56.

1<г<*

8. (Решение П. Нэша.) Пусть элементы массива X[I,J,K] определены для О < I < п, 0<J<n+l, 0<К<п + 2. Тогда A[I,J,K] = X[I,J.K]; B[I,J,K] = X[J.I + l.K]; C[I,J,K] = X[I.K.J + 1]; D[I,J,K] =X[J,K,H-2]; E[I,J,K] = X[K,I + 1.J +1]; F[I,J,K] = X [K, J + 1,1 + 2] . Эта схема наиболее удобна, поскольку позволяет без накладок упаковать (п + 1){п + 2){п + Z) элементов шести тетраздрических массивов в последовательном

порядке. Доказательство. АиВ заполняют все ячейки XCi.j.fc] с А; = min(i, j, А;); С и D заполняют все ячейки с j = min(i, j, А;) / А;; Е и F заполняют все ячейки i = mm{i, j, к) / j, к.

(Данную схему можнолбобщить до m размерностей, если только потребуется упаковать т! элементов обобщённых тетраэдрических массивов с помощью (п + 1) х (п + 2)... (п + т) последовательных позиций. Для этого следует связать перестановку aia2...am с каждым массивом и сохранить его элементы в массиве Х[1о, + Bi, 1о2 + В2, ... Дот + Bml, где В1В2 Вт -таблица инверсии для aia2 . am, которая определена в упр. 5.1.1-7.)

9. G1. Задать для Р1, Р2, РЗ, Р4, Р5, Р6 значения, указывающие на первые ячейки списков FEMALE, А21, А22, А23, BLOND, BLUE соответственно. Положим в дальнейшем, что концом каждого списка является связь Л, которая гораздо меньше любой другой связи. Если Р6 = Л, прекратить выполнение ашгоритма (список, к сожалению, пуст).

G2. (Обход списков может выполняться по-разному, например сначала обрабатывается список EYES, затем - HAIR и AGE и наконец SEX.) Установить Р5 <- HAIR(P5) несколько раз, пока не выполнится условие Р5 < Р6 (если оно уже выполняется, это может и не потребоваться). Если теперь Р5 < Р6, перейти к шагу G5.

G3. Установить Р4 4- AGE(P4) и повторять это действие до тех пор, пока не выполнится условие Р4 < Р6. Аналогично выполнять те же действия для РЗ и Р2 до тех пор, пока не выполнятся условия РЗ < Р6 и Р2 < Р6. Если теперь Р4, РЗ и Р2 меньше, чем Р6, то перейти к шагу G5.

G4. Установить Р1 <- SEX(Pl) и повторять это действие до тех пор. пока не выполнится условие Р1 < Р6. Если Р1 = Р6, значит, узел с заданным описанием девушки найден и можно вывести его адрес, Р6. (Возраст можно определить с помощью указателей Р2, РЗ и Р4.)

G5. Установить P64-EYES(P6). Прекратить выполнение ашгоритма, если Р6 = Л; в противном случае вернуться к шагу G2. 1

В этом ашгоритме реализован интересный, но не лучший способ организации списка для выполнения подобного поиска.

10. См. раздел 6.5.

11. Не более 200 4- 200 -Н 3 • 4 • 200 = 2800 слов.

12. VAL(QO) = с, VAL(PO) = b/a, VAL(Pl) = d.

13. В поле, по которому упорядочен список, в конце каждого списка удобно иметь метку "меньший при сравнении". Простейший однонаправленный список можно было бы использовать, например, применив только связи LEFT в BASEROWCi] и связи UP в BASECOLCj] и изменив алгоритм S следующим образом. На шаге S2 проверить, верно ли, что РО = Л перед установкой J f- COL (РО), и, если верно, установить РО 4- LOC (BASEROW [10]) и перейти к шагу S3. На шаге S3 проверить, верно ли, что Q0 = Л, и, если верно, прекратить выполнение алгоритма. Шаг S4 следует изменить так же, как и шаг S2. На шаге S5 проверить, верно ли, что Р1 = Л, и, если верно, продолжить выполнение алгоритма, как если бы выполнялось условие COL(Pl) < 0. На шаге S6 проверить, верно ли, что UP(PTR[J]) = Л, и, если верно, продолжить выполнение ашгоритма, как если бы значение поля ROW было отрицательным.

Эти изменения усложняют алгоритм и не способствуют экономии памяти за исключением поля ROW или COL в заголовках списков (а при работе с компьютером MIX это вообще не дает никакой экономии).