Замечание. Если отнощения 9 Ч 1 и 6 Ч 9 добавить к исходным данным (18), то эта программа найдет петлю и напечатает ее в виде 9, 6, 8, 5, 9.

26. Одно из рещений может включать две следующие стадии.

Стадия 1. (Таблица X используется, как последовательный стек, по мере того как применяются обозначения В = 1 или 2 для каждой используемой подпрограммы.)

АО. Для 1 < J < N установить B(X[J]) ч- В (X [J] ) -- 2, если B(X[J]) < 0.

Al. Если N = О, перейти к стадии 2; в противном случае установить Р ч- X[N] и уменьшить N на 1.

А2. Если В(Р) I = 1, перейти к шагу А1; в противном случае установить Р ч- Р -Ь 1. A3. Если В (SUB1 (Р)) < О, установить N <- N -Ц, В (SUB1 (Р)) <- В (SUB1 (Р)) -Ь 2, X [N] <-

SUBl(P). Если SUB2(P) О и B(SUB2(P)) < О, выполнить аналогичные действия с

SUB2 (Р). Перейти к шагу А2. Стадия 2. (Проход по таблице и перераспределение памяти.)

81. Установить Р ч- FIRST.

82. Есяи Р = Л, установить N <- N -Ь 1, BASE(LOC(X[N])) <- MLOC, SUB(LOC(X [N])) <r- О и завершить выполнение алгоритма.

83. Если В(Р) > О, установить N4-N-i-1, BASE(LOC(X[N])) <-MLOC, SUB(LOC(X[N])) <-Р, MLOC i- MLOC -i- SPACE (P).

B4. Установить P <- LINK(P) и вернуться к шагу В2.

27. Читателю предлагается самостоятельно изучить приведенный ниже код.

INCA STA ST3 9H LD3 J3Z LDA JAP INCl INCA STA ST3 JMP

0,3(B) X,l

0,2(SUB2) A2

0,3(B) A2 1. 2

0,3(3)

Bl ENT2 FIRST

LDA MLOC

JMP IF B3 LDX 0,2(B)

JXNP B4

INCl 1

ST2 X.KSUB) ADD 0,2(SPACE) IH STA X+l,1(BASE) B4 LD2 0.2(LINK) B2 J2NZ B3

STZ X+l. 1 (SUB)

28. Предложим здесь лишь несколько комментариев, имеющих отношение к "военной игре". Пусть А - игрок с тремя фишками, которые расположены в узлах А13, а В - другой игрок. В этой игре А должен "захватить" В, но если В сможет дважды вызвать повторение одного и того же состояния, он выиграет. Однако для того, чтобы не хранить сведения обо всей предыстории игры в виде набора всех состояний, следует изменить алгоритм. Отметим состояния 157-4, 789-В и 359-6, в которых очередь следующего хода принадлежит игроку В, как "проигрышные" и применим предложенный алгоритм. Теперь основная выигрышная стратегия для игрока А заключается в перемещении только в проигрышные для В состояния. Но игроку А также нужно учитывать некоторые моменты, чтобы предыдущие ходы не повторялись. В хорошей игровой программе для выбора одного из нескольких возможных выигрышных вариантов следует использовать генератор случайных чисел. Итак, очевидным методом решения этой задачи с выигрышем для игрока А является всего лишь случайный перебор вариантов, которые ведут к проигрышному для игрока В состоянию Однако существует несколько интересных ситуаций, которые могут эту, на первый взгляд, благовидную процедуру привести к неудачному исходу! Рассмотрим, например, состояние 258-7 со следующим ходом игрока А, которое является выигрышным. Из состояния 258-7 игрок А может попытаться выполнить ход в состояние 158-7 (которое согласно этому алгоритму является проигрышным для игрока В). Но если игрок В сделает ход 158-В и вынудит игрока А сыграть 258-В, после которого игрок В снова сыграет 258-7, то игрок В выиграет, так как повторилось предыдущее состояние В этом примере показано, что алгоритм должен повторно вызываться после каждого хода, начиная с каждого состояния, которое прежде было отмечено как "проигрышное" (если ход предстоит сделать игроку А) или "выигрышное" (если ход предстоит сделать игроку В). "Военная игра" вполне подходит для создания удовлетворительной демонстрационной программы.

29. (а) Если FIRST = Л, то ничего делать не надо, в противном случае установите Р <- FIRST, а затем несколько раз (если вообще это потребуется) повторно устанавливайте Р <- LINK(P) до тех пор, пока LINK(P) = Л. Наконец установите LINK(P) <- AVAIL и AVAIL <- FIRST (и, вероятно, также FIRST Л). (Ь) Если F = Л, ничего не делать; в противном случае LINK(R) <- AVAIL и AVAIL <- F (и, вероятно, также F Л, R LOC(F)).

30. Для вставки следует установить Р AVAIL, INFO(P) Y, LINK(P) 4r- Л; если F = Л, то F Р, иначе - LINK(R) Р и R Р. Для удаления следует выполнить (9) с F вместо Т. (Хотя неопределенное значение R удобно использовать для пустой очереди, это может привести к путанице в работе алгоритма сборки мусора из упр. 6.)

Доска для "военной игры".

РАЗДЕЛ 2.2.4

1. Нисколько, во всяком случае даже затрудняет. (Указанное условие будет не совсем соответствовать идеологицциклических списков, если не допустить, что узел NODE(LOC(PTR)) является заголовком списка.)

2. Состояние до выполнения конкатенации:

PTRi PTR2

Состояние после выполнения конкатенации:

PTRi

PTR2

3. Если PTRi = PTR2, единственным результатом операции будет PTR2 *- Л. Если PTRi ф PTR2, то обмен значениями связей приведет к разбиению списка на две части точно так, как удашение двух разных точек из окружности приводит к ее разбиению на две дуги. Во второй части этой операции указатель PTRi будет направлен на циклический список из узлов, которые следовашо бы пройти, если бы в исходном списке последовательность связей была направлена от PTRi к PTR2.

4. Пусть HEAD является адресом заголовка списка. Для проташкивания элемента Y в стек необходимо вьшолнить следующие действия: установить Р AVAIL, INFO(P) 4- Y, LINK(P) 4- LINK (HEAD), LINK (HEAD) 4- P. Для выталкивания из стека элемента данных Y необходимо выполнить следующие действия: если LINK (HEAD) = HEAD, то UNDERFLOW; в противном случае установить Р 4- LINK (HEAD), LINK (HEAD) 4- LINK(P), Y 4- INFO(P), AVAIL <J= P.

5. (Cp. с упр. 2.2.3-7.) Установить Q 4- Л, P 4- PTR и повторять R 4- Q, Q 4- P, P 4- LINK(Q), LINK(Q) 4- R до тех пор, пока Р / Л . (Затем установить Q = PTR.)

-3 -4-

7. При таком расположении поиск подобных членов может быть выполнен за счет одного прохода, а потому исключается необходимость повторного выполнения операций поиска произвольных элементов. Кроме того, расположение членов в порядке возрастания было бы несовместимо с меткой конца "-1".

8. При удашении узла или вставке нового узла перед ним необходимо знать, какой узел указывает на текущий узел. Однако для этого можно использовать и ашьтернативные способы. Узел NODE(Q) можно было бы удалить, задав Q2 4- LINK(Q) и NODE(Q) 4- N0DE(Q2), AVAIL <J= Q2. Узел N0DE(Q2) можно было бы вставить перед NODE(Q), заменив значения N0DE(Q2) 4 NODE(Q) и задав LINK(Q) 4- Q2, Q 4- Q2. Благодаря таким искусным уловкам можно выполнить удашение и вставку, даже не зная, какой узел связан с узлом NODE(Q). Они использовашись в ранних версиях языка IPL. Недостатком этого способа является то, что метка конца многочлена иногда может смещаться, а другие переменные связи могут быть связаны с ней.

9. Алгоритм А с Р = Q просто удвоит многочлен (Q). Впрочем, как и следовало ожидать, за исключением случая, когда COEF = О для некоторого члена с ABC > 0. Тогда он