AOP_Tom3 (1021738), страница 178
Текст из файла (страница 178)
(Таким образом, величина Ал из упр. 38 равна йь(1/ 1и 2 — бе(йь — 1) — б-ь (Д«)) + О(1).) 49. Правую часть равенства (40) можно улучшить, заменив ее на е *(и/х+-'х+хвО(п ')). Результат выразится в том, что будет вычтена сумма из упр.
47 с коэффициентом -' и 0(1) в (47) заменится выражением 2 — —,'(1/!и2+ бь(п)) + 0(а ь). (Двойка появилась из «2/и« в (45).) 50. ь«' = п!об и+н((7 — 1)/!ит — ь+5 ь(п))+т/(си — 1) — 1/(21ит) — -'бь(п)+0(п '), где б,(п) определяется в упр. 46 на 1и 2 и 18 заменяются на !и т н 1об . [Замечание. При си = 2, 3, 4, 5, 1О, 100, 1000 и 10 имеем б ь(п) ( .0000001725, .00041227, .000296, .00085, .00627, .068, .153, .341 соответственно.) 51. Пусть ььь = 2т. Можно распространить суммирование в (35) на все значения 1 > 1.
Тогда сумма будет равна г«-ь-ь» г".ь' — В[ Г(х)(! /Дь) 1 с!х = — Г(с)ььь с,(2в — х) «ьх 2«гь /, 2яс / с>ь при условии, что а > (й+ 1)/2. Итак, необходимо знать свойства дзета-функции. Если 3!(аь) > — д, то ~(ььь) = О([и[с+') при [ю[ -ь ао; следовательно, контур интегрирования можно как угодно далеко смещать влево, если только учесть вычеты. Самножитель Г(в) имеет полюсы в тачках О, — 1, -2,, а Д2х — й) имеет полюс лишь в точке с = (й+ 1)/2. Вычет в точке х = — / равен ьс ь(-1)'ь,( — 21 — к)//1„а Д-~) = (-1)" В«ь«ь/(и-ь1).
Вычет в точке с = (й+ 1)/2 равен -'Г((й+ 1)/2)Х1ь+ьььс. Но если !с = -1, то в точке х = О имеется двойной полюс, а Ь(х) = 1/(х — 1) + 7 + 0([х — Ц), так что вычет в 0 в зтом случае равен 7 + с 1и Х вЂ” -с7. Таким образам получаем асимптотический ряд, упомянутый в ответе к упр. 44. 52. Положим, что х = !/и; тогда )//~ ) =ехр(-2п(х/1 2+х/3 4+ )+(х/2+х/4+ .) — (1/бп)(х — х + ) + .
). 427 Искомую сумму теперь можно представить в виде ряда 2 '4>, 1~3(4)е 4 ~" при различных 74. Поскольку Г(х)2 = 2 о>, 3(!)1 ', то, действуя так же, как и в упр. 51, можно вычислить вычеты функции Г(3) и'Д2х — Л) при Л > О. Вычет в точке 3 = — у равен а вычет в точке х = (Л+ 1)/2 равен по~ Ю72Г((Й + 1)/2)(7+ -' !пи+ -'ф((Л + 1)/2)), где ф(х) = Г'(х)/Г(х) = Но, — 7. Так, например, если Л = О, то 2 4>, е ' 7" 4!(2) = 12/яп 1пп+ (37 — -' !и 2)2/яп+ -' + О(п™) при люболг М. Чтобы получить оо/(~"), добавьте к этой 4 2 величине ( ~ !и п + — 7+ — 4 — гй !в 2) 2/т/и + 0(п ). (См.
упр. 1 2 7-23 и 1 2 9 — 19 ) 53. Пусть 9 = 1 — р. Обобщая анализ, выполненный в упр, Зб, (с), получим, что если х„=о„+) ( 1(р"9" '+д'р" ")х„, 1Л) Ь>2 то х = а„+ ~ ( 1(-1)' аг(р + Ч~)/(! — р~ — Ч~). 1Л) Кй 2 Следовательно, можно, как и прежде, найти величины Вя и Сч Множитель -' в Вл нужно заменить на рд. Анализ асимптотического выражения для Ул выполняется, по существу, так же, как в тексте, причем Т = ~ ~~ )(е Р— 1+яр д ) >Цо>0 à — 3/24. о — Г(х) и *(р ' + д ') Нх/(1 — и — 9 *) 2яг -3(2-роо = (и/Лр)(!Пп + 7 — 1 + Лр /2Лр — Лр + 0(п)) + 0(1), где Лр — — -(р!ар+ д!п4), Лр —— р(!пр) + о(!од), а д(п) = 2 Г(г)24 ' */Лр, причем суммирование выполняется по всем комплексным числам х ф 1, таким, что р * + д ' = 1.
Это последнее множество точек, по-видимому, трудна исследовать в общем случае, на при р = ф ', 9 = ф 2 решением будут точки х = ( — 1)~+' + Лхо/!и ф. Главный член (п1п и)/Лр также можно было бы получить из общей формулы ван Змдена, приведенной в ответе к упр. 29. При р = ф ~ имеем 1/Лр ое 1.503718, по сравнению с 1/Л272 ж 1.442б95. 54. Пусть С вЂ” окружность радиуса (М+ 4)5 и интеграл по С стремится к нулю при М 4 оо. (Асимптотическое выражение для С можно теперь вывести по-новому, разлагая Г(п+ 1)/Г(п+ 25оо).
Метод, рассматриваемый в этом упражнении, применим ко всем суммам вида если функция / выбрана обоснованно!) Последняя формула выведена в работе Х, Е. 1>оог- !цп41, 'рог!еэовбев аббес О!/Гегепхелгесбливб (Вег!ос Ярппбег, 1924), 2103.) 55. Замените строки 04-06 в программе 14 следующим образом. 2Н ЕИТА 0,2 БТА 1МРОТ,З с<6<а 1СЕ БГ 1МСА 0,3 БТХ 1МРОТ,2 СИРХ ХМРОТ,4 а<Ь,с БИБ 1 ЬН ЬВА 1МРОТ,4 гА»-Ь ЮСЕ ЬН БТА »+1(0ь2) ЗНР 6Г ЬВА 1МРОТ,З а<с<Ь ЕИТ4 4Н ЬВА 1ИРОТ,З 6<с<а ЕВХ 1МРЬ1Т,4 ЬВА 1МРОТ,2 гАг-а ХВХ 1ИРОТ,2 БТХ 1ИРОТ,З ЬВХ 1ИРОТ,З гХг-с БТХ 1МРОТ,З ЛИР 6Г СИРА 1МРОТ,З ЛИР ЬГ ЬН ЬВХ 1МРОТ.4 6<а<с ЮЬ 1Г ЗН БТХ 1МРОТ,2 с<а<Ь БТХ ХИРОТ,2 СИРА ХМРОТ,4 гА:Ь ЬВХ 1МРОТ,4 6Н ЬВХ ХМРОТ+1,2 ЗЬЕ ЗГ БТХ 1ИРОТ,З БТХ 1ИРОТ, 4 СНРХ 1ИРОТ,4 гХ:Ь ЗНР бр ЕМТ4 2,2 10 4Г 1Н СИРА 1МРОТ,4 ЕИТБ 0,3 После этого должно следовать БТА 1МРОТ+1,2 (см.
замечание пгкле (27)). Замените команду в строке 22 командой БТХ 1ИРОТ+1,2. Если в системе команд отсутствует команда поразрядного сдвига, то первые три команды в программе нужно заменить командой ЕМТХ 0,2, 1ИСХ 0,3; ЕИТА 0; 01Т =2». Сущность этой программы состоит в организации обмена Вь ьь с Вць+,Нь1 и сортировки записей Вь, Вь+ь и В„. Затем к Вь „,... В„ь применяется обычная процедура разбиения. Несколько комшгд можно сэкономить, просто поместив медианный элемент в регистр гА и переписав Вь туда, где ранее был медианный элемент Далее все нужно продолжить, как в программе С) Но такой подход может привести к нежелательным последствиям, поскольку требуется порядка Аг~ шагов для сортировки массива Аг ьг"-1 ...
1. (Этот неожиданный побочный результат впервые подметил Д В. Колдрик (П. В. Со!бгьсу), но его нужно проверить самостоятельно. Попробуйте!) Рекомендуемый выше метод, авторство которого принадлежит Р. Седгевику, оказался свободным от связанной с д,еиной слова шгомалией, но работает так же бьютро, При использовании такой схемы не нужно проверять Ко и Кл»ь. Следовательно, проверка граничных значений не сдерживает скорости выполнения внутреннего цикла. 66.
Можно Решить РекУРРеитное соотношение (")х„= Ь, + 22 „" ь(Ь вЂ” 1)(п — )с)хь-ь пРи и > т, положив у = пх, я, =- пу ь — (и+ 2)у„, с„= пи»ьь — (и — 5)п„. Отсюда = б(Ь»ьь 2Ь ль+Ь ) прин > т. Напральер, пусть х„= Ь„ь арии < т н пусть Ь„= О. Тогда с„= О при всех и > т; следовательно, и — и»ьь = т — иыьь. Погкольку у ь = 12/т 5 5 и у ьь = 12/(го+1), окоичагельио находим х = г (и-61)/т(т+1)(т+2)+ — (т — 1)А/пя при н > гп.
В общем случае пусть /„= (12/(и — 1)(п — 2)) 2 ". ь(Ь вЂ” 1)(п — Ь)хь ь, если Ь» тождественно равно О, то решением при и > гп будет х = (гь+ 1) (т — 1)/ — (т — 4)/ ((т+ 1)/ — (т+ 3)/ -;. ) т- 7(т+ 1)(т+ 2) 7пд Если Ь = (")/гьв и х„ = О при и < гп, то решением будет х„(р — 3)(р — 2) 12 1 12 (т+ 1 — р)е Е и+ 1 (р — б)(р+ 1)(а+1)еьл 7 (р+ 1)(гл+ 2)г»'..
7 (р — б)(п+ 1)г при и > т. За исключсняем случаев, когда р = -1, получим х„/(и+ 1) = г (Н +ь— ХА Н,ьг) + 4д + То(т+ 2)1/(и+ 1) —. а когда р = б, х /(и+1) = — -'(Н» — с — Н -")/(и+ 1)1+ ьэ/(гп + 2)1+ яв/(и+ 1)1 Рассуждая, как в упр. 21-23, придем к выводу, что первая фаза разделения теперь внесет 1 в А, 1 в В и Аг — 1 в С, где 1 определяется, как и ранее, но восле перекомпановки, которая сделана в упр. 55 При новых предположениях 6 ьл = б(',~)(~; )/Аг(,:ь). Следовательно, рекуррентные соотношения, выведенные выше, в этой задаче появляются следующим образом. Значения 5я 7 ( ) для Л'(М для в>М Решения для У > М (И+Ц(гг((М+г))-1+О(Л-') (Сл -ЗАи)/5 (К+Ц(И(нл,.г-Им,,)+М-54!(М+г))+г+О(И-') (и+1)(г- — ",и„„.,)(м+г) — гг)(м+г)) ,-о(и-') (И+Ц(вйм ге+7((~~~))~~(~ ) а а а и — и, л(л -1У4 1 (и — 4)/5 К-1 а а Ал в„ ои ол вл Аналогично Бл = 5(Лг+1)(5М+ 3)/(2М+3)(2М+ 1) — 1+О(Х е).
В среднем суммарное время выполнения программы в упр. 55 равно 53-'Ая +11Ви + 4Сь + Зол + 8Еи+ 9Бя + 7Лг. Выбор М = 9 лишь немного лучше, чем Мт = 10, и приводит к среднему времени выполнения, равному примерно 10гггЛ" 1пЛг+ 2.116Лг (Асса!лб 7 (1977), 336-341]. После замены 388 на 017 11Ал добавляется к среднему времени выполнения и требует установить М = 10. РАЗДЕЛ 5.2.3 1. Негг но метод, в котором используется со (описанный непосредственно перед алгоритмом Б), устойчив.
2. Просмотр линейного списка, хранящегося в последовательных ячейках памяти, часто выполняется несколько бысгрее, если двигаться в сторону убывания индексов, поскольку, как правило, легче проверить, равен ли индекс О, чем проверить, превышает ли он Х. (По той же причине прн поиске на гласе 82 индекс убывает от 2 к 1; тем не менее см. упр.
8!) 3. (а) Перестановка ог... аи-г Х соответствуег исходным массивам Лгог... ая гам аг Наг .. ал газ, ..., агаз...пиггчох м аг... пл гЛг. (Ъ) Как показано в разделе 1.2.10, на первой итерации шага Б2 число случаев изменения максимума равно Нл — 1. (Следовательно, Вл можно найти из соотношения 1 2 7 — (8).) 4. Если исходный файл является перестановкой множества (1, 2,..., Х), то число случаев, когда на шаге БЗ окажется г = 1, в точности на единицу меньше числа циклов в этой перестановке. (В самом деле, нетрудно показать, что на гпагах Б2 и БЗ элемент 2 попросту удаляется из своего цикла.
Следовательно, шаг БЗ бесполезен лишь в том случае, если элемент У был наименьшим в своем цикле.) Согласно равенствам (1.3.3 — (21)) можно было бы сэкономить в среднем Ни — 1 нз Х вЂ” 1 выполнений шага БЗ. Таким образом, было бы неэффективно вставлять перед шагом БЗ дополнительную проверку "г = у?5 Вместо того чтобы сравнивать г с г', можно слегка удлинить программу для шага 82, продублировав часть команд, чтобы не переходить к шагу БЗ, если первоначальный выбор К; не изменился во время поиска максимума. За счет этого программа Б стала бы работать чуть-чуть быстрее.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
