6. Обозначения в пп (Ь) h*{d), но не в п. (а)! CARD является узлом, а не связью с узлом,

7. Вариант (а) дает значение NEXT(LOC(TOP)), которое в данном случае идентично значению ТОР; правильным является вариант (Ь), Повода для путаницы здесь нет Рассмотрим аналогичный пример, когда X является числовым значением: для занесения значения X в регистр А запишем LDA X, а не ENTA X, поскольку в последнем случае в регистр будет занесено значение LOC(X),

8. Пусть гА = N, гП = X,

ENTA О В1. N О,

LD1 ТОР X <- ТОР,

J1Z .+4 В2 Верно ли, что

9. Пусть г12 = X,

PRINTER EQU 18

EQU 1:1

EQU 4:5

EQU 0:5

ALF PILE

ALF EMPTY

ORIG PBUF+24

LD2 TOP

J2Z 2F

IH LDA 0,2(TAG)

ENTl PBUF

JBUS .(PRINTER)

JAZ »+3

X = A?

INCA 1

LDI 0,1(NEXT) JINZ .-2

N-f-1, NEXT(X).

TAG NEXT NAME PBUF

BEGIN

DONE PAREN

MOVE

MOVE

J2NZ

PAREN(3) *+2

BLANKS(3) 1,2(NAME) PBUF+1 0,2(NEXT) PBUF(PRINTER) IB ,

BLANKS ALF ALF ALF

Номер построчно печатающего устройства.

Определение полей.

Сообщение, которое печатается, если колода пуста.

Пусть X 4- ТОР. Колода пуста? гА TAG(X).

Приготовиться к выполнению команды MOVE. Дождаться готовности принтера. Верно ли, что TAG = О

(обращена ли карта лицом вверх)? Нет- копировать скобки.

Да: копировать пробелы. гА NAME(X).

Пусть X NEXT(X). Печатать строку.

Если X / Л, повторить цикл печати.

РАЗДЕЛ 2.2.1

1. Да. (Если элементы дека всегда будут вставляться с одного из двух его концов.)

2. Для получения перестановки 325641 нужно выполнить последовательность действий SSSXXSSXSXXX (согласно обозначениям из следующего упражнения). Перестановка 154623 не может быть получена, поскольку вагон 2 мо*ет предшествовать вагону 3 только в том случае, если он будет выведен из стека до вставки вагона 3.

3. Допустимой является такая последовательность, в которой количество действий X никогда не превышает количества действий S при их считывании слева направо.

Две разные допустимые последовательности действий должны давать разные результаты, так как если две последовательности совпадают вплоть до некоторой позиции, в которой одна последовательцрсть содержит действие S, а другая - X, то последняя последовательность выведет некий символ, который в первой перестановке не может быть выведен из стека раньше символа, вставленного действием S из первой последовательности.

4. Эта задача эквивалентна многим другим интересным задачам, как, например, перечисление бинарных деревьев, подсчет количества способов вставки скобок в формулу, а также вычисление количества способов разбиения многоугольника на треугольники, и была впервые упомянута в 1759 году в записях Эйлера и фон Зегнера (см. раздел 2.3.4.6).

В приведенном ниже элегантном решении, принадлежащем А. Д. Андре (1878), используется принцип отражения (reflection principle). Очевидно, существует (") последовательностей действий, которые содержат по п действий S и X. Остается только оценить количество недопустимых последовательностей (т. е. последовательностей, в которых содержится корректное соотношение S и X, но нарушаются другие условия). В любой недопустимой последовательности отметим первый символ X частичной последовательности до символа X включительно, в которой количество символов X превышает количество символов S. Тогда в этой частичной последовательности заменим каждый символ X символом S, а символ S - символом X. В результате получим последовательность с {п + 1) символами S и (п - 1) символами X. И наоборот, для каждой последовательности последнего типа этот процесс можно выполнить в обратном направлении и найти недопустимую последовательность первого типа, которая приводит к ней. Например, из последовательности SSXSXXXXXSSS таким образом можно получить последовательность XXSXSSSXXSSS. Благодаря такому соответствию получаем, что количество недопустимых последовательностей равно (J"i)-Следовательно, о„ = {) - („Д).

Используя эту же идею, можно решить более общую "задачу об оценке результатов баллотировки по выборочным данным" (ballot problem) из теории вероятностей, которая заключается в подсчете всех частичных недопустимых последовательностей для заданного количества символов S и X. Эта задача была решена еще в 1708 году Авраамом де Му-авром, который показал, что количество последовательностей, содержащих I символов А и т символов В, а также по крайней мере одну исходную частичную строку, в которой символов А на п больше, чем символов В, равно f{l,m,n) = („„„(тТ-п))- частности, Qn - {) -/(п, п, 1), как показано выше. (Хотя де Муавр привел свой результат без доказательства [Philos. Trans. 27 (1711), 262-263], из контекста статьи ясно, что он знал доказательство, так как формула, очевидно, верна при I > т + п. Применяя его метод производящей функции для решения подобных задач, можно получить условие симметрии f{l,m,n) = f{m + n,l - п,п) с помощью простых алгебраических выкладок.) Последующая история проблемы, связанной с оценкой результатов баллотировки по выборочным данным, и ее некоторые обобщения приведены в исчерпывающем обзоре D. Е. Barton, С. L. Mallows, Annals of Math. Statistics 36 (1965), 236-260; см. также упр. 2.3.4.4-32 и раздел 5.1.4.

Теперь рассмотрим новый метод решения задачи об оценке результатов баллотировки по выборочным данным с помощью двойных производящих функций, поскольку этот метод подходит для решения более сложных задач, например такой, как в упр. 11.

Пусть упш - количество последовательностей действий S и X длиной п, в которых количество символов X превышает количество символов S, если считывать их слева направо, и в которых общее количество символов S на m больше, чем общее количество символов X. Тогда йп = 5(2n)o- Очевидно, ЧТО дпт равно нулю для четных значений т + п. Легко видеть, что для этих величин выполняются следующие рекуррентные соотношения:

д(п+1)т = дп(т-1) + дп(т+1), m > О, П > 0; дот = Som-

Рассмотрим двойную производящую функцию G{x,z) = Yin т Зптх"и допустим, что g{z) = G(0,2). Тогда приведенное выше рекуррентное соотношение эквивалентно равенству \

(x+\)Gix,z) = \g{z)+\{G(x,z)-l), т.е. G{x,z) =

К сожалению, оно не дает ничего нового в случае, когда ж = 0. Несмотря на это попробуем разложить знаменатель на множители 2(1 - ri(2)x)(l - г2(2)ж), где

П(г) = (1 + л/Г:4), г2(2) = (1-ч/Г).

(Обратите внимание на то, что п Ч-гг = I/2; пгг = 1.) Продолжим эвристический анализ этого соотношения. Необходимо найти такое 5(2), чтобы для G{x,z), заданного с помощью приведенной выше формулы, существовало бесконечное разложение в степенной ряд по х и 2. Для функции г2(2) существуст разложение в степенной ряд и г2(0) = 0. Более того, для фиксированного z при х = г2(2) знаменатель С(ж, 2) стремится к нулю. Таким образом, необходимо выбрать величину g{z) такой, чтобы числитель также стремился к нулю при X - T2{z). Иначе говоря, вероятно, следует выбрать zg{z) - г2(2). Благодаря сделанному выбору выражение для G{x, 2) упрощается:

71>0

Именно такое разложение в степенной ряд удовлетворяет исходному равенству, а потому можно сделать вывод, что вид функции g{z) был выбран верно.

Для решения данной задачи нужно найти коэффициенты 5(2). Действительно, в данном случае можно получить простое выражение для всех коэффициентов G{x, 2), применяя бином Ньютона:

Пусть ш = 2 и г2(2) = zf{w). Тогда, применяя обозначения из упр. 1.2.6-25, получим /(w) =Еа>о Ak{l,-2)w. Следовательно,

к>0

Тогда

Gix,z) = JAmin,-2)xZ""+\

и общее решение будет таким:

/ 2п-I-1 \ 2т-I-1 / 2п \ / 2п \ 5(2„)(2т) -[ ) - = U- mj"U-m-lj

/2п--2\ 2m--2 /271-1-14 / 27i-f-1 \ 5(2n+iK2m+i) = [ ) -- = In-mj - U-m-lJ-

5. Если j < /; и < р/ь, то элемент pj нужно удалить из стека до размещения в нем элемента рк- Если pj > Рк, то элемент Рк должен оставаться в стеке до размещения в нем элементаPj. Комбинируя эти два правила, получаем, что условие pj < рк < р, для i < j < к невыполнимо, так как оно означает, что элемент Pj нужно удгилить из стека до элемента рк и после элемента р,, однако р, следует после рк-