Д. Кнут - Искусство программирования том 3 (2-е издание) - 2001 (Часть 2) (1119371), страница 83
Текст из файла (страница 83)
Обратно, если Х < !+ 1, то пусть !с внешних узлов находятск на уровне ! и ««' — Й узлов — на уровне 1+ 1, где 0 < Й < !««'. Как показано в упр. 2.3.4.5-3, Й2 ' + (ь7 — Ь)2 ' ' = 1; следовательно, «««+ Ь = 2'+«. Из неравенств 2' < ««' < 2«ы вытекает, что ! = (!8««'); отсюда определяется значение Ь«а также получается двина внешнего пути (34). 21. Пусть г(х) — корень правого поддерева узла х. Все подлеревья будут иметь минимальную высоту тогда и только тогда, когда ! !81(!(х)) ) < ! !8 С(х)) — 1 и ! !81(г(х)) ! < ) !8 г(х)~! — 1 для всех х. первое нз них эквивалентно условию 21(!(х)) — «(х) < 2 ««е «ы«! -!(х), а второе — условию !(х) — 2!(!(х)) < 20ак*«! — Г(х). 22.
Согласно упр. 20 четыре условия, (!81(!(х))), (!81(г(х))) > (!81(х)) — 1 н (!8«(!(х)Ц, (!81(г(х))! < ()8«(х)) -1, необходимы и достаточны. Рассуждая, как в упр. 21, можно доказать, что они эквнва«юнтяы сформулированным в условии этого упражнения неравенствам. (См. Ыш«!и Бапбейпэ, АММ 68 (1961), 133-134.) Распространение этого решения на общий случай приводится в упр. 33, 23. При сортировке посредством вставок в несколько списков предполагается, что ключи равномерно распределены в известном диапазоне, значит, он не принадлежит к числу методов "чистых сравнений", удовлетворяющих ограничениям, которые рассматриваются в этом разделе. 24. Действуйте сначала, как прн сортировке пяти элементов, до тех пор, пока не яолучнте одну нз конфигураций (б). В первых трех случаях завершите сортировку пити элементов при помощи еще двух сравнений, после чего вставьте шестой элемент у.
В последнем случае нух«но сначала сравнить Х:Ь, вставить Х в главную цепочку, а затем вставить с. (Р!саг«), ТЬеог«е «!ез Яиеьг!оппа«гец рабе Пб.) 25. Поскольку ««« = 7! = 5040 и «7 = 13, было бы 8192-5040 = 3152 вне«пних узла на уровне 12 н 5040 — 3152 = 1888 внешних узлов на уровне 13. 26. В работе 1.. Ко!!4г, Хессиге №«еэ !и Сошр. Яс«1 233 (1986), 449-457, представлен прекрасный способ проверки утверждения, что оптимальный метод сортировки дает путь длиной 62 416.
27. Это единственный способ распознать две наиболее часто встречающиеся перестаиовки за два сравнения, несмотря на то что первому сравиеиию соответствует разбиение с вероятностью .27/.73. 28. Луиь Куань (1лш Кэцл) составил программу длииой 873 строки, средиее время работы которой равна 38.925и. Максимальное время ее работы равно 43и; по-видимому, ово оптимально, поскольку как раз столько времени требуется для выполнения 7 сравнений, 7 проверок, б загрузок и 3 записей в память.
29. Не выполнив В(и) сравнений, невозможно дать однозначный ответ, какой является перестановка: четной или иечетиой. В самом деле, если предположить, что в результате выполнения некоторого числа сравиеиий мы 'сузили" задачу до такой степени, что осталось всего два возможиых исхода в зависимости от того, будет ли а; меньше или больше ау, где г и з — некоторые индексы, то один из этих возможных исходов — четная перестановка, другой — нечетная. (С другой стороны, для решения этой задачи сугкесшеуега алгоритм с временем работы 0(п); он просто подсчитывает количество циклов и вовсе ие содержит сравнений; см.
упр. 5.2.2-2.) 30. Возьмите оптимальное дерево сравиеиий высотой Я(п) . Двигаясь сверху вииз, мекайте местами 1 е+ 2 в правом поддереве узла г':11 В полученном дереве, которое интерпретируется как дерево сравнений-обменов, каждый концевой узел определяет единственную перестановку, а ее можно рассортировать ие более чем за л — 1 дополнительных сравнений- обменов (это показано в упр.
6.2.2-2). (Идея дерева сравиений-обмеиов прииадлехгит Т. Н. Хиббарду (Т. К. Н)ЬЬахб).] 31. Необходимо ие менее 8 сравнений-обменов, поскольку в любом дереве ь с высотой 7 существует ветвь, которая после 4 шагов приведет к конфигурации, где а Ф 1 (иля двойствеииой по отношению к ией).
Эту коифигурацию иельзя рассортировать за три операции сравиеиия-обмена, С другой сторонм, ниже показано дерево, на котором достигается искомая нижняя граница оценки (а также, быть может, миицмальиое среднее число сравнений-обменов). но ЗЗ. К любому дереву порядка х с разрешением 1 можно применить простую операцию для получения другого дерева, длина взвешевпого пути которого пе превышает длины пути ишсодссаго дерева, причем: (а) существует такое число й, что все внешние узлы лежат на уровпях й и я — 1, (Ь) ие более чем один внешний узел содержит нецелое значение, и если таковой имеется, то оп находится ла уровне (с, Длина взвевсеппого пути любого такого дерева имеет указанное значеиие, так что аяо должио быть минимальным. Обратно, если в веществепиозяачном дереве поиска выполпяютсл условия (Ь ) и (с ), то, применив яидукцию, момспо покшвать, что длина взвешепкага пути имею указанное значение, поскольку для этого параметра существует простая формула, выражающая ее через двины путей двух поддеревьев корни.
35. Ключ к решению этой задачи содержится в безуспешных экспериментах, описанных в работе КппСЬ, КаеЬ(ег, 1п(агтабов (вгосешспб (енсгв 1 (1972), 173-176. 36. См. Математические заметки 4 (1968), 511 — 518. Обзор достижений в решении этой задачи представлеи в работе Я, ге!впег, %. Т, Тсасссг, Сот бшасопсв, с=ав( Егс(бз и Е(ЗЬСу 1 (1993), 145-157. Тюв же доказано, что мы всегда можем получить 1 < Т(Ос)/Т(Ов) < р, где константа р чуть-чуть меньше 8/3. РАЗДЕЛ 5.3.2 1. Я(ш + и) < Я(ш) + Я(п) + М(ш, и). 2. Виутреиний узел, который является (с-м по счету при отношении порядка, симметричиом к исходному, соответствует сравнению Ас: Вв. 3.
Стратегик В(1,() пе лучше стратегии А(1, (+1), а стратегия В'(1,() ие превосходит стратегии А'(1, (-1). Следователыю, нужно разрешить рекурреитпсе глотнпшенке .М.(1,п) = шсп гаах(шах(1+.М.(1,(-1)), шах(1+.М.(1,п — ())), и > 1; с<1< сйсбс ' '1<с< .М.(1,9) = О. Нетрудно проверить, чта этому соотношению удовлетворяет решение (18(п + 1Ц. 4. Нет (см, С, СЬгВсеп, КОСЯ 19 (1978), 259-266), 6.
При у = с + 1 можно воспользоваться стратегией А'(с, с+1), за исключением случая с < 2. При у > с + 2 момсно применить стратегию А(Ь с+2), 7. Чтобм вставить й + ш элементов в последовательность и других элементов, вставьте независимо (с элементов и св элементов. (Если (с и т велики, то можно применить более совершенную процедуру; см. упр. 19.) 8.
На следующих диаграммах с:У означает сравнение А,: В,; через Мо обозначено слияние с элементов с у элементами за М(с, у) шагов, а через А — сортировка конфигурации ~~ или,Д. 'за три шша, вв св Мы Мш Мсв+1 А Мы Мсв+1 резво Мы+1 М1з+3 11. Воспользуемся указанием: положим и = дь Можем считать, что 3 > 6. Без потери общности можно первым сравнением сделать Аз:В».
Если г > д, », то исход Аз < В» потребует еще > 1 шагов. Если .з < д»», та исход А» < В» не вызовет трудностей, н поэтому необходимо исследовать лишь случай Аз > В.. Больше всего информации мм получаем при г' = д» ь Если Г = 2Ь + 1, то можно было бм слить Аг с д» вЂ” д»» = 2" элементами, превьппающими В, „и слить А» с остальными д»» элементами, на для этого понадобилось бы еще Ь + (Ь + 1) ы» шагав. С другой стороны, если и = у~ — 1, то можно было бы слить Аз с 2» ' — 1 элементами, а затем А, — с и элементами еще за (Ь вЂ” 1) + (Ь + Ц шагов. Следовательно, М(2, д»-1) < к Случай Г = 2Й значительно сложнее; обратите внимание на то, что д» вЂ” у»-» > 2" Предположим, что если Аз > В», „то мы будем сравнивать А».В..
Если» ) 2~ ', то исход А» < Вт потребует еще Ь+(Ь вЂ” 1) сравнений (слишком много). Если д < 2" ", то можно, как и раньше, доказать, что выбор д = 2з ' даст больше всего информации. Б случае А» > Взз-» можно было бы сравнить также А» с Взз-»+зз-з, затем с Вгз-» гз-згзз-з, 'поскольку 2з ~+2з з+2" з > у»-цостаетсялишь слить (А1,А») си — (2з '+2" г+2" з) элементами, Разумеется, вовсе не обязательно сразу же выполнять какие-либо сравнения с Ац можно вместо этого срэлнить Аз:В„е» . Если з < 2 з, то рассматриваем случай Аг < В +»-», если же д > 2» з, то РассматРиваем Аз > В„+» зь Этот последний счУчай тРебУет ензе не менее (Ь вЂ” 2) + (Ь + 1) шагов. Продолжая рассуждение, обнаруживаем, что единственный потенциально плодотворный путь — это Аз ) В...
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
