LEFT

PIVOTSTEP SI

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

15. Пусть гП = PIVOT, J, rI2 = РО, rI3 = QO, rI4 = P, rI5 н P1,X; LOC (BASEROW [t]) =BROW + i; LOC (BASECOL [j]) = BCOL + j, PTR[j] = BCOL + j (1:3).

01 02 08 04 05 06 07 08 09 10 11 12 13 Ц

15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33

35 36 37 38 39 40 41 42 43 44 45

S4A S4

EQU 0:3

EQU 4:5

EQU 0:3

EQU 4:5

EQU 1:3

STJ 9F

LD2 0,1(ROW)

ST2 10

LD3 1,1(COL)

ST3 JO

LDA =1.0=

FDIV 2,1

STA ALPHA

LDA =1.0=

STA 2,1

ENT2 BROW,2

ENT3 BC0L,3

JMP S2

ENTA BCOL.l

STA BCOL,1(PTR)

LDA 2,2

FMUL ALPHA

STA 2.2

LD2 1,2(LEFT)

LDI 1,2(COL)

JINN 2B

CMP4

0,3(UP) 0.3(ROW)

loss

I(ROW) ENT4 BROW.4 LD5 1,4(LEFT) 1,2(LEFT) 1,2(COL) JO 34 0,1 2

LD2 LDI CMPl JE

ENTA SLA JINN LDAN 2,3 FMUL ALPHA STA 2,3 JMP S3

Вход в подпрограмму, rll = PItfOT. SJ. Инициализация. 10 <- ROW(PIVOT).

JO 4- COL(PIVOT). Константа 1.

ALPHA 4- 1/VAL(PIVOT).

VAL(PIVOT) 4- 1

PO 4- LOC (BASEROW [10]).

QO 4- LOC(BASECOL[JO]).

PTR[J] 4- LOC (BASECOL [J]).

VAL(PO) ALPHA X VAL(PO).

52. Обработка осевой строки. PO 4- LEFT(PO). J4- COL(PO).

Если J > 0, обработать J

53. Поиск новой строки. QO 4- UP(QO). rI4 4- ROW(qo).

Если rI4 < 0, выйти.

Если rI4 = 10, повторить. I 4- rI4.

P 4-LOC (BASEROW [I]). PI 4- LEFT(P)

S4. Поиск нового столбца J 4- COL(PO).

PO 4- LEFT(PO).

Если J = JO, повторить.

r.4(0 3) <r- J.

Если J < 0,

установить VAL(QO) 4-

- ALPHA X VAL(QO).

Замечание. Используя соглашения из главы 4, строки 71-74 можно переписать так: LDA 2.3; FHUL 2,2; FCMP 2,5; JE S8; STA TEMP; LDA 2.5; FSUB TEMP (с параметром EPSILON в ячейке памяти 0).

17. Чтобы получить строку г матрицы С, нужно сложить к-е строки матрицы В, умноженные на элементы А [г, Л], такие, что А [г, А:] / 0. Для этого следует организовать связи между столбцами COL матрицы С, а связи ROW будут поддерживаться автоматически. [А. Schoor, Inf. Proc. Letters 15 (1982), 87-89.]

18. Трижды выполнив осевое преобразование в столбцах 3, 1, 2 соответственно, получим

После заключительных перестановок получим следующий ответ:

/1 -2 1\

-2 1/

20. ао =L0C(A[1,1]) - 3, aj = 1 либо 2, aj = 3-ai.

21. Например, М <- max(I, J), LOC(A[I,J]) = L0C(A[1,1]) + M(M - 1) + I - J. (Совершенно независимо было предложено сразу несколько таких формул. А, Л. Розенберг и X. Р. Стронг предложили следующее А;-мерное обобщение: LOC(A[Ii, ... Д*]) = L/t, где

Ll =L0C(A[1 1])+I,-1, Lt =Lr-i + (Mr-Ir)(Mr-(Mr-l)"")HMr = max(Ii,..., Ir)

[IBM Tech. Disclosure Bull. 14 (1972), 3026-3028]. Другие подобные результаты приводятся в Current Tirends in Programming Methodology 4 (Prentice-Hall, 1978), 263-311.)

22. С помощью комбинаторных обозначений (упр. 1.2.6-56) можно записать

«2 +----hik + k-

[Det Kongelige Norske Videnskabers Selskabs Forhandlinger 34 (1961), 8-9.]

23. Пусть c[ J] = LOC (A [0, J]) = LOC (A [0.0]) + m J, где m - количество строк в матрице в момент увеличения количества столбцов J на единицу; анашогично пусть г[1] = LOC(A [1,0]) = LOC (А [0,0]) -l-nl, где п - количество столбцов в матрице в момент увеличения количества строк I. Тогда функция размещения может иметь следующий вид:

LOC(A

[Ij]) Г 1 + Ф], если c[J] > г[1];

\ J -Ь г[1] в противном случае.

Нетрудно доказать, что c[j] > r[l] влечет c[J] > r[l] + J, а c[J] < r[l] влечет c[J] + I < r[l]; следовательно, соотношение

LOC(A[I,J]) = max(H-LOC(A[0,J]), J-f LOC(A[I,0]))

также будет выполняться. При этом необязательно накладывать ограничения на последовательное выделение тп ячеек. Единственное ограничение заключается в том, что при росте матрицы нужно последовательно расположить m или п новых ячеек по адресам, большим, чем адреса ранее использованных ячеек. Эта конструкция принадлежит Э. Дж. Оту и Т. X. Мерретту [Е. J. Otoo and Т. Н. Merrett, Computing 31 (1983), 1-9], которые также обобщили данный результат для к измерений.

24. [См. А. F. Aho, J. Е. Hopcroft, and UUman J. D., Tiie Design and Analysis of Computer Algorithms (Addison-Wesley, 1974), exercise 2.12.] Помимо массива A, следует организовать проверочный массив V такого же размера и список L использованных ячеек памяти. Пусть п - количество элементов в списке L. В исходном состоянии п = О и содержимое L, А и V может быть произвольным. При каждой попытке доступа к элементу А [А;] для А;,