и наоборот, нeoбxoмaя перестановка может быть получена с помощью следующего алгоритма: "Для j = 1, 2, ..., п будем вставлять столько элементов, сколько требуется (ни одного или более), де тех пор, пока в стеке не появится элемент Pj. Затем удалим элемент pj из стека". Этот алгоритм будет неверен, только если будет достигнуто значение j, для которого элемент pj находится не на верщине стека, а покрыт некоторым другим элементом р/ь, где к > j. Так как значения в стеке всегда монотонно возрастают, получим Pj < Рк- И элемент р/ь мог быть там, если бы он был меньще р, для некоторого г < j.

П. В. Раманан [SICOMP 13 (1984), 167-169] показал, как охарактеризовать перестановки, которые можно получить при работе со стеком при наличии тп дополнительных ячеек памяти. (Это удивительно сложное обобщение данной задачи.)

6. По определению очереди можно получить только тривиальную перестановку 12 ... п.

7. При работе с деком с ограниченным вводом для вывода первым элемента п необходимо вставить в очередь элементы 1, 2, ..., п во время первых п операций. А при работе с деком с ограниченным выводом для вывода первым элемента п во время первых п операций в очередь необходимо вставить элементы pip-i - - - Рп- Следовательно, ответы будут такими: (а) 4132, (Ь) 4213, (с) 4231.

8. При п < 4 не существует, а при п = Ъ существует четыре такие перестановки (см. упр. 13).

9. Выполняя с помощью дека с ограниченным выводом операции в обратном порядке для перестановки, полученной с помощью дека с ограниченным вводом, можно получить трижды обращенную перестановку. И наоборот, выполняя с помощью дека с ограниченным вводом операции в обратном порядке для перестановки, полученной с помощью дека с ограниченным выводом, можно также получить трижды обращенную перестановку. Это правило позволяет установить взаимно однозначное соответствие между двумя множествами перестановок.

10. (i) В допустимой последовательности должно быть п символов X и п символов S и Q вместе взятых, (ii) Количество символов X никогда не должно превышать общего количества символов S и Q при подсчете их слева направо, (iii) Всегда, когда количество символов X равняется общему количеству символов S и Q (при подсчете их слева направо), следующим должен быть символ Q. (iv) Две операции XQ никогда не должны выполняться одна за другой в таком порядке.

Необходимость правил (i) и (ii) очевидна. Дополнительные правила (iii) и (iv) добавлены во избежание двусмысленности, поскольку в пустой очереди операция S эквивалентна операции Q, а также потому, что последовательность действий XQ всегда можно заменить последовательностью QX. Таким образом, любая полученная последовательность соответствует по крайней мере одной допустимой последовательности.

Для того чтобы показать, как две разные допустимые последовательности приводят к разным перестановкам, рассмотрим последовательности, которые одинаковы вплоть до некоторой позиции. Например, в одной последовательности в этой позиции указано действие S, а в другой - действие X или Q. Согласно (iii), если очередь не пуста, в результате выполнения этих двух последовательностей действий будут получены разные перестановки (в отношении расположения элемента, вставленного при выполнении действия S). Другой возможный вариант заключается в том, что последовательности АиВ одинаковы вплоть, до некоторого действия, вслед за которым в А имеется действие Q, а в J5 - X. В таком случае в последовательности В после этого места также могут располагаться действия X, после которых согласно правилу (iv) не может быть символа Q, но согласно правилу (ii) должно следовать действие S. Поэтому перестановки будут разными.

11. По аналогии с упр. 4 допустим, что дпт является количеством частичных допустимых последовательностей длиной п, которые оставляют т элементов в деке и не заканчиваются символом X. Аналогично определяется hnm, но для тех последовательностей, которые заканчиваются символами X. Тогда 5(„+i)m " дпш-г) +iti(m-i)[Ti> 1] и hn+i)m = gn{m+i) + hn(m+i)- Задав G{x,z) и H{x,z) по аналогии с определениями из упр. 4, получим

z) = xz + 2xz + 4x2 + (8ж + 2ж)2 + (1бж + 8ж)2 + • • •; Н-(ж, 2) = 2 + 2ж2 + (4ж + 2)2 + (8ж + бж)2 + • • •.

Задав /1(2) = Я(0,2), получим 2"С(ж,2) = 2жС(ж, 2) + ж(Я(ж,2) - /1(2)) + ж, 2-Я(ж,2) = 2) + ж~(Я(ж,2) - /1(2)) и, наконец,

ж2(ж - 2 - xhiz))

G(X,2) =

ж - 2 - 2x2 + XZ

Как и в упр. 4, попытаемся выбрать /1(2) таким, чтобы заменить часть числителя и знаменатель множителем в более простом виде. Например, С(ж,2) = ж2/(1 - 2жг2(2)), где

Г2(2) = + 1 - (2 + 1)2 -822).

С учетом условия 6о = 1 искомая производящая функция будет равна

i (3 - 2 - v/1 - 62 -I- 22 ) = 1 -f- 2 -I- 22 -I- 62 -f- 222" + 902 -I- • • • .

Выполнив дифференцирование, найдем удобное для вычислений рекуррентное соотношение: п6„ = 3(2п - 3)6„-1 - (п - 3)6п-2, п > 2.

Другой способ решения этой задачи, предложенный В. Р. Праттом , заключается в использовании контекстно-свободных грамматик для набора строк (см. главу 10). Бесконечная грамматика с подстановками 5 -> д"(Вж)", В -> s(f{BxYB для всех п > О и В -> е является однозначной и позволяет подсчитать количество строк спх так же, как в упр. 2.3.4.4-31.

12. Согласно формуле Стирлинга а„ = 4"/\/7тЗ--0(4"п~). Для анализа Ь„ рассмотрим сначала общую задачу оценки коэффициента ш" в разложении в степенной ряд выражения л/1 - ш \/1 - olw, где (а < 1. Следовательно,

УГУГ=УГУ1-а + а(1-и;) = ч/Г )*( " ")*

где /3 = а/(1 - а), и искомый коэффициент равен (-1)"\/1~Е/ь()/3*(*"*"п)- Тогда

, ..п1к+\12\ Гп-к-Ъ12\ r(n-fc-l/2) (fc+1/2) ГГГТД М п >/ V п ) Г(п+1)Г(-Л-1/2)

и т.-*-1/2 = ;Lo [ ;*7/2!Jn-*-i/- t 3/2-m) огласно 1.2.11.1-(1б). Таким образом, получим асимптотическое разложение [ш"] \/\ - w\/\ - aw = соп" -I- сщ" + ••• + СтП-"-/+0(п-"-=/), где

Для Ьп запишем 1 -62-1-2 = (1 - (3-1-4/8)2)(1 - (3 - 4/8)2) и допустим, что w = (3-1-4/8)2, а = (3 - \/8)/(3 -I- \/8). Тогда асимптотическая формула будет иметь следующий вид:

(У2-1)(3 + ч/8)" 1 (V2 + l)"- 1 .

23/V1/2t,3/2 ll + tt" - 23/41/2„3/2 +

13. в. p. Пратт о6нару:!}сил, что перестановка невозможна тогда и только тогда, когда она содержит подпоследовательность с относительными значениями

5,2,7,4,...,4fc4-l,4fc-2,3,4fc,l или 5,2, 7,4,... ,4fc+3,4fc, 1,4fc+2,3

для некоторого к > 1, либо такая же перестановка, но в которой поменяли местами два последних элемента или элементы 1 и 2, или одновременно и то, и другое. Таким образом, для к = 1 запрещенными являются следующие перестановки: 52341, 52314, 51342, 51324, 5274163, 5274136, 5174263, 5174236. [STOC 5 (1973), 268-277.]

14. (Рещение предложено Р. Мелвиллом в 1980 году.) Пусть стеки Д и 5 расположены так, что очередь начинается с верхнего элемента стека R, продолжается до нижнего элемента стека R, а затем проходит от нижнего элемента к верхнему элементу стека 5. Если стек R пуст, то элементы стека 5 выталкиваются в стек R до полного опустощения стека 5. Для удаления элемента из начала очереди следует вытолкнуть верхний элемент стека R, который не будет опустощен до тех пор, пока не будет пустой вся очередь в целом. Для вставки элемента с конца очереди следует протолкнуть элемент в стек 5 (если только стек R не пуст). Для извлечения из очереди элемент следует по крайней мере дважды вытолкнуть и дважды протолкнуть.

РАЗДЕЛ 2.2.2

1. М - 1 (ко не М). Если допустить, что в очереди может находиться М элементов, как это предлагается в (6) и (7), то будет невозможно отличить пустую очередь от полной, проверяя только R и F, поскольку проверить можно будет только М состояний. Лучще пожертвовать одной ячейкой памяти, чем чрезмерно усложнить программу.

2. Вывод элемента с конца: если R = F, то UNDERFLOW, Y Ч- X[R]; если R = 1, то R Ч- М, в противном случае R ч- R - 1. Ввод элемента с начала: пусть X[F] i- Y; если F = 1, то F ч- М, в противном случае F Ч- F - 1; если F = R, то OVERFLOW.

3. (а) LD1 I; LDA BASE,7:1. Для этого потребуется 5 тактов вместо 4 или 8, как в (8).

(b) Решение 1. LDA BASE,2:7, причем для всех базовых адресов Ii = О, 12 = 1. Решение 2. Если необходимо, чтобы для базовых адресов выполнялось условие Ii = I2 = О, то можно записать LDA Х2,7:1, где в ячейке Х2 содержится NOP BASE,2:7. Во втором рещений потребуется выполнить на один такт больще, но в таком случае базовая таблица сможет использоваться с любыми значениями индексных регистров.

(c) Это эквивалентно LD4 Х(0:2), и для ее выполнения потребуется столько же времени, но регистр г14 будет содержать значение Ч-О, тогда как Х(0:2) содержит -0.

4. (а) NOP ».7 (Ь) LDA Х,7:7(0:2). (с) Это невозможно Код LDA Y,7:7, в котором по адресу Y содержится NOP Х,7:7, нарушает ограничение, накладываемое на поле 7:7 (см. упр. 5). (d) LDA Х,7:1 с дополнительными константами

X NOP »+1,7:2 NOP .+1.7:3 NOP .+1.7:4 NOP 0,5:6

Время выполнения равняется 6 тактам, (е) INC6 Х.7:6, где X содержит NOP 0.6:6.

5. (а) Рассмотрим команду ENTA 1000.7:7 с конфигурацией памяти

Ячейка ADDRESS I1 I2

1000. 1001 7 7

1001: 1004 7 1

1002: 1002 2 2