Д. Кнут - Искусство программирования том 3 (2-е издание) - 2001 (Часть 2) (1119371), страница 94
Текст из файла (страница 94)
Аналогично дерево типа ю(А, С) можно образовать из и(В, А) и е(С, А) Дерево из упр. 7 есть г(.4)-дерево, построенное этим способом.[ Пусть г(н),..., ю(п) обозначают минимальную длину внешнего пути среди всех деревьев соответствующего типа с н-листьями, построенных с помощью такой процедуры. Имеем г(1) = з(1) = а(1) = О, г(2) = Ф(2) = ю(2) = 2, 1(1) = е(1) = ю(1) = з(2) = н(2) = е(2) = оо, Для и > 3 имеем Чтобы перейти с уровня я на уровень п+ 1 во время начального распределения, введите л» "подуровней", в которых на ленты (Т1, Т2,..., Т5) добавляется соответствеипо (4, 4, 3, 2, 1) серий 1»т "подуровней" с (4,3,3,2,1) сериями, 1»з — с (3,3,2,2,1), к» вЂ” с (2,2,2,1,1), е» вЂ” с (1,1,1,1,0) сериями, где л» < а, лт < Ь, лз < с, 1»» <»1, х» < е„.
(Если (ям..., Й») = (а,..., с„), значит, достигнут уровень п + Ц Добавьте фиктивные серии, если необходимо дополнить подуровень. Затем выполните слияние я» + 1»т + йз + 1»» + яе серий с (Т1,..., Т5) на Тб, й» + -. + Ус» серий с (Т1,..., Т4) на Т5, ..., серии й» с Т1 на Т2, 1»1 — с (Т2,..., Тб) на Т1, хх — с (Т3,..., Тб) на Т2, ... и к» вЂ” с Тб иа Т5. 18. (Решение предложено М.
С. Патерсоном (М, Б. Рагешоп).) Предположим, запись 1 помещена в последовательность на ленте номер т;. По меньшей мере, С)т( записей могут иметь данную последовательность т, где С зависит от объема внутренней памяти (см, раздел 5.4.3). Следовательно, (т»)+ + (тл) = й(Х!обтЛ'). 19. 20. Сильное Т-Ио-дерево имеет У-йто-расстановку меток, в которой нет трех ветвей, имеющих вид соотве»ственно А, А или А, А или длв некоторого имени ленть» А и некоторых» < 1 < 1» < 1 < и Неформально, чтобы "вырастить" некоторое А, необходимо вырастить все остаиьные деревья А до создания какого-либо нового А. 21, И 22.
Это действительно для любого представления в виде дерева, образуемого последовательной заменой всех вхождений, например заменой на для некоторых фиксированных имен лент А, В, С, )У. Так как вхсэкдения заменяются по одному н тому же образ)1т, порядок (ДГО илн Р(РО не вызывает различий в структуре дериш. Сформулируем это условие в терминах векторной модели: всякий раз, когда (р) "+)) ~ рщ) илия=в))ир()=-1,имеемр()+ . +р))+р()жО.
) ) ) 1 23. (а) Пусть в) < «э « - ит; "каскадная" стадия которая превращает С(о) в в. (Ь) Очевидно, так как С(е)ь < С(ю)э при всех (г. (с) Если В ПОЛУЧЕНО За О СтадИй, тО ИМЕЕМ и -) ВО) -) ° -) ВЫ) ы В дпя НЕКОТОРОГО ЕДИНИЧНОГО вектора в и некоторых других элементов вп), .... Следовательно, и~~) -С С(в), в~~) -~ С(С(и))... и < Сй)(к) и о)+ . +вт меньше нлн равно сумме элементов СО)(и); последнее достигается при каскадном слиянии. (Эта теорема обобщает результат упр. Ь.4.3-4; к сожалению, понятие "сткяии", как оно определено здесь, не имеет, по-видимому, пнкахой практической ценности,] 24. Пусть р~ )... рр+)) будет стадией, которая переводит ш в о.
Если р)0 = -1, р)) П О, ,, р; = О я р) ) = -1 для некоторого )) < ( — 1, то можно вставить ры) между рп) н (Й+1) ы) рб '). Повторяем эту операцию, пока асе (-1) во всех столбцах не станут соседннмн. Тогда, если р)р О н р ' Ф О, можно положить и,"') г- 1; в конце концов, все столбцы будут состоять нз +1, за которымк следуют -1, а за нинн — О. Таким образом, стадия, которак переводит ю' в в для некоторого ю' )- и, построена, После перестановки столбцов эта стадия пршгямает янд (1,..., 1, -1)" г...
(1, -1, О,..., О)'э(-1,0,..., О)". Последовательность, состоящая из Т вЂ” 1 соотношений (хм ..,, хт ) < (х) + хт,, хт ) + хт, О) < (х1+хт-)+хт,...,хт-э+хт-1+хт,хт,б) "с (х~+хт-э+хг-)+хт,..., хт-э+хт-э+хт- +хг, хт 1+хт, хт, 0) .< (х~+хэ+хз+-'+хт, хз+ .+хг,, хт ~+хт,хт, 0), показывает теперь, что наилучший выбор величин а есть ат = от, ат-) = стчм оэ = вэ, а) = О. Результат является оптимальным, если переставить столбцы так, чтобы выполнялось щ « .
вт. 23 (а) Предположите, гг„) вт ь+) » . ° ет > щ » . вт ь и исшшьзуйте (1,, 1,-1,0,...,0)"™+'. (1, ",110," 0~-1) (Ъ) Для 1 < 1 < Т вЂ” )г сумма наибольших 1 элементов )уг(о) равна (1 — 1)за + эь+) (с) Если в Ю ш в фазе, использующей х выводных лент, то можно, очевидно, очи)ать, что эта фаэа имеет ввк (1,..., 1, -1, О,, О)"' ..
(1,..., 1, О,..., О, -1)'", причем каждая нз остальных Т вЂ” й лент используется как вводная во всех операциях. Выбор о1 = иг-ь+)..., оь = вт является наилучшим. (0) См. упр. 22, (с). Всегда имеем 51 = 1; я = Т вЂ” 2 всегда лучпае, чем Ха = Т вЂ” 1, так как предполагается, что, по крайней мере, одна компонента вектора и равна нулю.
Следовательно, для т = 3 имеем 121... 54 = 14 и начальное распределение (Ра+1, Ра, 0). Для т = 4 найденьа следующие недоминирующие стратегии и соответствующие распределения, 4=2 12 (3,2,0,0) 4= 3 121 (5,3,3,0); 122 (5,5,0,0) 41 = 4 12П (8,8, 5, О); 1222 (10, 10, О, 0); 1212 (11, 8, О,О) 4 = 5 12121 (19, 11, 11, О); 12222 (20, 20, О, 0); 12112 (21. 16, 0,0) , д = б 122222 (40,40,0,0); 121212 (41,30,0,0) 4> 7 124 ' (5 24 2,5.24 2,0,0) Таким образом, для Т = 4 и 4 > б слияние с минимальным числом фаэ подобно сбаланси- рашаниому слиянию с незначительными искажениями в самом коаще (переход от (3, 2, О, 0) к (1, О, 1, 1), а не к (О, О, 2, 1) ).
Когда Т = 5, недоминирующими стратегиими являются 1(32)" '2, 1(32)" '3 для д ы 2п > 2; 1(32)" 132, 1(32)" '22, 1(32)" '23 для д = 2п+ 1 > 3. (Первая стратегия имеет в своем распределении наибольшее число серий.) На шести лентах они таковы: 13 нли 14, 142 нли 132 (либо 133), 1333 или 1423 и 134 ' для 41 > 5. Т1 Т2 А1 А1А1 — А1 — А1 Х12 Х]2А1 А1 Х22 — Аа Т1 Т2 А1 Аа — Аа[)2 А4 Аа А4 АаА1 А4 Х41 А4 Аа АаА1 — Аа РАЗДЕЛ 5.4.5 1. Следующий алгоритм управляется массивом а[Х вЂ” 1] .. 4[1]а[0], который, в сущно.
сти, представляет число, записанное в системе счисления с основанием Р. Мы многократно добавляем единицу к этому числу; "переносы" говорят нам, когда следует выполнить слияние. Ленты пронумерованы от 0 до Р. О1. (Начальная установка) Присвоить (а[Х -1],...,4[0]) 4- (О,...,О) и 4 а- О. (Во время выполнения этого алгоритма 4 будет равно (1[Х-1] + ° + а[О]) шоа(Т ) О2.
(Распределение.] Записать начальную серию на ленту 4 в порядке возрастания. Установить 1 4- О, Ой, Добавить единицб.] Если 1 = Б, остановиться; результат находится иа ленте (-Х) шоб Т в порядке возрастания тогда и только тогда, когда Х, чепю. В противном случае установить аП] 4- 1 П] + 1, 4 а- (д + 1) шо41 Т.
О4. (Переносу] Если 1[1] < Р, то вернуться к шагу О2. В противном случае выполнить слияние на ленту (41 — 1) шойТ, установить 1[1] 4- О н 4 4- (4+ 1) шоа(Т, увеличить 1 на 1 и вернуться к шагу 03. $ 2. Следите эа числом серий на каждой ленте. Когда исходные данные будут исчерпаны, добавляйте, если необходимо, фиктивные серии, пока не придете к такому положению, когда на каждой ленте будет находиться максимум одна серия и по крайней мере одна лента не будет занята.
Затем завершите сортировку посредством шце одного слиянии, перемотав сначала некоторые лепты, если это необходимо, (Ориентацшо серий можно извлечь из массива 1.) 3, Операция ТО Операция ТО Распределение Распределеняе [22 А1 Слияние Пэ Слияние Х]2 Распределение Х42 А1 Слияние Слияние Х)2 Распределение Распределение Х]2 Копирование Слияние ]42 Х12 Копирование Слияние ХЬ Слияние Х12 В этот момент Т2 можно перемотать — и окончательиое слияние завершит сортировку. Чтобы избежать бесполезных операций копирования, при которых серии просто сдвигаются вперед или казал, можно в конце шага ВЗ просто сказать "'Если исходные даяиые исчерпаны, перейти к В7" и добавить новый шаг.
В7. [Завершение.) Установить э е- — 1 и перейти к 32 после повторения следующей операции до тех пор, пока 1 = О. Установить э' +- 4 П вЂ” 1, о) и установить о' и г' равными индексам, таким, что 4П вЂ” 1,4') =- -1 и 4 [1 — 1, г') = — 2. (Мы получим 4' ж г и в' < 4П вЂ” 1,Я < э'+ 1, 1 14 4', у Зэ т'.) Если э' — э нечетно, продвинуть уровень 1, в противном случае — откатить его (см.
ниже). Затем выполнить слияиие на лепте г, читая в обратном порядке; установить 1 е- 1 — 1, 4 [1, 43 < — -1, 4[1, г) +- э' + 1, г е- Р и повторить. Здесь "продвижение" означает повторение следующей операции до тех пор, пока (4+ (-1)') щи Т = г: установить р е- (о+ (-1)') пик1 Т и скопировать одну серию с лепты р н» ленту 4, затем установить 4 [1, 4) +- э+ 1, 4 [1, р) е- -1, 4 4- р. "Откат" уровня означает повторение следующей операции до тех пор, пока (д — (-1)') щи Т = г: установить р +- (4 — (-1)') шоп т и скопировать одну серию с ленты р иа ленту о, затем установить 4 [1, 41 +- э, 1[1,р) 4- — 1, 4+- р.
При операции копврования чтение с ленты р выполняется в обратном направлении, в результате чего направление копируемой серии изменятся на противоположное. Если окажется, что при копировании с р иа 4 11[р) > О, то нужно вместо копирования просто уменьшать Р[р) и увеличить В[4). (Основная идея состоит в том, что, если входные данные исчерпаны, желателъно исключить, по крайней мере, по одной серии на каждой ленте, Разряд четности каждого неотрицательного элемента 4[1,Я укажет, является ли серия восходящей или иноходи~пей.
Наименьшее Я, при котором измеиение алгоритма хоть как-то сказывается, есть Р + 1. э Если Р велико, такое изменение вряд ли когда-нибудь вызовет болъшое рэсхождеиие, но оио позволит компъютеру не выглядеть слишком глупо при некоторых обстоятельствах. Одиано и этот алгоритм можно еще дорабатывать, чтобы более эффективно обрабатывался случай Я = 1.) 4. На самом деле можно опустить установку 4[0, 03 иа шаге В1 и 4[1,43 на шаши ВЗ и В5. (Однако 4 [1, г) долоюно устанавливаться на шаге В8,) Новмй шаг В7 в ответе к предыдущему упражнению требует значение 4 [1, д) (если только в явном виде ие учитывает, что 4' = г, как отмечается в указанном ответе).
б. Ры — (Р— 1)Ры э < Я < Ры прк некотором й > О. РАЗДЕЛ $.4.6 1. [23000480/(и + 480) [ и. 2. В этот момеит все записи правого буфера переданы па вывод, На шаге Р2 во время слиявия проверка "Полон ли буфер вмвода7" предшествует проверке "Пуст ли буфер ввода?"; это существенно, иначе пришлось бы ввести дополнительные проверки (если ие внести изменеияя, как в упр. 4). 3. Нет.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
