AOP_Tom1 (1021736), страница 151
Текст из файла (страница 151)
4, получим С(х, х) = хх+ 2х 2 + 4хзхз+ (бх + 2х )з~+ (1бх + 8х )з + Н(х,э) = 2 + 2хх + (4х + 2)2 + (бх + бх)2 +. Задав Ь(з) = Н(0 2), получим 2 'С(х х) = 2хС(х,э) + х(Н(х х) — Ь(2)) + х, 2 'Н(х 2) = х 'С(х,э) + х 1(Н(х,х) — 6(2)) и, наконец, С(*,2) = хз(х — 2 — хб(з)) х — 2 — 2хзз + ххэ Как и в упр. 4, попытаемся выбрать 6(2) таким, чтобы заменить часть числителя и знаме- натель множителем в более простом виде.
Например, С(х, 2) = хх/(1 — 2хгэ(2)), где (*) = — ( '+) — б(*'+))'-б ') 42 С учетом условия 6э = 1 искомая производящая функция будет равна ((б — — Г- б ~) = + * 2 бг + бб бб~ + Выполнив дифференцирование, найдем удобное для вычислений рекуррентное соотношение: пЬ = 3(2п — 3)6 — ( — (и — 3)6„2, и > 2. Другой способ решения этой задачи, предложенный В. Р. Праттом, заключается в использовании контекстно-свободных грамматик для набора строк (см. главу 10). Весконечная грамматика с подстановками Я -4 д" (Вх)", В -э зд" (Вх)"э'В для всех и > 0 и В -4 е является однозначной и позволяет подсчитать количество строк с и х так же, как в упр, 2.3.4.4 — 31. 12. Согласно формуле Стирлинга а„= 4~/т/япз+С(4" и бб'). Для анализа 6 рассмотрим сначала общую задачу оценки коэффициента ш" в разложении в степенной ряд выражения т/1 — ш т/1 — пш, где (а~ < 1.
Следовательно, 'Т- )- =Л- Л- б (1- )- 'Т- 2 ( )б(1 — ) /1/2 1 ь ЗЗ(<2 где )3 = а/(1 — и), и искомый коэффициент равен ( — 1)" т/1 — а 2 д ( ~ ))э ( +„'< ). Тогда )=~ <4+1/2Т /и-6-3/2~ Г(и — 6-1/2) (<4+1/2) + ь 1)2 — ( )=( и ! '1 и ) Г(и+1) Г( — 6-1/2) т/яп я и и " '~ = 2', о ~ „ь,'2(~ ]и ь '(~ 1+ 0(п " ~)2 ) согласно 1.2.11.1 — (1б). Таким образом, получим асимптотическое разложение (ш"] т/Т вЂ” шб/1 — пш = сап + с(п + ...,, п---з,э+С(п---зт2) где Для 6„запишем 1 — 62+ зэ = (1 — (3+ 4/8)2)(1 — (3 — бб)8)з) и допустим, что ш = (3+ т/8)х, а = (3 — т/8)/(3 + т/8), Тогда асимптотическая формула будет иметь следующий вид( 6„(/' — 1)(3+ /8)" (, +С(„- )) ( "+')Зв '(1.„С(„- )) 23))4я1/2пз)2 22<4я1/Зле<2 13.
В. Р. Пратт обнаружил. что перестановка невозможна тогда и только тогда, когда она содержит подпоследовательность с относительными значениями 5,2,7,4,...,41+1,48-2,3,4А1 или 5,2,7,4,...,4А+3,45,1,45+2,3 для некоторого А > 1, либо такая же перестановка, но в которой поменяли местами два последних элемента или элементы 1 и 2, или одновременно и то, и другое. Таким образом, для А = 1 запрещенными являются следующие перестановки: 52341, 52314, 51342, 51324, 5274163, 5274136, 5174263, 5174236.
(АТОС 5 (1973), 268 — 277.] 14. (Решение предложено Р. Мелвиллом в 1980 году.) Пусть стеки В и 8 расположены так, что очередь начинается с верхнего элемента стека В, продолжается до нижнего элемента стека В, а затем проходит от нижнего элемента к верхнеллу элементу стека Я. Если стек В пуст, то элементы стека 8 выталкиваются в стек В до полного опустошения стека Я. Для удаления элемента из начала очереди следует вытолкнуть верхний элемент стека В, который не будет опустошен до тех пор, пока не будет пустой вся очередь в целом.
Для вставки элеллента с конца очереди следует протолкнуть элеллент в стек 8 (если только стек В не пуст). Для извлечения из очереди элемент следует по крайней мере дважды вытолкнуть и дважды протолкнуть. РАЗДЕЛ 2.2.2 1. М вЂ” 1 (но не М). Если допустить, что в очереди может находиться М элементов, как это предлагается в (6) и (7), то будет невозможно отличить пустую очередь от полной, проверяя только й и Г, поскольку проверить можно будет только М состояний. Лучше пожертвовать одной ячейкой памяти, чем чрезллерно усложнить программу. 2.
Вывод элемента с конца; если В = Г, то ОИОЕВГЫМ, У < — Х(В); если В = 1, то В «- И, в противном случае В «-  — 1. Ввод элемента с начала: пусть Х(Г) +- 7; если Г = 1, то Г л — м, в противном случае Г < — à — 1; если Г = й, то ОРВВИ.ОИ. 3. (а) 1.01 1; ЬОА ВАВЕ,7: 1.
Для этого потребуется 5 тактов вместо 4 или 8, как в (8). (Ь) Решение 1. ЬОА ВАЕЕ,2:7, причем для всех базовых адресов 1г = О, 1г = 1. Решение 2. Если необходимо, чтобы для базовых адресов выполнялось условие 1л = 1г = О, то можно записать ЬОА Х2,7:1, где в ячейке Х2 содержится ИОР ВАБЕ,2:7. Во втором решении потребуется выполнить на один такт больше, но в таком случае базовая таблица сможет использоваться с любыми значениями индексных регистров.
(с) Это эквивалентно Ы)4 Х(0: 2), и для ее выполнения потребуется столько же времени, но регистр г14 будет содержать значение +О, тогда как Х(0: 2) содержит — О. 4. (а) ИОР «.7 (Ь) ЬОА Х.7:7(0:2). (с) Это невозможно Код ЬОА 7,7:7, в котором по адресу 7 содержится МОР Х,7:7, нарушает ограничение, накладываемое на поле 7:7 (см. упр. 5). (Й) ХОА Х,7: 1 с дополнительными константами Х МОР «+1,7:2 МОР *+1,7:3 МОР *+1,7:4 ИОР 0,5:6 Время выполнения равняется 6 тактам.
(е) 1МС6 Х,7: 6, где Х содержит ИОР 0,6:6. 5. (а) Рассмотрим команду ЕМТА 1000,7: 7 с конфигурацией памяти Ячейка АРОВЕБВ 1г 1г 1000. 1001 7 7 1001; 1004 7 1 1002: 1002 2 2 1003: 1001 1004: 1005 1 7 1005: 1006 1 7 1006: 1008 7 7 1007: 1002 7 1 1008: 1003 7 2 и с гП = 1, г12 = 2. Найдем 1000,7,7 = 1001,7,7,7 = 1004,7,1,7,7 = 1005,1,7,1,7,7 = 1006,7,1,7,7 = 1008,7,7,1,7,7 = 1003,7,2,7,1,7.,7 = 1001,1,1,2,7,1,7,7 = 1002,1,2,7,1,7,7 = 1003,2,7,1,7,7 = 1005,7,1,7,7 = 1006,1,7,1,7,7 = 1007,7,1,7,7 = 1002,7,1,1,7,7 ы 1002,2,2,1,1,7,7 = 1004,2,1,1,7,7 = 1006,1,1,7,7 = 1007,1,7,7 = 1008,7,7 = 1003,7,2,7 = 1001,1,1,2,7 = 1002,1,2,7 = 1003,2,7 = 1005,7 = 1006,1,7 = 1007,7 = 1002,7,1 = 1002,2,2,1 = 1004,2,1 = 1006,1 = 1007. (Более быстрый способ выполнения этих выкладок вручную заключается в последовательной оценке адресов, указанных в позициях 1002, 1003, 1007, 1008, 1005, 1006, 1004, 1001, 1000 в атолл порцлке. Но колшьютеру, очевидно, придется выполнить эту же оценку именно в заданном порядке.) Автор попытался применить нескольхо необычных схем изменения содержимого памяти во время оценки адреса с полным восстановлением исходного состояния после вычисления окончательного адреса.
Аналогичные алгоритмы рассматриваются в разделе 2.3.5, Однако эти попытки были бесплодными и, похоже, для сохранения всей необходимой информации просто не хватит места. (Ь, с) Пусть Н и С являются всполюгательными регистрами, а М вЂ” счетчик. Для получения адреса Н для команды в ячейке Б необходимо сделать следующее. А1. ]Инициализация.] Установить Н г — О, С л- 1., М +- О, (В этом алгоритме С является "текущей" ячейкой, Н используется для сложения содержимого различных индексных регистров, а М является ллерой глубины косвенной адресации.) А2.
]Проверка адреса.] Установить Н +- АООНЕ33(С). Если 11(С) =,у, 1 < у < 6, то М < — М+ г17. Если 1у(С) =,у, 1 < у < 6, то Н+- Н+г1) Если 11(С) = 1э(С) = 7, то М (- М+ 1, Н л- О, АЗ. [Косвенная адресацияу] Если 1~(С) или 1у(С) равно 7, то С +- М, и перейти к шагу А2. В противном случае Н +- М + Н, Н +- О. А4. ]Сокращение глубины.] Если М > О, то С +- Н, М +- М вЂ” 1, и перейти к шагу А2. В противном случае М является исколлым значением. 3 Этот алгоритм можно корректно использовать в любой ситуации, за исключением случаев, когда 11 — — 7 и 1 < 1у < 6 и когда во время оценки адреса в поле АООЕЕЕБ возникает случай 1л = 1э = 7. Результат будет таков, как если бы значение 1з было равно нулю.
Для разъяснения принципа действия алгоритма А рассмотрим принятые в п. (а) обозначения. Состояние 1.,7,1,2,5,2,7,7„7,7 представляется с помощью С или М = Б, М = 4 (количество замыкающих семерок) и Н = гП+ г12+ г15+ г12 (постндексирование). В решении для и. (Ь) этого упражнения значение счетчика М всегда будет равно либо О, либо 1.
6. (с) приведет к переполнению (ОРЕЕРБОН), (е) приведет к недостатку (ОМОЕНРЬОН), а если выполнение программы будет продолжено, то в дальнейшем приведет к переполнению (ОЧЕЕРЬОН) для заключительного 1ъ 7. Нет, так ках ТОРЫ должно быть больше, чем ОУ ОТОРН], 8. При работе со стеком полезная инфорллация вставляется или удаляется с одной стороны, а свободная позиция — с другой: В С Здесь А = ВАБЕ [»З, В = ТОР[13, С = ВАБЕ[» + 1], При работе с очередью или деком полезная информация вставляется или удаляется на концах, а свободная позиция в середине: А В С В Или наоборот: информация вставляется или удаляется в середине, а свободное место— на хонцах: А С В 11 Здесь А = ВАБЕ[»), В = ВЕАВ[»), С = РНОВТ[Я, [1 ж ВАБЕ[у + Ц. Для непустой очереди эти два случая отличаются условиями В < С и В > С соответственно.
Или, если известно, что очередь не переполнена, эти условия будут иметь вид В < С и В > С соответственно. Очевидно, что алгоритмы необходил»о модифицировать таким образом, чтобы можно была расширять или сокращать пустые промежутки. (Таким образом, в случае переполнения, когда В = С, свободное пространство между В и С можно создать, перемещая только одну часть, а не обе сразу.) При вычислении БОИ и О[») на шаге 62 следует учесть, что кахспая очередь занимает на одну ячейку больше, чем ей действительно требуется (см. упр. 1). 9. Для любой заданной последовательности действий ас,аэ,...,а для каждой пары (», А), где 1' < А и а, > ал, иеобходил»а одна операция перемещения.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
