Д. Кнут - Искусство программирования том 3 (2-е издание) - 2001 (Часть 2) (1119371), страница 76
Текст из файла (страница 76)
5.3.3-24. ЗЗ. Действуйте, как на первой итерации поразрядной обменной сортировки, ко вместо первого разряда числа используйте знаковый разряд. 34. В каждой итерации после обнаружения, по крайней мере, одного разркда, имеющего значение О, и одного разряда„имеющего значение 1, т. е. после первого же обмена, можно не проверять условие» < /. Таким образом можно уменьшить время выполнения программы Н примерно на 2С машинных циклов. 33. А = !»! — 1, В = (пап О, ате -'!»! !3 !»1, шах -'!7 !3 !7), С = г! !3 Н, С = 1Н, К = б = Н = О, Я = -'!!à — 1, Х = (ппп О, ате -'(!7 — 1), шах !7 — 1), В общем случае параметры А, С, С, К, Ь, Н и Я зависят от значений ключей в последовательности, но не от нх начального расположения; начальное расположение ключей влияет только на параметры В н Х.
36. (а) 2, (~)(~)(-1)~~!໠— — ~ (.)(»»)(-1)»"уаэ — — ~;(")фпа~ = а,. (Ь) (Ь„а); ( — бы); ((-1)™э ~); ((1-а)"); ((")(-о) (1-а)" ~). (с) Запишем соотношение, которое требуется доказать, в виде х = р„= а„+ з . Тогда из п. (а) получим 9» =- а + = . Также 2' "2.,»йз(„")р» = х„„следовательно, у„удовлетворяет тому же рекуррентному соотношению, что и х„. [Некоторое обобщение этого результата приводится в упр, ЬЗ и 6,3-17. Оказывается, непосредственно доказать, что х = а„2" '/(2" ' — 1), отнюдь непросто!! 37.
(2 „„с ( " )2 ") при произвольной последовательности констант се, см с», .... [Из этопз ответа, хотя он и верен, не сразу видно, что (1/(и 4 1)) и (и — бы) принадлежат к числу таких последовательностей! Последовательности вида (а„+ а„) всегда являются двойственными по отношению к самим себе, Заметны, что в терминах производящих функций А(х) = 2 а„з"/и! имеем А(з) = с*А(-з); следовательно, равенство А = А эквивалентно утверждению о том, что А(х)е-*~з — четная функция,) ЗВ.
Итерация разделения, порождающая левый подмассив длиной э и правый подмассив длиной г! — э, дает следующие вклады в суммарное время выполнения; В=г, С=!»г, К=бы В=бе, Н=б~л, Х=Ь; где ! — число таких ключей среди К»,..., К„разряд Ь которых равен 1, а Ь вЂ” это разряд Ь ключа К,+»; если» = !7, то Ь = О (см. (17)). Это приводит к таким рекуррентным уравнениям, как Вь. =2 ~ (~) ~ )(!+В,+В,,) е«»«»«л =-(!7 — 1)+2 ~ !1 ~В„, где!7>2; Во=В» — -О 1 »-л где~ «3» (см, упр, 23). Применив для решения этих уравнений метод, описанный в упр.
36, получим формулы Ан = !'"л — Ул + 1, Вл = 1(Пл + Ф вЂ” 1), Сл = 1л + »7., Кн = !!г/2 7 л = Нл = 3(1л — !~я — !Ь) +Л, Лл = з(Ал — Вл). Ясно, что Сл = О, 39. После каждой итерации быстрой сортировки, по крайней мере, один элемент попадает в свою окончательную позицию, но этого не происходит прн обменной поразрядной сортировке (см. табл. 3). 40. Если переключаться на метод простых вставок всякнй раз, как только на шаге Н2 будет г — ! < М, то проблема разрешится, если только ие встретится более М равных элементов. Если последнее весьма вероятно, то всегда, когда на шаге Н3 будет у < ! или / ы г, можно проверить условна К~ = = К .
41. В работе 1,псз М, »Уейпет, 1ЕЕЕ Тгапэ. С-34 (1935), 362-367, проанализировано несколько подходов, из которых описанный ниже нам представляется наиболее подходящим для использования на практике, Он несколько упрощен в работе Веп»!еу, Мс1!гоу, Яойнаге !згасг!се уг Ехр. 23 (1993), 1236-12Ж Основная идея состоит в том, чтобы работать с массивом, разделенным на пять частей <К 7 >К =К до тех пор, пока средняя часть не станет пустой. Затем нужно перебросить две крайние части в середину, Р1.
»Начальная установка.» Установить а е- Ь ь- 1, с ь- с( ь- г. Р2. »Увеличивать Ь до тех пор, пока не станет Кь > К.» Если Ь < с и Кь < К, увеличить Ь на 1 и повторить этот шаг. Если Ь < с и Кь = К, выполнить обмен Не ьь Йь, увеличить а и Ь на 1 и повторить этот шаг. РЗ. [Уменьшатьсдотех пор, цоканестанетК, < К.» Юли Ь < си К, > К, уменьшить с нв 1 и повторить этот шаг. Если Ь < с и К, = К, выполнить обмен Л, +ь )7а, уменьшить с и ь1 на 1 и повторить этот шаг. Р4. »Замена.» Если Ь < с, выполнить обмен Нь ее В„увеличить Ь на 1, уменыпить с на 1 н вернуться к шагу Р2.
Р5. »Очистка,» Выполнить обмен Всеь ьь 77 ь при 0 < Ь < пцп(а — (,Ь вЂ” а): также выполнить обмен 7(ьеь ьь й, ь при 0 < Ь < ш!п(4 — с,г — 4). Окончательно установить ! ь- 1+ Ь вЂ” а, / ь- т — 4+ с. $ Совершенно очевидная модификация иа шаго Р1 должна обеспечить эффективную обработку выршкденных случаев н обеспечить а < Ь н с < 4 до перехода к Р2. Тогда исчезнет необходимость в проверках "Ь < с" на шагах В2 и ВЗ (см.
упр. 24). Более того, подобная замена позволит избежать обмена записи с самой собой. Одно из приложений сортировки — сбор записей с равными ключами вместе. Таким образом, разделение на три части зачастую более предпочтительно, чем разделение на две части, предуслгатриэаемое алгоритмом (). Операнди обмена на шаге РЬ выполняются эффективно, поскольку все записи с ключами, равными К, к этому времени уже заняли свок окончательные позиции. Это упражнение придумано В, Г.
И. Фейеном (И'. Н. Я. Ре!)еп), который назвал его "проблемой голландского флага'*: "Задано множество объектов красного, белого и синего цветов, случайным образом разбросанных мемеду тремя колонками. Нужно придумать способ взаимного обмена пар объектов таким образом, чтобы красные собрались в верхней части колонки, а синие — внизу, причем каждый объект должен просмагриваться только один раз и разрешается испольэовать минимальное число дополнительных переменных для управления процессом", »См.
Е. %'. Р!)Ьлсга, А Вмс(р!!ле оГ Ргойгашш!вй (Ргеайсе-На!1, 1976), СЬаргег 11".» 42. Это особый случай теоремы Карпа (см. В,. Ы. Катр, ЗАСМ 41 (1994)., 1136-1150, 52.8). Существенно более строгая аснмптогическая граница для хвоста распределения при быстрой сортировке была получена в работе С. Я, Н. МсР1агш!6, Н. В. Наукап(, Х лП8опгйшн 21 (1996), 476-507. 43. При а ь О+, как следует из упр.
1.2.7-24, имеем ' г Гее у' '(е "— Ц49+/ р 'е "49= Г(а) — 1/а = (Г(а+Ц вЂ” Г(Ц)/а-+ Г'(Ц = — у. о 3 44. При Ь > О имеем гь(т) )(2т)!" ~ Г((Ь+Ц/2) — Ььо — Ег>е( — Ц~Вь ьзгьь/ ((5+22 Ь Ц/! (2т)"). При Ь = -1 вклады от ф ~(гп) в (36) взаимно уничтожаются с подобными членами в разложении Н -м и имеем г з(т) = Нм — ь+(1/ь/йтт) ~,>о/-ь(Г) ф(!п(2пь)+ 7) — ~ 1~,(-Ц~ВП/(22)/! (2гп)'. Поэтому вклад в рг' ~ члена Х/С (33) получается из суммы т ~,>, Г ' ехр(-1~/2т)(1 — го/Зтп ч- г~/18т~)(1 — 1~/4т~)(1 — 1/2т — С /Зтз) + 0(т-лт) = гт!пт + -'(!и 2+ 2)т —,ь >/2нт+ 1„+ 0(т-ьуз), Член --'йГ' ' дает вклад * Имеетсн русский перевал; Дейкстра еь В. Днспнлянна лрогрэммнроэання. — М.: Мир, 1976.
— Прим. верее. — а Яа>а ехр(-Ф~/2ап)(1 — а~/Зла~)(1 — а/2па)(1 + а/ап) + 0(па а~~) = -1ъ/2лап + 1 Член йбаа дает вклад -, И наконец член -(а — ЦВа!а! дает вклад -упа 2 Фехр( — ! /2ап)+ 0(па-а~а) = —,'а + 0(ап-ма). 45, Рассуждение, использованное прн выводе тождества (42), справедливо и для тождества (43), нужно только отбросить вычеты в точках е = -1 и з = О.
46. Действуя тал же, как при вычислении интеграла (4$), получаем (е — Ц!/(л 2+ бе(п), где б,(п) = — ~ бс(Г(е — 2ла/а/)и 2) ехр(2лааа !8 и)). 2 !п2 [Обратите внимание на то, что )Г(в+ ай)!~ = (П ас,((аз+ !а))л/(аэ!а!алФ), где в > О— целое, так что можно найти верхнюю границу для функции б„(п).) 47. СУмма ~1>а е "аа (и/2а)а на самом деле Равна ивтегРалУ из УпР. 46 пРи всех е > О. 48. Воспользовавшись промеж у гочным тождеством г-ааа+ааа *= —,/ Г( ) 'бе, 2ла' а,а а,, действуем так же, как описано в тексте, ио теперь 1 — е * выполняет роль е — 1+ х; е' еаЯп+ Ц = ( — 1/2ла)/ 'Д~~~~ Г(л)п 'а(л/(2 * — Ц+ 0(п '), а интеграл равен !8п+ 7/!и 2 — 1 — бе(п) в обозначениях упр. 46.
(Таким образом, величина 4я из упр. 38 равна !а(1/!и 2 — бе(аа' — Ц вЂ” б-а (аа')) + 0(Ц.) 49. Правуаочастьравеиства(40) можноулучпппь, заменив ееиае "(и/х+бя+хаО(п ')). Результат выразится в том, что будет вычтена сумма из упр. 47 с коэффициентом — и 0(Ц в (47) заменится выражением 2 — а(1/(и 2+ ба(п)) + О(п а). (Двойка появилась из "2/и" в (4$).) 50. Уев = и 1ой и+ п((7- Ц/(и па — а + б а (и)) + па/(па - Ц - 1/(2 (и па) — Зб (и) + О(и '), где ба(п) определяется в упр.
46 но !и 2 н !8 заменяются на (пап и !об . (Замечание. При ап = 2, 3, 4, $, 10, 100, 1000 и 10е имеем б а(ц) < .0000001725, .00041227, .000296, .0008$, .00627, .068, .153, .341 соответственно.] 51. Пусть !а/ = 2ап. Можно распространить суммирование в (3$) на все значении 1 > 1, Тогда сумма будет равна ге+а — / Г(х)(а /!аа) 'аа бз = —, / Г(з)!аа" б(2е — /а) бл а>а а -аее а-аач при условии, что а > (й+ Ц/2, Итак, необходимо знать свойства дзега-функции. Если бс(ю) > -4, то ь(па) = 0()ва)а+а) прн )аи) -а со; следовательно, контур интегрирования можно как угодно далеко смещать влево, если только учесть вычеты.
Сомножнтель Г(е) имеет полюсы в точках О, — 1, -2,..., а а,(2е — аа) имеет полюс лишь в точке л = (й+ Ц/2. Вычет в точке л = -/ равен Ж 1(-Цаб(-2а — /а)//!, а б(-и) = ( — Ц" В„+а/(и+ Ц. Вычет в точке е = (к + Ц/2 Ранен аГ((/а + Ц/2)ааааа+а!а ~. Но если й = — 1, то в точке е = 0 имеетсЯ ашойной полюс, а б(е) = 1/(е — Ц + 7+ 0()л — Ц), так что вычет в 0 в этом случае равен 7+ -' (и !а! — 1ау. "Гаким образом получаем аснмптотический ряд, упомянутый в ответе к упр.
44. 52, Положим, что х = а/и; тогда ( )/( ) =ехр( — 2п(л'/1.2+х/3 4+ ° )+(я'/2+л/4+" ) (1/бп)(яа-яа+".)+" ). „,г,„ Искомую сумму теперь можно представить в виде ряда 2,>, ! «!(!)е ' ~" при различных Ь. Поскольку Дх)" = ) ',>, 4(Ф)! *, то, действуя так же, как и в упр, 51„можно вычислить вычеты функции Г(х) и'Д2х — Ь)~ при Ь > О.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
