Д. Кнут - Искусство программирования том 3 (2-е издание) - 2001 (Часть 2) (1119371), страница 96
Текст из файла (страница 96)
А. Бендером (Е. А, Вевбег).) й. Число проходов шейкерсортировки равно 2 шах(ип..., нэ)-(О илн 1), тнк как кахгдая пара проходов (слева направо, справа налево) уменьшает каждое ненулевое н на 1. 10. Начните с какого-нибудь метода распределения (бмстрая илн обменная поразрядная сортировка) „пока не получатся однобобинные файлы. И наберитесь терпения. РАЗДЕЛ 9.6.9 1. 7 — (х шод -') оборотов.
2. Вероятность, что й = ам н й + 1 = о, „, для фиксированных Ь, о„г и 1 ф 1' равна Р;,, ) ' (Ра- )Кра)( д ~й -1~ ~5-9~ ~Р7, — 5 — 1~ ~Р5- й — 1-5+9~ ( 5 — 1 ) (9+ г — 2) ~РЬ вЂ” Й вЂ” 1)(25-9 — г) к — ')=к -"1" )(","')(' ')=(" )"-- «<э<го «<ь ° «ь Ь-9 2Ь-1 «««, <с Вероятность того, что к = а, и к+ 1 = 90 +М, Длк фиксированных 1«, 9 и «равна 9(5,9)/( ), где 9(/с,9) = ( ) ( ), Х К (Ру — 1) ( ~РŠ— 1) 1<«<з ]ЯСОМР 1 (1972), 161-166.] 3.
Найдите минимум в соотношения (5) иа интервале 2 < т < гпш(9, я). 4. (а) (О 000725(чР+1) +О 014) Х. (Ь) Замените "птп+Щ' в формуле (5) выражением "(О 000725(з/т+1)«+О 014)п! [" Натурные" эксперименты на компьютере показывают, что оптимэльиые деревья, определяемые этими соотношениями, весьма напоминают деревьи, которые определяются теоремой К при и = 0.00145, Д = 0.01545. Фактически существуют деревья, оптимальные для обоях рекуррентных сост>оп«ений, если 30 < и < 100.
Предложенное выше измеиеиие позволяет экономить около 10««времени сляяияя при условии, что и = 64 или 100, как в примере, который рассматриватся в основнои тексте раздела. Такой способ распределения памяти для буферов рассматривался еще в 1954 году Х. Сьювордом, который показа«, что 4-путевое слияние позволяет мииимизировать время пояска.] 5. Пусть А (и) и В (и) — стоимости оптимальных иаборов п«деревьев, и листьев которых находятся соответственно на четных и нечетных уровнях. Тогда А«(1) = О, В«(1) .= а+1); А (и) и Вм(п) опРеделеиы, как в (4), пРи т > 2; А~(п) = пап««(ат««+ Вя+ В (и)), В~(п) = пил~~, <„(спля+ бп+ А (и)). Последние уравнения корректны несмотря иа то, что А«(««) и В«(««) определяются друг через друга! 6. А«(23) = В~(23) = 268.
]Интересно отметить, что и = 23 есть единственное значение, меныпее или равное 50, при котором никакое дерево с и листьями равной четности не является оптимальным в случае, когда нет ограничений иа четкость. Возможно, это сдинсшеениое такое значение, когда а = 1Ц 7. Для некоторого дерева рассмотрям величины пА + Дсп ..., ш$, + Де«, где бэ сумма степеней пути и е, — есть длина пути для у'-го листа Для оптимального дерева с весами ш~ < ° < ш„будет выполняться иеравевство а«(«+,9с~ > - > о«(„+ Де„, Всегда можно переупорядочить индексы так, что ой~ + Де« = . = а«(«+бе«, где первые й листьев сливаются эместе. 9. Пусть И минимизирует (аж + 11)/1вна Рассуждение по индукции с нспользоеаняем при этом выпуклости показывает, что А~ (а) > (ш1+/1) и Ый, а, причем равенство наступает при а = Ы'.
Соответствующая верхняя оценка получается из полного 4-арного дерева, поскольку в этом случае 7у(г) = ЫЕ(т), Е(г) = Еа + ~6. при а = И' + (й — 1)г, 0 < г < е1'. 10. См. ЯТОС 6 (1974), 216-229. 11. Из результата упр. 1 2 4-38 следует / (а) ы Зев+2(а-Зеш), когда 23е ' < а/т < 3', / 4(а) = Зйа + 4(а — 3'та), когда Зе < а/га < 2.
3'. При этом /г(п) + 2а > /(а), причюе равенство выполняется тогда и только тогда, когда 4 3" ' < а < 2 3', /е(а) + За = /(а); /е(а) + 4а > /(а), равенство выполняется тогда и только тогда, когда а = 4 Зе; и /»(а) +та > /(а) для всех т > 5. 12. Испцяьзуйте спецификации —, 1:1, 1:1.1, 1:1:1:1 ог 2:2, 2:3, 2:2:2, ..., (а/3):((а+ 1)/3): ((а + 2)/3), ...; прн этом получаются деревья со всеми лнстьямн на уровне 9+ 2, где 4 Зе < а < 4.
Зе+'. (Если а м 4 Зе, формируется два таких дерева.) 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;3, 3:4:4, 3:3:3:3, 3:3:3;4, 3:3:4:4, 3:4:4:4, 4:4:4:4,..., $:б:б:б:12, б:б:б:б:12, б:б:б.б:13, .... (По-видимому, степени всегда < б, но доказать это утверждение довольно сложно.) 1$. Если первоначально в лифте находятся а человек, то при первой остановке оценка совместности возрастет не более чем на а+ Ь, При следующей остановке оценка возрастет не более чем иа Ь+ ш — а.
Значит, после Ь остановок оценка возрастет не более чем на ЬЬ+ (Ь вЂ” 1)га. 16. 11 остановок: 123456 на этаже 2, 334466 на этаже 3, 444666 на этаже 4, 256666 на этаже 5, 466666 на этаже 6, 123445 на этаже 4, 112335 на этаже 5, 222333 на этаже 3, 122225 иа этаже 2, 111555 на этаже 5, 111111 на этаже 1. )Это минимум. Результат для 10 остановок при произвольной вместимости лифта может иметь следующий вид. Остановки па этажах: 2, 3, 4, 5, 6, ре, ре, ре, ре, 1, где ргре1еере есть ~врастая~в~а ~но~е~~ва (2,3,4,5), Такой график движения возможен только прн Ь > 8. См.
Матт1п Оегбвег, Клозет ВопбАлпш (Хше Уог)с Ргеепшп, 1986), СЬареег 10.) 17. Существуег по меньшей мере (Ьа)1/ЬР конфигураций; чнсю, которое может быть получено нз некоторой заданной конфигуриши после е остановок, не будет превышать ((а - 1)(е е )) ' ', что меньше, чем (а((Ь+ гл)е/Ь)е)', палученное в упр. 1.2.6-67. Следовательно,' некоторая конфигурация требует е(1в и+ Ь(1+ )в(1+ т/Ь))) > 1п(Ьа)! — а!пЬ! > ба1вЬа — Ьа — н((Ь+ 1) 1пЬ вЂ” Ь+ 1), как следует нз упр.
1.2.5-24. Замечение. Учитывая то, что 1/(е + у) > " гшв(1/л, 1/9), когда з и и положительны, можно выразить зту нижнюю оценку в более приемлемой форме: а1о8(1+а) )) Такой результат получен в работе А. Аббэгиа), Л. Б. Уййег, САСМ 31 (1988), 1116-1127, в которой также приводится соответствующая верхняя оценка: (~, ( и1 8(1+») )) Расширение этого решения для нескольких дисков описано в работе М. Н.
Хо61пе, Л, Я. Чйеег, АСМ Бушроашп оп Рагайе) А(еог1ейшз алй АгсЬЗесппш' $ (1993), 120-129. 18. Ожидаемое число остановок есть 1 ',>, р„где р, — вероятность того, что необходимо не менее е остановок, Пусть 9, = 1 — р,+~ — вероятность того, что необходимо не более в остановок. 'Гогда из упр. 17 следует, что 9, < /(е — 1+ [э = О)), где /(е) ы ЬГ'а'/(Ьп)! и и = п((Ь+т)е/Ь)'. Если/(1-1) < 1 </(1), то~,>,р > я~+ +ра =1-(4в+.
+Е-з) > С вЂ” (Ргп) +/(0)+ .. + /(1 — 2)) > 1 — (о'"'+о~"'+ +а ') >1 — 1 > 5 — 1. 19. Осущеспитя анализ, выполните шаг (тй) в обратном направлении, распределяя записи сначала в ящик 1, а затем — в ящик 2. Это именна та операция, которая моделируется в отношении файла ключей на шаге ((т).
[Ргэлсееоп Соп/егелсе оп 1айппшгэоп Ясилсеэ эпИ $уэгетз 6 (1972), 140-144.) 20. Следует серьезно отиестись и выбору метода внутренней сортировки, учитывая ограничения, которые иаклалываются страничной органиэацией. 'Гакие методы, как метод Шелла с уменьшением смещения, вычисление адреса, пирамидалъиая сортировка и сортировка списка, вряд ли приемлемы, если мэл реальный объем оперативной памяти, поскольку при их реализации потребуется большое число "рабочих страниц". Методы быстрой сортировки, обменной поразрядной сортировки и погледовательяо распределяемого слияния или поразрядной сортировки значительно лучше "себя чувствуют" в страничной среде. Существуют определенные нюансм, которые можно учитывать при создании алгоритмов внешней сортировки, но которые исключаются при использовании автоматической системы распределения страниц; (1) выбор иа основе предсказания файла исходных данных, который должен читаться следующим, чтобы нужные даняые оказались загруженными к тому моменту, когда в иих появится необхцпимость; (й) выбор размера буфера и порядка слияния в соответствии с характеристиками оборудования и данных.
С другой стороиы, виртуальиая машина зиачительно упрощает программирование и с ее помощью можно получить неплохие результаты, если программист работает аккуратно и учитывает возможности той реалыюй вычиглительиой системы, для которой разрабатывается программа. Первое достаточно полное исследование этой проблемы вмполиено Браун (Бгамп), Густввсоном (Ошаеатеоп) и Манкииым (МэпЫп) [САСМ 13 (1970), 483-494.) 21. [(Х -/)/Я; см. СМагЬ, формула (3.24). 22.
После считывания группы из П блоков, которые содержат а1, понадобится знать а еп ~ прежде, чем будет выполнено считмвание следующей группы из П блоков. Если хранить агеп ~ с а;, то понадобятся также значения ае, ..., ап е в виде иекоторого заголовка файла с тем, чтобы начать процесс. Но, следуя этой схеме, невозможно записать блоки ае...ап-~ до тех пор, пока ие будет вычислено ап... агп-э Таким образом, потребуется 577 — 1 выходных буфера вместо 2П для того, чтобы продолжительное время сохранять записываемую яиформацию. Отсюда следует, что лучше записать значения о в отдельный короткий файл.
[Такие же соображения можно привести и по отношению к рацдомизированному разделению.) 23. (а) Для реализации алгоритма 5,4,6г требуется 4 входпмх буфера, каждый объемом, соответствующим размеру суперблока 77В. (Если к этому прибавить еще и буфера вывода, то в сумме получитси 611В записей в буферах оператввиой памяти в случае использования алгоритма 5.4.6Р и 5Ю — в случае использования алгоритма БувсЯогд) (Ь) В то время, когда считывается группа из 17 блоков, нужно иметь в своем распоряжении пространство для буферов, чтобы хранить предыдущие 77 блоков и один незавершенный блок, т. е.
(217+ 1)В записей. (Пля вывода требуется еще 2ПВ, ио в результате многих операций обработки даиных в ходе выполнения 2-путевого слияиия на практике передается на выход сравнительно небольшой объем информации.) 24. Пусть 1-м блоком в хронологическом порядке будет блок 71 серии йь в частности.6 ш О и )п =1 при 1 < 1 < Р. Этот блок будет считываться в момент времеви 1~ = Х „,Х~ьз, где и то,з = ((г ( 1 < г < 1 н я, = я и (хь + Х,) шад В = 8)( есть число блоков серии я на диске 8, которые хронологически < 1 н 8 = (хы + у)) пнин В. Пусть вш = ) (г ) 1 < г < 1 н /с„ш я)); тогда иш — (8 — хь) шабВ( 1!ьз = Р поскольку у, пробегает значения О, 1, ..., вц — 1, если 1 < г < 1 и й, = й. Последователь- ность 1~ для примера из (19)-(21) есть 11111 22223 434об 34567 82345 67893 После того как начнется слияние с 1-го в хронологическом порядке блока, количество необходимых блоков в буферах будет составлять 1, + В + Р, если 1 > Р.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
