Д. Кнут - Искусство программирования том 3 (2-е издание) - 2001 (Часть 2) (1119371), страница 86
Текст из файла (страница 86)
Если [де[ < дь получим [ф = г, а если иет то получим [С[ > [Яе, '— [С(ре)[+ 1 > [Яе[ — (9 — г) + 1; так что в обоях случаях будет сделано ие менее и — д подбрасываний. Существует и+ 1 — 1 множеств Т, в которых содержатся 1 — 1 старших элементов, определяемых паиным листом дерева, и для каждого такого Т вероятность достичь его раппа либо О, либо 2 7/[,), где / > и — 9 есть число подбрасываний моиеты, соответствующее Т. [Этот сопериик был "реализоваие в статье Беита (Вель) и Джона (ЗоЬв), АТОС 17 (1985), 213-21б.[ (с) если ь < г, замените 1 значением и+1-1; получим, что 1 > г, когда г максимизирует правую сторону, поскольку г будет 0(ь/и ), Если возможно достичь АЗ с [С(р) [ > 9 — г при всех р б Те, алгоритм выполнит и — 1 сравнений 1-го по старшинству элемеита со всеми другими в дополнение ие менее чель к (г — 1)(д — г+ 1) сравнениям, которые выполняются между Я и Т ь '.[рэ).
(ь() Выберем г = [ь/т1 и ь) = 2г — 2. (Несколько лучше положить д и г+ [ь/т+1) — 2; такой выбор позволит максимизировать нижнюю оценку, выведенную в (с).) РАЗДЕЛ 5.3.4 1. (Если гп = 2Ь вЂ” 1 иечетио, то лучше, чтобы в диаграмме за оь вместо вьем вьем пьет, следовали элементы оьэм пэвм еь+ь, .... Такая замена корректна, поскольку линии, которые мы переставляем, сравниваются одна с другим.) 8-элемектяья сортировка Пратта (3,5)-элементное четко-нечегкое слияние хь еь — ьь хь мь -7.— ьэ хь ез -4» — ьь ш юь 7 — ьь кь вэ -3 — ьь кь еь 7 -ьь Уь юь -3- ьт Уь еь — ьь 2.
Для приращения Ь нужно 2 — [2Ь > и[ уровней; см. ириведеипую выше диаграмму для и=8. 3. С(т,т-1) = С(гп,т) — 1 при т > 1. 4. Если предположить, что Т(б) = 4, то в каждый момент должны действовать три компаратора, так как Я(б) = 12. Но тогда, удалив нижнею линию и связанные с ией четыре компаратора, мы получили бы Я(8) < 8, а это — противоречие. [Те же рассуждения показывают, что Т(7) = Т(8) = б, Яан Парберри (1ап РегЬеггу) провел длительный компьютерный поиск и пришел к результату Т(9) = Т(10) =- 7; см.
МаСЬ. буээешэ ТЬеогу 24 (1991), 101-11б.[ 5. Пусть /(и) = /([и/2]) + 1+ [!8[п/2Ц, если и > 2. Тогда, применив индукцию по н, получим /(и) = (1+ [!Зп])(!Зп]/2. 6. Можно считать, что на кюкдой стадии выполняется [и/2] сравнений (лишние сравнения не помешают), Так как Т(б) ж 5, достаточно доказать, что Т(5) = 5. В случае и = 5 после двух стадий мы не можем избежать частичных упорядочений ь.
или ~., которые нельзя рассортировать за оставшиеся две ставни. 7. Допустим, что исходными ключами будут (1, 2,..., 10). Ключевым моментам решения является то, что после первых !б компараторов линии 2, 3, 4 и б не могут содержать ни 8, ни 9, ни б и 7 вместе. 8. Это очевидное обобщение теоремы Р, 9. ЛХ(З, 3) > Я(б) — 2Я(З), М(4,4) > Я(8) — 2Я(4), ЛХ(5, 5) > 2М(2, 3) + 3, как следует из результатов упр.
8 н М(2, 3) > Я(5) — Я(2) — о(3). Анавогично М(З, 4) = 8. Но чему равны М(3,5) и М(4,5)7 10, Используйте указание н метод доказательства теоремы 2, Затем покажите, что число нулей в четной подпоследовательности минус число нулей в нечетной подпоследовательности равно ж! или О, 11. (Решение М. У. Грина.) Рассматриваемая сеть симметрична в том смысле, что всякий раз, когда х, сравнивается с х„., найдется соответствующее сравнение хм,,: хж, ь Любая симметричная сеть, способная сортировать последовательность (хе,..., хэ Д, будет также сортировать последовательность (-аз~,,..., — зе).
Бэтчер заметил, что эта сеть в действительности будет сортировать любой циклический сдвиг (хз, хз+м ..., хз „„хе,..., зу ~) битонной последовательности. это следует из принципа нулей и единиц. !Данный результат не прилолспм к битонным сортировщнкам, если ях порядок отличен от степени 2. Например, сортнровщик на рнс. 52 не сможет сортировать погледовательность (О, О, О, О, О, 1, О). Сформулированное Бзтчером определение битонной последовательности сложнее и менее удобно, чем то, которым мы пользуемся.] 12. Последовательность х ч р является бнтонной (ра«смотрите последовательности нз О н 1), а последовательность я Л р — нет (рассмотрите, например, (3, 1, 4, 5) А (б, 7, 8, 2)).
18. Идеальное тасованне заменяет щ элементом х, где двоичное представление 2 получается из представления ! в результате циклического сдвига вправо на один разряд (см. также упр. 3.4,2-13). Рассмотрим перетасовку компараторов, а не линий. Тогда первый столбец компараторов имеет дело с парами х[!] и х[! б 2" '], следующий столбец — с парами з[!] н х[! я 2" з], ..., ый столбец — с «[!] и э[1 !5 ц, (! + 1)-й столбец — сяова с э[1] н х[! Э 2" '] и т, д. Здесь О! обозначает операцию "исключающее или" над двоичными представлениями. Эти соображения показывают, что рис. 57 эквивалентен рис.
об; после з стадий мы получаем рассортированные группы из 2' элементов с чередующимися направлениями упорядочения. В работе С. С. Р!ахФоп, Т. Иве), Май. Яузсешз Тйеогу 27 (1994), 491-508, показано, что любая сеть такой структуры имеет, по меньшей мере, П((!обп)~/!об!обп) уровней задержки. 14.
(а) Пусть р;, = х „у-, ы вп, уь = вь при 1, ф 5 Р /,; тогда рп' = хп. (Ь) Это очевидно до тех пор, пока множество (1„7'„!пЯ имеет только три отличающихся элемента; пРедположим, что !. = гь Тогда, если в < 1, пеРвые з — 1 компаРатоРов заменЯт (1„/„7~) соответственно элементами О„д,,т,) как в (и')',так н в (а")'. (с) (а')' = а и п~ = а, прд ь, » . »,1. (4)пу яма[1:/], да рв(К1 ° ° ~ Кв) (й у Ху) Л (9*(вы..., ВП ..
°, ХЗ,..., К ) У 9 (КЫ..., КЗ, ° ° ~ ап ° °, Зв)). ПО сгроив итеративную процедуру нз этих равенств, получим искомый результат. (е) / (к) = 1 тогда и только тогда, когда не существует пути на графе С„от 1 к» при угловии х; > х,. Если а — сеть сортировки, то сопряженная с а сеть также является сетью сортировки и 7' (я) = 0 при всех х, удовчетворяющих неравенству к, > х,+ь Примем х = епЦ это показывает, что С не имеет дуг от» к к» прн некотором 7п Р». Если Й~ ф 1+ 1, то В ж Е(П У ЕЖ) ПОКаЭЫВавт, ЧтО С' ИМЕЕТ дуту От» ИЛИ 7»» К ВЭ Прн НЕКОтОрОМ ЛЭ й (йй~).
Если Йг Р' » + 1, продолжаем рассуждать так же до тех пор, пока не найдем путь на графе О от» к (+ 1. Обратно, если и не является сетью сортировки, пожиким, что л— ВЕКтвр С ач > Коы и д„(Х) = 1 Двя НЕКОтОрОГО СОПряжЕННОГО С»' ПОЛуЧНМ 7к (К) = 1, так что О может н не иметь пути от 1 к 1+1.
[В обв»ем случае (гп); < (хп) при всех э тогда и только тогда, когда С имеет ориентированный путь от 1 к 7' ярн всех а', сопрвженных с и.] 16. [1: 4ЦЗ: 2] [1: 3] [2: 4Ц2: 3]. 16. Процесс, очевидно, заканчивается. После каждого выполнения шага Т2 выходы с номерами 1» и 2 меншотся местамн, поэтому в результате выполнения алгоритма сформируется некоторая перестановка выходных линий. Так как получившаяся (стандартная) сеть не изменяет вход (1,2,...,и), выходные линии должны вернуться на свои прежние места.
17. Сделайте сеть стандартной, воспользовавшись результатом упр. 16. Затем, анализируя входную последовательность (1, 2,..., и), увидим, что стандартные сети выбора должны помещать 1 наибольших элементов на 1 линий с наибольшими номерами, а 1)(п)-сеть должна помещать »-й в порядке убывания элемент на линию и+ 1 — й Примените принцип нулей и единиц. 16. Из доказательства теоремы А слезбет, что Ъ~(п) > (н — 1) [13(1+ 1)] + (131]. 19. Сеть [1: пЦ2; и]... [1: ЗЦ2:3] выбирает наименьшие два элемента, имея 2п — 4 компара- торов.
Для 17»(п) добавьте [1:2]. Нижняя оценка получается из теоремы А (см. ответ к предыдущему упражнению). 20. Прежде всего, заметим, что 1»(г») > Уз(п — 1)+2, если и > 4. В силу симметрии можно считать, что первый компаратор есть [1: и], после него располшкена сеть для выбора тре- тьего в порядке убывания нз (хэ, хэ,, кь) и еще один компаратор. связанный с линией 1. С другой стороны, Ъз(5) < 7, так как 4 компаратора находат минимум и максимум нз (хм кэ, гэ, г»] н остается рассортировать три элемента. 21.
Утвержденна ложно. Рассмотрите, например, сети [1:2ЦЗ:4Ц2:ЗЦ1.4Ц1;2ЦЗ 4] и [1 2] [3:4Ц2:ЗЦЗ:4Ц1:4Ц1:2ЦЗ:4]. (Однако Н. Г. де Брейн (Х. О. де Вгп»1п) доказал, что новые компараторы не вносят путаницу в нрпмпшпену»о сеть сортировки в смысле упр. Зб; см. Ебзсге»е Май. 9 (1974), 337.) 22. (а) Результат получается индукцией по длине и, поскольку из з~ < у, н х, < у, следует, что х; Л в, < Рд Л 91 и х; У э; < уд У 9». (Ь) Результат получается индукцией по Длине а, посколькУ (х; Л хз)(9; Л У,) + (лс У э»)(Р» Уру) > х»9»+ х»91. [Следовательно, и(х Л у) < в(зо Л уа). Автором этого вывода является У.
Шокли (%~. воск)еу).] 23. Пусть х» ж 1 тогда н только тогда, когда р» >,1', 9» = 1 тогда и только тогда, когда р» > 71 Отсюда (кп)» - -1 тогда и только тогда, когда (рп)» > 7', и т. д, 24. Формула для!,' очевидна, а дли 1] выберем э = х Л р, как в указании. Обратите внимание на то, что из упр. 21 следует, что (эа)» = (эа)» = О. Добавление дополнительных едипнц к г доказывает существование перестановки р, такой, что (рп')» <»(э), как следует из результатов упр.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
