AOP_Tom1 (1021736), страница 150
Текст из файла (страница 150)
8. Пусть гА ш М, гП щ Х. ЕИТА 0 В). М < — О. 101 ТОР Х +- ТОР. )12 а+4 В2. Верно ли, что Х = Л? 1ИСА 1 ВЗ. М е- И+ 1. 101 0,1(ИЕХТ) Х +- ИЕХТ(Х). )1ИХ ь-2 1 9. Пусть г12 ш Х. РВ1МТЕВ ТАС ИЕХТ МАМЕ РВОР Номер построчно печатающего устройства. Определение полей. Сообщение, которое печатается, если колода пуста.
ВЕС1И 1Н Да: копировать пробелы. гА +- МАНЕ(Х). Пусть Х +- МЕХТ(Х), Печатать строку. Если Х ~ Л, повторить цикл печати. 2Н СОМЕ РАНЕН ВСАМКБ РАЗДЕЛ 2.2.1 1. Да. (Если элементы дека всегда будут вставляться с одного из двух его концов.) 2. Для получения перестановки 325641 нужно выполнить последовательность действий оЯоХХББХЯХХХ (согласно обозначениям из следующею упражнения).
Перестановка 154623 не может быть получена, поскольку вагон 2 может предшествовать вагону 3 только в том случае, если он будет выведен из стека до вставки вагона 3. 3. Допустимой является такая последовательность, в которой количество действий Х никогда не превышает количества действий Я при их считывании слева направо. ЕОО 18 ЕРО 1:1 ЕОО 4:Б ЕОО 0:Б АЬР Р11Е АСР ЕМРТТ ОВТС РВОР+24 102 ТОР 122 2Р ЬОА 0,2(ТАС) ЕИТ1 РВОМ )ВНБ е(РЕ1МТЕВ) )АХ а+3 ИОЧЕ РАВЕН(3) Л(Р а+2 МОЧЕ ВСАМКБ(3) ЬОА 1,2(МАМЕ) БТА РВОМ+1 102 0,2(МЕХТ) ООТ РВОМ(РВТМТЕВ) )2МХ 1В . Н1Т А1Р ( ААР АХР ) АСР Пусть Х +- ТОР. Колода пуста? гА <- ТАС(Х). Приготовиться к выполнению команды НОТЕ, Дождаться готовности принтера.
Верно ли, что ТАС = О (обращена ли карта лицом вверх)? Нет копировать скобки. Две разные допустимые последовательности действий должны давать разные результаты, так как если две последовательности совпадают вплоть до некоторой позиции, в которой одна последовательность содержит действие Я, а другая — Х, то последняя последовательность выведет некий сил»вол, который в первой перестановке не может быть выведен из стека раньше символа, вставленного действием Я из первой последовательности. 4. Эта задача эквивалентна многим другил» интересным задачам, как, например, перечисление бинарных деревьев, подсчет количества способов вставки скобок в формулу, а также вычисление количества способов разбиения многоугольника на треугольники, и была впервые упомянута в 1759 году в записях Эйлера и фон Беспера (см.
раздел 2.3.4.6). В приведенном ниже элегантном решении, принадлежащем А. Д. Ан,:ре (1878), используется принцип отражения (гейестюп рппс!р!е). Очевидно, существует (з") последовательностей действий, которые содержат по и действий Я и Х. Остается только оценить количество недопусшпммх последовательностей (т. е. последовательностей, в которых содержится корректное соотношение Б и Х, но нарушаются другие условия). В любой недопустимой последовательности отметим первый символ Х частичной последовательности до символа Х включительно, в которой количество символов Х превышает количество символов Б.
Тогда и этой частичной послеловательности заменим каждый символ Х символом Б, а символ Б— символом Х. В результате получим последовательность с (и+1) символами Я и (и — 1) символами Х. И наоборот, для каждой последовательности последнего типа этот процесс можно выполнить в обратном направлении и найти недопустимую последовательность первого типа, которая приводит к ней.
Например, из последовательности ЯЯХЯХХХХХБЯЯ таким образом можно получить последовательность ХХЯХЯБЯХХБЯЯ. Благодаря такому соответствию получаем, что количество недопустимых последовательностей равно („",). Следовательно, а„= ( ") — ( ",). Используя эту же идею, можно решить более общую "задачу об оценке результатов баллотировки по выборочным данным" (Ьа!!ос ргоЫеш) из теории вероятностей, которая заключается в подсчете всех частичных недопустимых последовательностей дяя заданного количества символов Я и Х.
Эта задача была решена еще в 1708 году Авраамом де Муавром, который показал, что количество последовательностей, содержащих ! символов А и пз символов В, а также по крайней мере одну исходную частичную строку, в которой символов А на и больше, чем символов В, равно 7"((,т,п) = (,„'»~, !). В частности, а„= („") — 7"(п,п,1), как показано выше.
(Хотя де Муавр привел свой Результат без доказательства [РЬ!!оз. 7?апа 27 (1711), 262 — 263), из контекста статьи ясно, что он знал доказательство, так как формула, очевидно, верна при ! > т+ и. Применяя его метод производящей функции для решения подобных задач, можно получить условие симметрии з*(1,го,п) = 7'(и»+ и,! — п,п) с помощью простых алгебраических выкладок.) последующая история проблемы, связанной с оценкой результатов баллотировки по выборочным данным, и ее некоторые обобщения приведены в исчерпывающем обзоре П. Е. Вагсоп, С.
Ь. Ма)!озгв, Алла!э оЕ МаВь БсабзВсз 36 (1965), 236 — 260; см. также упр. 2.3.4.4-32 и раздел 5.1.4. Т п р рассмотрим ~оный л»етод решения задачи об оценке зульта в б, лоти ки по выборочным данным с помощью двойных производящих функций, поскольку этот метод подходит для решения более сложных задач, например такой, как в упр.
11. Пусть д„— количество последовательностей действий Б и Х длиной и, в которых количество символов Х превышает количество символов Б, если считывать их слева направо, и в которых общее количество символов Б на т болыие, чем общее количество символов Х. Тогда а„= дщ„»о. Очевидно, что д равно нулю для четных значений т+и. Легко видеть, что для этих величин выполняются следующие рекуррентные соотношения: д!»П — — дщ П+дщ»чр т>0, п>0; до =бе И наоборот, необходил~ая перестановка может быть получена с помощью следующего алгоритма: "Для у = 1, 2, ..., п будем вставлять столько элементов, сколько требуется (ни одного или более), дй тех пор, пока в стеке не появится элемент рз.
Затем удалим элемент рз из стека". Этот алгоритм будет неверен, только если будет достигнуто значение у, для которого элемент рз находится не на вершине стека, а покрыт некоторым другим элементом рю где й > 11 Так как значения в стеке всегда монотонно возрастают, получим рз < ры И элемент рь мог быть там, если бы он был меньше р, для некоторого 1 < у. П. В. Раманан (31СОМР 13 (1984), 167-169) показал, как охарактеризовать перестановки, которые можно получить при работе со стеком при наличии ти дополнительных ячеек памяти.
(Это удивительно сложное обобщение данной задачи.) 6. По определению очереди можно получить только тривиальную перестановку 12... и. 7. При работе с деком с ограниченным вводом для вывода первым элемента и необходимо вставить в очередь элементы 1, 2,..., и во время первых и операций. А при работе с деком с ограниченным выводом для вывода первым элемента и во врал~я первых и операций в очередь необходимо вставить элементы р~ рз...
р„. Следовательно, ответы будут такими: (а) 4132, (Ь) 4213, (с) 4231. 8. При и < 4 не существует, а при и = 5 существует четыре такие перестановки (см. упр. 13). 9. Выполняя с помощью дека с ограниченным выводом операции в обратном порядке для перестановки, полученной с помощью дека с ограниченным вводом, можно получить трижды обращенную перестановку. И наоборот, выполняя с помощью дека с ограниченным вводом операции в обратном порядке для перестановки, полученной с помощью дека с ограниченным выводом, можно также получить трижды обращенную перестановку. Это правило позволяет установить взаимно однозначное соответствие между двумя множествами перестановок. 10.
(1) В допустимой последовательности должно быть и символов Х и п символов Я и (е вместе взятых. (8) Количество символов Х никогда не должно превышать общего количества символов Б и Я при подсчете их слева направо. (ш) Всегда, когда количество символов Х равняется общему количеству сил~волов Я и Я (при подсчете их слева направо), следующим должен быть символ Я.
(1ч) Две операции Хс) никогда не должны выполняться одна за другой в таком порядке. Необходимость' правил (1) и (й) очевидна. Дополнительные правила (91) и (1ч) добавлены во избежание двусмысленности, поскольку в пустой очереди операция Б эквивалентна операции ь), а также потому, что последовательность действий ХЯ всегда можно заменить последовательностью ЯХ. Таким образом, любая полученная последовательность соответствует по крайней мере одной допустимой последовательности. Для того чтобы показать, как две разные допустимые последовательности приводят к разным перестановкам, расслютрим последовательности, которые одинаковы вплоть до некоторой позиции.
Например,в одной последовательности в этой позиции указано действие Б, а в другой — действие Х или Я. Согласно (ш), если очередь не пуста, в результате выполнения этих двух последовательностей действий будут получены разные перестановки (в отношении расположения элемента, вставленного при выполнении действия Я). Другой возможный вариант заключается в том, что последовательности А и В одинаковы вплоть до некоторого действия, вслед за которым в А имеется действие Я, а в  — Х. В таком случае в последовательности В после этого места также могут располагаться действия Х, после которых согласно правилу (л) не может быть символа Я, но согласно правилу (й) должно следовать действие Я.
Поэтому перестановки будут разными. 11. По аналогии с упр. 4 допустим, что д„является количеством частичных допустимых последовательностей длиной и, которые оставляют ш элементов в деке и не заканчиваются символом Х. Аналогично оцределяется Ь„ж, но для тек последовательностей, которые заканчиеаютсл символами Х. Тогда д< з() = 2д < 0 + 6~< — 0[тп>1) и 6< +бы = дь< 0+6 < +1). Задав С(х,х) и Н(х,э) по аналогии с определениями из упр.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
