Д. Кнут - Искусство программирования том 4 выпуск 4 - 2007 (1119377), страница 28
Текст из файла (страница 28)
1(С„+, 1 — С„)У = С„+С„!+ +С!. Аналогично этому, ~ (Ь+ 1) равна »-1 » С(»-1» 1К»-1+0 = ~~ С(»-1 !К»-гез! = ~~~ (С„у+з — 2С»-1+1) = 1=! 1=1 =С„+, — (С„+С., +".+С,). 1=1»=О Таким обрезом, общая стоимость алгоритма составляет С»+! + 4С» + 2 (С»-! + + С1) + О (и) = (26/3 — 10/(Зп) + О (и ~)) С» сделано для ьуэкж$п$ааа1а,ого обращений к памяти. 46. Каждый из простых случаев на шаге КЗ встречается С„! раз, так что сб- щэл стоимость этого шага составляет ЗС„! + 8С„! + 2 (ф— 2С„1) обращений 116 ОТВЕТЫ К УПРАЖНЕНИЯМ к памяти.
Выборка г, на шаге К4 выполняется (х" ' ~) С(х)'+ = Сгп; мп раз; суммирование для о' > 2 дает общее количество обращений к памяти в этом цикле, Равное С<„зд„+П = С„+1 — ЗС„+ С„м Стоимость шага Кб — 6ф— 12С„э. Шаг К6 немного сложнее, но можно показать, что операция г — гь выполняется ф— ЗС„1 + 1 раз при и > 2, а операция г; — 0 выполняется С„1 — п + 1 раз.
Таким образом, общее количество обращений к памяти — С„+1+ 7С» — 9С„э + и+ + 3 = (8.75 — 9.375/и + 0 (и э) ) С„. Хотя это общее количество асимптотически хуже, чем у алгоритма В в ответе к упражнению 44, большой отрицательный коэффициент при и ' означает, что в действительности алгоритм В выигрывает только при и > 58; такие большие значения и на практике не встречаются. 46. (а) Движение влево от ~~ увеличивает площадь на д — р, (Ь) Шаги влево на пути от Яй) до (® соответствуют левым скобкам в а,... ахи, и мы имеем на таком го-м шаге д — р = сь. (с) Эквивалентно, С„+1(х) = 2 ь х"Сь(х)С ь(х).
Это рекуррентное соотношение выполняется, поскольку (и + 1)-узловой лес Г состоит из корня крайнего слева дерева с л-узловым лесом р) (потомками этого корня) и (и — й)-узловым лесом Р'„(остальные деревья) н поскольку длина внутреннего пути (Г) = х + длина внутреннего пути (У)) + + длина внутреннего пути (г',) .
(а) Строки в Ар<по,~ имеют вид ае)сч)... а, ~)аг, где каждое а представляет собой подстроку корректно вложенных скобок. Площадь такой строки равна сумме по всем 1 площадей а плюс г — 7', умноженное на количество левых скобок в о . Прилеечанне: полиномы С1 (х) были представлены Л. Карлицем (1. Сэгйсэ) и Д. Риорданом (Л. ВЗогдап) в 1гпке Мавл.,1., 31 (1964), 371-388; тождество в условии (д) эквивалентно нх формуле (10.12). Они также доказали, что Это обобщает результат упражнения 43. Из (с) мы получаем цепную дробь С (х, х) = = 1/(1 — х/(1 — хл/(1 — хтх/(1 — ° . )))), для которой Д.Н. Ватсон (С.Н.
%агеоп) доказал ее равенство Р(х, л)/Г (х, с/х), где ( 1)п ит и Р(х, ) =7 (1 — )(1 — ') " (1 — ") [см. 7. анонс(оп Май. Зос„4 (1929), 39-48). Мы уже встречались с втой производящей функцией в несколько измененном виде в упражнении 5.2.1-15. Длина внутреннего пути леса представляет собой "'длину левого пути" соответствующего бинарного дерева, а именно сумму количества левых ветвлений на пути от корня по всем внутренним узлам.
Более общий полинам г гя Ъ тв в . ллиив левого пути(т]„Ломив правого пути(т) где сумма берется по всем и-узловым бинарным деревьям Т, похоже, не имеет простого адаптивного рекуррентного соотношения наподобие соотношения для сделано для эуэуж!я$анаса.ого ОТВЕТЫ К УПРАЖНЕНИЯМ 117 С„„(х) = С„(х,1), рассматривавшегося в данном упражнении; однако мы име- ем С„.»2 (х, у) = 2» х»С» (х, у) у" »С„» (х, у). Таким образом, сверхц функция С(х,у,г) = 2",„С„(х, у) г" удовлетворяет функциональному уравнению С(х,у,г) = 1+ гС(х, у,хг) С(х,у,уг).
(Случай х = у рассматривался в упражне- нии 2.3.4.5-5.) 47. С„( ) = Е *( 2 )С (х) С(„)(„) (х) 0 < р < 48. Пусть С (г) = С ( — 1, г) с использованием обозначений из упражнения 46 и пусть С(г) С(-г) = Р(22). Тогда С(г) = 1+ гГ(гг) и С( — г) = 1 — гР(гг); так что г'(г) = 1 — гг' (22) н г' (г) = С (-г). Отсюда следует, что ц ( г) С ( 2) ав г)лб (1 + С ( 2))1» г 'атьь), пРи четном 9 зто выРажение Равно (-1) С~„дптл П (Р четно), а пРн нечетиом— 0 72) (-1) С(гуг) (гу21. Идеальный код Грен для строк А,щ может существовать, только Ь/2) если ~Сг, (-1)~ < 1, поскольку соответствующий граф двудольный (см.
рнс. 41); ~Сгг ( — 1) ~ представляет собой разность между размерами частей, поскольку каждый идеальный переход изменяет с1 + . + с„на *1, 49. Согласно алгоритму П при и = 15 и )'2' = 10е зто строка 0 (О 0) (((О 0) )) ((((О) 0)) ).
ЬО. Внесите следующие изменения в алгоритм П. К шагу Ш добавьте присваивание г +- О. На шаге П3 проверку 12' < с' замените проверкой а = ')*. На шаге ()4 вместо 12 — 12' — с' выполните установку г — г + с'. Кроме того, опустите присванвание а на шагах ()3 и П4. Строка в (1) имеет рвиг 3 141 592 (кто бы мог подумать?).
51. По теореме 7.2.1.3Е 57 = ( ') + ( ™,) + . + ( "); следовательно, к„Ф = ( ",) + + („'2) + ° + ( „"), поскольку г„> 1. Теперь заметим, что 1»' — к„Ф представляет собой ранг 2122... г„, согласно формуле (23) и упражнению 50. (Пусть, например, 21... гг = 1256 с рангом 6 в табл.
1. Тогда 21... вг = 7632, )2" = 60 н к160 = 54. Заметим„что Х достаточно велико, поскольку 21 = 2и — 1; нз рис. 27 видно, что к„г7 обычно нревмшаен2 57 при малых )2'.) 52. Количество завершающих правых скобок имеет то же распределение, что и количество ведущих левых скобок, и последовательность строк вложенных скобок, которая начинается с '(»)' — ( )А(„»)(„п. Следовательно, вероятность того, что 4, = й, равна С(„»К„П/С„. Используя 1.2.6-(25), можно найти, что отсюда следует, что среднее значение и дисперсия равны соответственно Зи/(ц + 2) = = 3 — 6/(и + 2) и 2п (2пг — и — 1) / ((и + 2) (и + 3)) = 4+ 0 (и 1) .
[Моменты зтого распределения были впервые вычислены Р. Кемпом (Н. Ке1пр) в Асга 1п(огтапса, 35 (1998), 17-89, теорема 9. Заметим, что с„= А — 1 имеет, по сути, то же поведение.) сделано для 2»г»лкпИапа(а.ого 118 ОТВЕТЫ Е УПРАЖНЕНИЯМ 53. (а) Согласно упражнению 52 — Зп/(и + 2). (Ь) В соответствии с упражнением 5.2.2-7 математическое ожидание равно Н„.
(с) По индукции можно найти, что математическое ожидание равно 2 — 2 ". (4) Любав (фиксированная) последовательность левых и правых ветвлений имеет одно и то же распределение шагов перед тем, как будет встречен лист (другими словами, вероятность встретить узел с бинарным обозначением Дьюи 01101 равна вероятности встреппь узел 00000). Таким образом, если Х = й с вероятностью ры каждый из 2" потенциальных узлов на уровне Й является внешним с вероятностью рь. Математическое ожидание 2 „2 "рю таким образом, представляет собой математическое ожидание количества внешних узлов, а именно п + 1 во всех трех случаях.
(Этот результат можно проверить непосредственно, с учетом того, что рь = = С(„ь1(„ц/С„в случае (а); рь = [~ь) /и! в случае (Ь); рь = 2 ь+(ь=") в случае (с). Примечание: средняя длина пути в указанных трех случаях равна 9(/й), 9 (1ой и) и 9 (и) соответственно; таким образом, зтот путь оказывается более длинным при более коротком среднем пути к листу.
Это поясняется тем, что вездесущие "дыры'* возле корня приводят к удлинению других путей. Случай (а) имеет интересное обобщение для (-арных деревьев, для которых рь = С(~ „(,, „ /С„' с использованием обозначений из упражнения Зб. Тогда среднее расстояние до листа равно (8+ Ц и/((1 — 1) и+ 2), и очень поучительно доказать с использованием телескопических рядов, что 54. Дифференцируя по х, получим С'(х, 3) = ФС'(х, 3) С(х, хх)+ хс(х, с) (С'(х,хх) + хс'(х,хх)), где С'(х,х) обозначает производную С(х,х) по ю Таким образом, С'(1,з) = 2сСс(1,с) С(х)+хзС(з) С'(х); а поскольку С'(з) = С(х) +2хС(х)С'(х), можно найти решение для С' (1, х), получая с~С (х) /(1 — ЗхС(х)) . Следовательно, (с( + " + с„) = (сч] С' (1, а) = 2~" ' — 1~ (Зп + 1) С„, что согласуется с упражнением 2.3.4.5-5.
Аналогично находим Таким образом, математическое ожидание и дисперсия равны соответственно 1з~/т~Р'+ С(п) и (ь — —,) пз~'+ С(п). сделано для ьтьтжш$ана1а,ого ОТВЕТЫ К УПРАЖНЕНИЯМ 119 56. ДиФФеренцируя, как в упражнении 54, и используя формулы из упражнения 46 (6) и 5,2.1-14 вместе с («") С(«)'~(1 — 4«) = 2«"+' — Я", 2' У(«"+1), получаем ««С(«) +з Ус+1'1 «С(«)"~~1 1 — 4« 2 (,/Г=й 2р+ с+1 ~-, 2р+у с+1 2р+т 56. Используйте упражнение 1.2.6-53 (Ь), [См. В1Т, 30 (1900), 67-68.) 5У. 2Яе (а, Ь) = ( ') (~ь ) + ( ++~«~), согласно 1.2.6-(21).
Упражнение 1.2.6-53 гласит, следовательно, 2Я1 (а, Ь) = («а) («ь) -,~+5. Поскольку Ь2Яр(а, Ь) — Яр+«(а, Ь) = Яр(а, Ь вЂ” 1), находим, что 2Я«(а, Ь) = ( ~+~ ) «+«~ь,, , '2Я« (а, Ь) = (,, ) ( ь") а Ь / (а + Ь) . Формула (30) получается путем подстановки а = т, Ь = и — т и С( ьн +«1 = ( ~ь)— -(. ь* ).
Аналогично: среднее значение ю«„, 1 равно ~ ~(25-1)С,„,Е „цс,„„„ц<„„,„,, ьзе деленному на С„, или 2ЯЗ (т, и+ 1 — т) — Я«(т, и+ 1 — т) т(и+1-т) С„ т(а+1 — т) 2т 2и+2-2т 2п р, В)Т, 20 (1960), 152-163; Н. Р 6(пйег, ЯоосЬ й. Ма«Ь., 0 (1933), 193-196.) 56. Суммируя по всем случаям, когда левое поддерево содержит Ь внутренних узлов, получаем = (1 = т = и = О) + )' С«10 ц1 ь ц( ь ц + У С -1-«$0-ц~ы~.
Таким образом, тройная производящая функция 1(и, в, «) = 2 ,', „0 „и'и™«" удовлетворяет уравнению «(и,ти, «) = 1+ сии(ия) 1(и, и>, «) + и«С(«) 1(и, ~а, «) . сделано для юикьтлп$апаса.ого 120 ОТВЕТИ К УПРАЖНЕНИЯМ Мы получаем также аналогичное линейное соотношение для «(в, х) = д«(а, в, х) / /да~~,, посколькУ «(1,в,х) = 2 ь )2 С„в х" = (С(х) — вС(иЯ))/(1 — в) и хС(х) = С(х) — 1. Алгебраические преобразования дают нам С(х) + вС(ия) — (1+ в) 2вС(х) С(ия) С(х) — вС(ия) «(в2 х)— (1 - в)' 1 — в (1 — в) х.
(2 )(2 — 2 ) можно так же, как в упражнении 36; отсюда следует, что /2т') /2п — 2т') (2гп + 1) (2п — 2т + 1) «па — -2~ ) ~ ) — С„для 0 с т с и. '~т)(, и-т ) (и+1)(п+2) (Р. К!гесЬепЬоГег, Х СогпЫпа«ог(сз„1ПГогша«(оп зад дув«егп Яс!енса, 3 (1983), 44-60. Информация о более высоких моментах и обобщениях может быть найдена в работах %,Л. СЩаЬг, Иап2«ош д«гпс«пгез ап2«А!бог!«Ь)пв, 3 (1992), 361-374; А, РапЬо!хег апг) Н. Рго(!шйег, Х д«а«(е«)са) Р!апп(пд ап2! 7пуегепсе, 101 (2002), 267-279. Обратите внимание, что производяшдя функция «(а, в, х) дает /12( ~~(С~ -Ю( -ВС( — -мя)( — — г). Используя тот факт2 что Еь (,)С(ч й)(2в-1) = С(я-г)(22+э) при т Э 1, получаем ь формулу « „+С„= 2.ь(«г+1) С( Ю( г)С(„„,)(„„,+ь,1), сумма в которой, следовательно, может быть записана в аналитическом виде.] 59.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
