Д. Кнут - Искусство программирования том 3 (2-е издание) - 2001 (Часть 2) (1119371), страница 77
Текст из файла (страница 77)
Вычет в точке х = -/ равен и '(-1)1(В„+„,/(2/+ Ь+ 1))'/у!, а вычет в точке х = (Ь+ 1)/2 равен я!«+Ю!«Г((Ь + 1)/2)(7+ 1 !во+ 1Ф((Ь+ 1)/2)), где 0(х) = Г'(х)/Г(х) = Н,, — у. Так, например, если Ь = О, то 2,> е ' !" Щ = -'«/яп п1в и+ (47 — 1 !в 2)т/япп+ - + О(п ' ) при любом ЛХ. Итобы получить Я„/( „), добавьте к втой величине (зт!пи+ Б7+ з« вЂ” ~~ !п2)«/я/й+ О(п '). (См. упр. 1 2 7-23 и 1 2 9-19) 63.
Пусть 4 = 1 — р. Обобщая анализ, выполненный е упр. 36, (с), получим, что если яе = ел + ~ (р 4 + ч р™)е «Ь~ х =о +,) ~,)(-1)' «(и'+9")/(1-р"-4') «»е Следовательно, можно, как и прежде, найти величины Вн и Ся. Множитель -' в Вн нужно заменить на р4, Анализ аснмптотического выражении для Уя выполняется, по существу, так же, как в тексте, причем Т„= ~~ ~ /(е """ — 1+яр*у" ') >ьз>о г-«! х+ю — Г(х)п *(р '+4 )Ня/(1 — и ' — 4 *) -од= (и/Ьр)(!и и + 7 — 1 + Ь> /2Ь> — Ьр + 4(п)) + 0(1), где Ьр = — (р!вр+ 4!п4), Ь> — — р(!пр) + 4(!п9), а Ю(п) = 2„Г(х)п ' */Ьр, причем суммирование выполняется по всем комплексным числам х;4 1, таким, что р * + 4 * = 1, Это последнее множество точек, по-видимому, трудно исследовать в общем случае, но при р = ф ', 4 = ф ~решением будут точки я = (-1)"+'+Ья!/)пй, Главный член (»!пп)/Ьр также можно было бы получить нз общей формулы ван Эмдсна, приведенной в ответе к упр, 29.
При р = «« ~ имеем 1уЪр 1.503718, по сравнению с 1/Ь~гз 1 44269$. 64. Пусть С вЂ” ояружность радиуса (М + 1«)Ь н интеграл по С стремится к нулю прн М -«оо, (Асимптотическое выражение для !7„можно теперь вывести по.новому, разлагая Г(п+ 1)/Г(п+ !Ь«п). Метод, рассматриваемый в атом упражнении, применим ко всем суммам вила )( — 1)" «/(Ь) = —, ~В(п+ 1,-х)/(я) дх, если функции / выбрана обоснованно'.) Последняя формула выведена в работе 1>. Е. !Чбг- !опб, 1'ог!ееппйвп ()Ьег О!!гегелхевгесЬлилб (ВегЫп: Ярг!пбег, 1924), 1103.) бб. Замените строки 04-06 в программе Я следующим образом. 2Н НИТА 0,2 ЗТА 1ИРОТ.З с<Ь<а ЛОЕ ЗР ТИСА 0,3 ЗТХ 1ИРОТ,2 СМРХ 1ИРОТ,4 а<Ь,с ЗЕВ 1 ЗН ЬРА ХМРОТ,4 где-Ь ЛСЕ ЗВ ЗТА в+1(бг2) 5ИР 6Р 10А 1ИРОТ,З а<с<А ЕМТ4 ь 4Н ЬОА 1ИРОТ,З Ь<с<а Ы)Х 1МРОТ.4 Ый 1МРОТ,2 гА+-д 10Х 1ИРОТ,2 ЗТХ ХМРОТ,З ЬВХ 1ИРОТ,З гХ г- с ЗТХ 1МРОТ,З ЛМР бу СИРА 1ИРОТ,З ЛМР ЗР ЗН 101 ХЕРСТ,4 А<о<с Л.
1Р ЗН ЗТХ 1МРОТ.2 с<а<Ь 5ТХ 1ИРОТ, 2 СИРА 1ИРОТ,4 ГА.Ь 101 1ИРОТ,4 65 ЫХ 1ИРОТ+1,2 ЛЕ ЗР ЗТХ ХЕРСТ,З ЗТХ 1ИРОТ.4 СМРХ 1ИРОТ,4 гХ:Ь Л1Р бу ЕМТ4 2,2 М 4Р 1Н СИРА 1ИРОТ,4 ЕИТЗ 0,3 После этого должно следовать ЗТА 1ИРОТ+1,2 (см. замечание после (27)). Зшяеннте команду в строке 22 командой зтх 1МРОт+1,2. Если в системе команд отсутствует команда поразрядного сдвига, то первые три команды в программе нужно заменить командой ЕМТХ 0,2. 1ИСХ 0,3; ЕИТА 0; 017 2 .
Сущность этой программы состоит в организации обмена Л,~г с К~ О+,Нэ1 и сортировки записей Кн Кггг и )Ь„. Затем к Кггг... Я, г применяется обычнаа процедура разбиения. Несколько команд можно сэкономиттн просто поместив меднанный элемент в регистр гА и переписав Нг туда, где ранее был медианный элемент. Дктее все нужно продолжить, как в программе (). Но такой подход может привести к нежелательным последствиям, поскольку требуется порядка Лн шагов для сортировки массива Ж 57-1 ... 1.
(Этот неожиданный побочный результат впервые подметил Д. Б. Колдрик ()У. В, Со)бг1с)г), но его нужна проверить самостоятельно. Попробуйте!) Рекомендуемый выше метод, авторство которого принадлежит Р. Седгевику, оказался свободным от связанной с длиной слова аномалией, но работает так же быстро. При использовании такой схемы не нужно проверять Ке и Клен Следовательно, проверка граничных значений не сдерживает скорости выполнения внузреннего никла. 56. Можно решить рекуррентное соотношение (")хх = Ь + 2Щ г(Й вЂ” 1)(п — Ь)хг-г при и > пг, положив у = гш„, и = пу„е, — (п+ 2)Р, с„= пи„тг — (и — 5)и„, Отсюда с„м 6(Ьх+з — 25„.гг+Ь„) прин > т, Иапример, прешь х„= Ь„г прап < т и прстпьб„ш О.
Тогда о = О при всех и > нк следовательно, и — в„+г = пз-и тг. Поскольку у +г = 12/ш А А и р +з = 12/(гп+1), окончательно находим х„= ф(в+1)/гл(ел+1)(т+2)+ ЬгА(гп-1)А/па при и > пг. В общем случае пусть /„=- (12/(и — 1)(п — 2)) 2„„" г(Ь вЂ” 1)(п — Й)хь н если Ь„ тождественно равно О, то решением при и > гп будет х = (и+1) (гп+1)/ +з — (ш — 4)/ ьг ((па+1)~/+г — (т+3)/ +~)гпА 7(пг + 1)(гл + 2) 7пА Если Ь„= (") /пг.
н х„= О при и < т, то решением будет х„(р — З)(р — 2) 12 1 12 (т+ 1 — Р)е Е и + 1 (Р— 6ИР+ 1)(п+ 1)'+' 7 (Р+ 1)(гл+ 2)"е' 7 (Р— 5)(п+ 1)г при и > гл, За исключением случаев, когда р = — 1, получим х„/(и+ 1) = — „(гт ~+г— Нм+т)+ Я+ 14э(ш+2)1/(и+Цг, акогдар = б, х /(и+1) = — И(Н -е — Нм-е)/(гг+1)-+ 4э/(гп т2) .+ ~р/(л+ 1) Рассуждая, как в упр. 21-23, придем к выводу, что первая фаза разделения теперь внесет 1 в А, г в В и дг — 1 в С, где 1 определяется, как н ранее, но посев перекомпановки, которая сделана в упр.
55. При новых предположениях Ьмл = 6(', )(; )/гт(, г). Следовательно„рекуррентиые соотношения, выведенные выше, в этой задаче появляются следующим образом. Значения зк/( з) ддя/л'<М язями>М Решения для Ж > М (к+ 1)( И АМ+2)) — !+О(Ф е) (С„-ЗАк)/5 (н+ !)( зш (нк+л — нм+л)+ лэ — зт-/(м+2))+2+О(н з) ( + )( 7 ах+1/( . ) — х/(М+2))4О(Н ) (Ж+!)(азМ-Ц+йх/(М+2))+О(Ж з) 1 (Н-4)/5 Н-! О 0 О О О Ф- Нк Ф(Ю-1)/4 Аналогично Бк = ф(Н+ 1)(5М+ 3)/(2М+ 3)(2М+ 1) — 1+ 0(!!г э). В среднем суммарное время выполнения программы в упр.
55 равно 531Ак + 11Вк + 4Ск + ЗВк + ЗВк + 9$к + 7Ж. Выбор М = 9 лишь немного лучше, чем М = 10, и приводит к среднему времени выполнения, равному примерно 10$/л/!пХ+ 2.!!бай «Асса 1лб 7 (1977), 335-34!). После замены 389 на 017 11Ак добавляется к среднему времени выполнения и требует установить М = 10. РАЗДЕЛ 5.2.3 1. Иет, но метод, в котором используется оо (описанный непосредственно перед алгоритмом Б), устойчив. 2. Просмотр линейного списка, хралящех"осл в последовательных ячейках памяти, часто вызхохлняется несколько быстрее, если двигаться в сторону убывания индексов, поскольку, как правило.
легче проверить, равен ли индекс О, чем проверить, превышает ли он Ж. (По той же причине при поиске на шаге 82 индекс убывает от х к 1; тем не менее см. упр. 8!) 3. (а) Перестановка аз .., ак ~/Х/ соответствует исходным массивам Фаз...ак-~аь алмаз...ак лаз, ...
ахаз...ак-зНак-ы аь.,ак-зЖ. (Ь) Как показано в разделе 1.2.10, на первой итерации шага 82 число случаев изменения максимума равно Нк — 1. (Следовательно, Вк можно найти нз соотношення 1.2.7-(8).) 4. Если исходный файл является перестановкой множества (1, 2,..., Н), то число случаев, когда на шаге БЗ окажется л =,1, в точности на единицу меньше числа циклов в этой перестановке.
(В самом деле, нетрудно показать, что на шагах 82 и БЗ элемент х попросту удаляется из своего цикла. Следовательно, шаг БЗ бесполезен лишь в том случае, если элемент / был нанменьпхим в своем цикле,) Согласно равенствам (1.3.3-(21)) можно было бы сэкономить в среднем Нк — ! из Х вЂ” 1 выполнений шага БЗ. Таким образом, было бы неэффективно вставлять перед шагом БЗ дополнительную проверку "'л = 175 Вместо того чтобы гравниваты с /, можно слегка удлинить программу для шага 82, продублирован часть команд, чтобы не переходить к плаху БЗ, если первоначальный выбор К, не изменился во время поиска максимума. За счет этого программа Б стала бы работать чуть-чуть быстрее. 5. (Ж вЂ” 1)+ (/л/ — 3) + ..
= (Жз/4!. 6. (а) Если на шаге БЗ окажется, что л и. /, то после его выполнения число инверсий уменьшится на 2т — 1, где т на единицу больше числа ключей, лежащих в интервале влежду К, и К. среди Клал...Кх л. Ясно, что пз не меньше, чем ихлад в значение параметра В на предыдущем влаге 82.
Примените теперь следствие из упр, 4, связывающее циклы с условием ! =,~'. (Ь) Любую перестановку можно получить из Ф... 2 1 путем последовательных взаимообменов соседних элементов, которые нарушают исходное упорядочение. (Примените в обратной последоватльзьностн те обмены, под действием которых перестановка сортируется в поркдке убывании.) Каждая такал операция уменьшает 1 иа едипицу и измеввет С иа ш1.
Следовательно, ии длв одной перестановки значение 1 — С не превосходит соответствующего зиачеиия длв Я... 2 1. [Из упр. 5 вытекает, что неравенство В < [Н~Х4) — наилучшее из возможиых.[ 7. В работе А. С. г'ао, Ол вггш8йс ве(ест(ол васс (Сошрвсег Бс(елее ТесЬп(са( Веров( 183, Рппсесов Оп(тегвйу, 1988), показано, что дисперсия равна аКьв + О(1т'~~~!оКХУ), где а = -"тук 1п ~ 0.9129. В ией также высказано предположение, что в действительности составляющэл ошибки значительно меньше.
8. Можно иачииать очередную итерацию шага 32 с позиции Кь поскольку мы запомнили шах(Км...,К*-~). Один из способов учета всей этой доиииительиой информации— испавьзоваиие таблицы связи Х ы .. Х л, такой, что Кс равно предыдущему выделенному элементу всакий раз, когда Кв также выделено; Хо = О. [Тот же результат можпо получить, использук меньший объем дополнительной памвти, "заплатив" за это лишней операцией сравнения.[ В приведеиной ниже Н1Х-программе применяется модификация адреса в ходе выпол- неииа, котарав ускоряет реализацию внутреннега цикла.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
