AOP_Tom3 (1021738), страница 197
Текст из файла (страница 197)
Значит, до(г) имеет внд ба(х)/(1 — г) и о1а~ = йд(1), поскольку бд(1) ф О и бег(1 — А) т О для [г[ < 1. РАЗДЕЛ 5.4.7 1. Выполняйте сортировку от младших цифр к старшим поочередно в системах счисления с основанниями Р и Т вЂ” Р. (Если сгруппированы пары цифр, то получим, в сущности, чистое основание Р (Т вЂ” Р). Так, если Р = 2 и Т = 7, то система счисления — двоичнопятеричная, которая очевидным образом связана с десятичными обозначениями.) 2. Если К вЂ” ключ, находящийся в диапазоне от О до Рь — 1, то пусть фибоначчиевым представлением Ä— 1 — К будет а„гР„~ + + а~рг, где а, равны О или 1 и нет двух последовательных единиц.
После фазы 1 на ленте (1 + 1) шос( 3 находятся ключи с аз = О, а на ленте (1 — 1) шаг) 3 — ключи с аг = 1 в порядке убывания значений а,-г... ао. [Представьте сортировальную машину длн перфокарт с карманами "О" и г1" и рассмотрите процедуру сортировки Г„карт, на которых перфорированы ключи а„г... аг в н-2 колонках. Обычная процедура их сортировки в порядке убывания, которая начинается с младшей цифры, может быть упрощена, поскольку все, что находится в кармане "1" в конце одного прохода, попадает на следующем проходе в карман "О".) 4. Если бы на уровне 2 находился внешний узел, то нам не удалось бы построить такое хорошее дерево. В противном случае на уровне 3 имеется самое большее три внешних узла, на уровке 4 — шесть, так как предполагается, что каждый внешний узел оказывается на одной и той же ленте.
т в 9 6. 09, 08, ..., 00, 19, ..., 10, 29, ..., 20, 39, ..., 30, 40, 41, ..., 49, 69, ..., 30, 60, б1, ..., 99. У. Да. Сначала распределяем записи во все меньшие и меньшие подфайлы, пока не получим файлы на одной бобине, которые могут быть рассортированы отдельно. Этот процесс является двойственным по отношению к сортировке файлов на одной бобине с последующим слиянием их во все большие и большие файлы на нескольких бобинах. РАЗДЕЛ 5.4.8 1. Да. Пусть направления файла и дерева выбора чередуются от возрастающего к убывающему, тогда в результате получим шейкср-сортировку Р-го порядка (см, упр.
9). 2. Пусть Ял = Уп — Лл", решим рекуррентные соотношения для Ян, заметив, что следовательно, /М+21 l ли=1(Х+ ц+( )) Аг(Х вЂ” ц приХ)М. 3 Теперь исключим Ун и получим Хл 20 / 1 1 — = — (Н,, — Им, з)+г( — — — ) А+1 3 ' '1А'+1 М+2У 1 1 3М+4 3 ~ 3 ! ~(А'4 ЦА'(Л'-Ц (М+г)(М+ЦМ)+ М~-г ' 3. Да.
Найдите элемент, который является медианой, за 0(Х) шагов, используя построение, аналогичаое приведенному в теореме З.З.ЗЕ, и с его помощью разделите файл. Еще один интересный подход, предложенный Р. У. Флойдом (К. % Р!суй) и Э. Дж. Смитом (А. 3. Яписб), состоит в том, чтобы слить две серии из Ж элементов за 0(Ю) единиц времени следующим образом.
Раздвиньте элементы на ленте, оставив между ними промежутки, затем последовательно занесите в каждый такой промежуток число, которое определяет конечное положение элемента, предшествующего этому промежутку. 4. Можно объединить график для этажей (1,..., р+1) с графиком для этажей (9,..., и): когда по первому графику лифт впервые достигает этажа р + 1, то подняться на этаж 9 и действовать в соответствии со вторым графиком (считая текущих пассажиров лифта "дополнительными" людьми в алгоритме теоремы К), После выполнения этого графика вернуться на этаж р+ 1 и возобновить прежний график. Ь. Рассмотрим Ь = 2, ш = 4 и следующее поведение алгоритма.
э: — — — ~л 5667 4566 э э. — ю — — ~и — ~% 5667 2345 э . — — — 7» — —.э» 5667 1234 2345 э э: — — ~» — — — — — ~Ф» 5566 Этаж 3: — 63 — — +23 2556 Этаж 2: — 62 — +00 0055 Этаж 1: — 55 — +00 0000 I Теперь 2 (в лифте) меньше, чем 3 (на третьем этаже). (После построения примера, подобного этому, читателю должно быть ясно, как установить справедливость более слабого свойства, используемого в доказательстве теоремы К.) б. Найдем миннмалыэые г, 7, такие, что Ь, < Ь', и Ь, > Ь'.
Введем нового человека, который хочет переехать с этажа г на этаж 71 При любом й это не увеличит игах(иэ, э1эч м 1) или шах(Ьэ, Ь'„). Продолжим процесс, пока не получим 6 = 6' при всех у. Теперь заметим, что алгоритм в тексте раздела, если изменить Ь на Ьэ на шагах К1 и КЗ, по-прсжнему работает. 8. Пусть их число будет Р» и пусть сх . число перестановок, для которых иэ = 1 при 1 < й < и. Тогда Р» = ЯгР„г + с)гР» г + .. + О„, Рэ, Рэ = 1. Можно показать, что 1л е= 3 при и > 2 (см. ниже), поэтому, используя производясцие функции, получим »-г Р„г" = (1 — Зх)/(1 — 4г + 2хг) = 1 + х + 2гг + бгэ + 20гэ + 68хэ + 2Р.
= (2+72)" '-ь(2 — Г2)" '. Чтобы доказать, что Я» = 3"' ', рассмотрим тернарную последовательность хгхг... х, такую, что гхп — — 2, х„= 0 и 0 < хь < 2 при 1 < й < и. Следующее правило определяет взаимно однозначное соответствие между такилэи последовательностями и требуемыми перестановками агаг...аэ, аэ= й, шах(7((1<йнлих =0)или7'=1), еслихэ=О; если хь = 1; ппп(3 ! (у > й или х, = 2) или 1' = н), если хэ = 2. (Это соответствие было получено автором совместно с Э. Л.
Бендером (Е. Л. Всвдсг).) О. Число проходов шейкер-сортировки равно 2 птах(иы..., и»)-(О или 1), так как каждая пара проходов (слева направо, справа налево) уменьшает каждое ненулевое и на 1. 10. Начните с какого-нибудь метода распределения (быстрая или обменная поразрядная сортировка), пока не получатся однобобинные файлы. И наберитесь терпения. РАЗДЕЛ 5.4.9 1. -' — (х гвоэ( —.' ) оборотов. 2. Вероятность, что й = а, и й+ 1 = а, „для фиксированных й, д, г и г ф г' равна 1'(д, ц й)1151(РЬ вЂ” 2г')ЯРТ)!, где 9.
Пусть е! минимизирует (от+ Б)/!от, Рассуждение по индукции с использованием ири этом выпуклости показывает, что Аз (и) > (о»!+Б) и !ок, и, причем равенство наступает при и = »7~. Соответствующая верхняя оценка получается из полного «1-арного дерева, поскольку в этом случае В(г) = г!Е(г), Е(т) = гп+»!г при и = »!'+ (»! — Цг, 0 < т < е!'. 10. См. БТОС 6 (1974), 216-229. 11. Из результата упр. 1.2.4-38 следует /,„(и) = 34й+ 2(й-3»т), когда 2 3» ' < и/т < 3»; /~(й) = Здп+ 4(й — 3»т), когда 3» < й/»и < 2 3». При этом /з(й) + 2й > /(и), причем равенство выполняется тогда и только тогда, когда 4 3» ' < и < 2 3»; /з(п) + Зп = /(и); /»(и) + 4й > /(й), равенство выполняется тогда и только тогда, когда и = 4 3»; и / (и) +»йп > /(п) для всех т > 5.
12. Используйте спецификации —, 1 1, 1 1 1, 1 1 1 1 ог 2 2, 2 3, 2 2 2, ..., [и/3) [(й+1)/3): [(»з+ 2)/3), ...; при этом получаются деревья со всеми листьями на уровне д+ 2, где 4. 3» < и < 4 3»+'. (Если й = 4 3», формируется два таких дерева.) 14. Следующие спецификации деревьев были построены для случаев и = 1, 2, 3, посредством исчерпывающего просмотра всех разбиений и: —, 1:1, 1:1:1, 1:1:1:1, 1:1:1:1:1, 1:1:1'1:1:1,1:1:1:1:3,1:1:3:3,3:3:3,1:3;3:З,З:4:4,3:3:3:З,З;3:3:4,3:34:4,3:4.4:4,4:4;4:4,..., 5:б:б:б:12, б:б:б;6:12, б:б:б:б;13,,... (По-видимому, степени всегда < 5, но доказать это утверждение довольно сложно.) 15. Если первоначально в лифте находятся а человек, то при первой остановке оценка совместности возрастет не более чем иа а+ Ь.
При следующей остановке оценка возрастет не более чем нз Ь+ т — а. Значит, после Ь остановок оценка возрастет не более чем на !»Ь+ (!» — 1)т, 16. 11 остановок: 123456 на этаже 2, 334466 на этаже 3, 444666 на этаже 4, 256666 на этаже 5, 466666 на этаже б, 12344Б на этаже 4, 11233Б на этаже 5, 222333 на этаже 3, 122225 иа этаже 2, 111555 на этаже 5, 111111 на этаже 1. [Это минимум. Результат дли 10 остановок при произвольной вместимости лифта может иметь следующий вид, Остановки на этажах: 2, 3, 4, 5, б, рз, рз, р», рз, 1, где рзрзр»рз есть перестановка множества (2,3,4,5).
Такой график движения возлюжен только при Ь > 8. См. Мшбп Оегдпег, Кпоеее»! ВопбЛлпез (Ь!ез» Ъогрс Ггеешап, 1986), СЬареег 10.[ 17. Существует по меньшей мере (Ьп)(/Ь!" конфигураций; число, которое может быть получено из некоторой заданной конфигурации после з остановок, не будет превышать ((й — 1) [~ез )) ' ', что меньше, чем (й((Ь+ т)е/Ь) )', полученное в упр. 1.2.6-67. Следо- вательно,' некоторая конфигурация требует з(1ай+ Ь(1+ !П(1 + т/Ь))) > )п(Ьй)! — й!ПЫ > Ьй(ПЬй — Ьй — й((Ь+ Ц ЬзЬ- Ь+ 1), как следует из упр. 1.2.5-24.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
