AOP_Tom3 (1021738), страница 194
Текст из файла (страница 194)
21. 333343333332322 3333433333323 33334333333 3333433 333323 Т5 22. гв — З г — З г — — -1 + 3(п шос1 3 = 1(. (Это соотношение, подобное соотношению Фибоначчи, следует из того, что 1 — гг — 2гз — г~ = (1 — фг)(1 — егг)(1 — огг)(1 — огг), где ыз = 1.) 23. Вместо (25) длины серий в течение первой половины и-й фазы слияния будут в„, а в течение второй половины — йо где в„= 1 -г + Зо — з 1- зв з + во-з, З = 1 -г + в„— г + В„З + В„З.
ЗДЕСЬ МЫ ПепатаЕМ Вв = З = 1 Прн П < О. [В ОбщЕМ СЛуЧаЕ, Ещгн Е„аг является суммой первых 2г членов из и г + + ов. г, имеем в = 1 = г„г + . + го, + 2г,,-г + 1 —,-г + + 1 и. Если е„е~ есть сумма первых 2г — 1 членов, то в„=г — г-Ь.. -его-.,-г-~-в,—,-г-с +в -г,з =1 — г+ ° +г —,+в -„+ ° +вв-г( Вместо (27) и (28) (и — гК вЂ” ги — гН -ги -зЪ вЂ оП~,-зУ -з) + 1, (и„гЪв г) + 1, (и — гЬв-ги — 3) + 1, (и„г'гв ги„г) + 1, ( г — ги — зŠ— зи — 4" — 4) + 1 11„= Е„= 1г, и„= 1ы 1з 1з В 1з24 1з — 24 В 26.
Если сортируются 2" начальных серий, то во время слияния обрабатываются и - 2"-е серии. Каждая половина фазы (за немногими исключениями) сливает 2" г и перематывает 2" '. Если сортируются 2 +2" ' начальных серий, то обрабатываются во время слияния О 1 2 3 4 5 6 7 В 8'16' 16 В. 16' 16' В 16' 16' 16' 16о 16о О 1 1 2 2 5 8 Зг Зо 8 1 80 В 24 В 24о32о 32' (В) О 1 1 1 2 3 4 б 1 3 3 5 7 11 15 23 Т1 Тб ТЬ Т4 ТЗ Т2 Т1 Тб п 2" +(п — 1) 2" '. Каждая половина фазы (за немногими исключениями) сливает 2" или 2" и перематывает 2" ' + 2" з начальных серий.
27. Стратегия работает тогда и только тогда, когда наибольший общий делитель чисел распределения равен 1. Например, пусть имеется шесть лент; если мы распределим (а, Ь, с, 4, е) на ленты Т1-Т5, где а > Ь > с > 8 > е > О, то после первой фазы получится распределение (а-е,Ь вЂ” е,с-е,с( — е,е) и бсс1(а — е,б-е,с — е,б — е, с) = бед(а,Ь,с,д,е).
(Любой общий делитель одного из атих множеств чисел делит также числа другого множества.) Рассматриваемый процесс уменьшает количество серий на каждой фазе до тех пор, пока на одной ленте не останется боб(а,Ь,с,б,е) серий. (Заметим, что эти но многофазные распределения иногда оказываются лучше многофазного при определенном расположении фиктивных серий, как показано в упр.
13. Это свойство впервые было замечено Б. Сзкманом примерно в 1963 году.) 28. Мы получаем любую такую пятерку (а,Ь, с,б, е), начав с (1, О, О, О, 0) и выполнив ровно н раз следующую операцию: выбрать и из 1а, Ь, с,4, е) и добавить к к каждому из остальных четырех злементов (а,Ь, с,б, е), Чтобы доказать, что а + Ь+ с + 4 + е < 1„, докажем по индукции, что если а > Ь > с > и > е, то всегда имеем а < а„, Ь < Ь, с < с, 4 < 4, е < ев.
В предположении, что сказанное справедливо дли уровня и, зто также должно быть справедлиио для уровня п т 1, поскольку распределения (и -~- 1)-го уровня суть (Ь+а, с+а, 0+а, с+а, а), (а+Ь, с+Ь, лИ-Ь, с+Ь, Ь), (а+с, Ь+с, 8+с, еч-с, с), (а-ьб, Ь-ьб, с+8, с+с(, 4), (а+с, Ь-ье, с+с, йч-е, е). 30. Дж. А. Мортенсон (3. А. Моглепвоп) свел результаты вычислений в следующую таблиду. Уровень Т=5 Т=б Т=7 Т=3 Т=9 Т=10 1 2 2 2 2 2 2 Мл 2 4 5 6 7 8 9 Мз 3 5 6 7 8 9 Мз 4 8 8 10 12 14 16 М4 5 10 14 13 17 20 23 Мз 6 18 20 26 27 32 31 Мв 7 26 32 46 47 56 42 Мг 8 44 53 74 82 92 92 Мз 9 68 83 122 111 138 139 Мв 10 112 134 206 140 177 196 Мзо П 173 197 317 324 208 241 Мм 12 290 350 401 488 595 288 Мзз 13 466 566 933 640 833 860 Мз з 14 756 917 1371 769 1064 1177 Мз4 15 1220 1431 1762 2078 1258 1520 Мы 16 1976 2313 4060 2907 3839 1821 Мы 31. (11алдош Бзгисзигее 4з А!8ог1збтв, 5 (1994), 102-104) Кз(п) = Ь;~ ~з = ~'А з,.
Имеем и — 4 — 1 = ал + . + а„если в дереве т + 1 листьев и (Ь + 1)-й лист имеет ал — 1 предков, отличных от предков первых Ь листьев. (Приведенные семь примеров деревьев соответствуют суммам в правой части 1+1+1+1, 1+ 1+2, 1-Ь2-Ь1, 1+3, 2+1+1, 2+2 и 3+1.) РАЗДЕЛ 5.4.3 1. Выясняя с помощью табл. 5.4.2-6, сколько раз в среднем обрабатывается каждая запись, видим, что многофазный лзетод с расщеплением лент лучше, если имеется 6, 7 или 8 лент. 2. Методы, по существу, тождественны, если число начальных серий является числом фибоначчи; в противном случае способ распределения фиктивных серий лучше у многофазпого метода. Каскадный алгоритм помещает 1 на Т1, 1 на Т2, 1 на Т1, 2 на Т2, 3 на Т1, 5 па Т2 и т.
д. Поэтому на шаге С8 никогда не обнаружится, что Р]р — Ц = М(р — 1], если р = 2. В результате все фиктивные серии оказываются на одной ленте, а это менее эффективно, чем метод алгоритма 5.4,2Р. 3. (Распределение заканчивается после тою, как 12 серий помещаются на ТЗ на шаге (3, 3).) Тб 2г4ш 26 5. Если имеется а начальных серий, то й-й проход выводит а„з серий длиной аз, затем 6„з — длиной Ьз и т. д. 7.
езе„г -ьезе з+ +е ео длин начальных серий (см. упр. 5), что может быть также записано в виде аза з т ага — з+ . + а зао, это коэффициент при (г" з] в (А(г) А(г)). 8. Знаменатель А(г) имеет различные корни, и его степень выше степени числителя, поэтому А(г) = 2 дз(р)/(! — рг) р(! — 9з(р)), где сумма берется по всем корням р уравнения Оз(р) = р. Этот специальный вид р полезен при вычислении ез(р) и Оз(р), 9.
Эти формулы справедливы для всех больших и из (8) н (12), если иметь в виду значение Ом(2 з!и бз). Чтобы показать, что они справедливы при всех и, необхсщимо знать, что дм з(г) есть частное от деления 9, з(г)д (г) на д,(г) — г при 0 ч гп < г. Это можно доказать, либо используя (10) и учитываи, что при сокращении степень Ф з(г)д (г)— д,(г)д~ з(г) снижается, либо учитывая, что из результата упр.
5 следует, что А(г)' .~- В(г)'+ . + Е(г) -+ 0 при г -э со, либо найдя явную формулу для числителей В(г), С(г) н т. д. 10. Е(г) = гз(г)А(г); Р(г) = гз(г)А(г) — гз(г); С(г) = гз(г)А(г) — гз(г) В(г) = гз(г)А(г)— гз(г); А(г) = гз(г)А(г)+! — гз(г), Таким образом, А(г) = (1 — гз(г))/(1 — гз(г)). [Обратите внимание на то, что г (2 в!и 9) = з!п(2тлб)/соз 9; следовательно, гм(г) является многочленом Чебышева (-1)~т'с!г -з(г/2).] 11.
Докажите, что /о(г) = 9!ч~з1(г) — П 7з!(г) и что /„,(г)/ з(г) = 1 — г (г). Затем используйте результат упр. 1О (Это выражение для знаменателя в явном виде впервые было выведено Девидом Е. Фергюсоном (РатЫ Е. Гегбпзоп).) 13. См. упр. 5.4.6-6. Т1 Т2 ТЗ Т4 !ы 1м !гз !ы 1з 1ы 8 69 5з бз — 9' 23' 17' 100 1 4. Доказывается по индукции (см. упр. 5.4.2 — 28). 1 1 1 1 1 1 1 1 1 0 1 1 1 0 0 1 1 0 0 0 1 0 0 0 0 Т5 11з 1!з 11 25' РАЗДЕЛ 5.4.4 1.
Сначала (перед выводом восходящей серии) следует записать концевую запись, содержащую -оо. (Запись с ключом +ос по-прежнему должна располагаться в конце серии, если только мы собираемся когда-либо считывать ее в прямом направлении, например на последнем проходе.) Для нисходящих серий поменять ролнми — со и +со. 2. Наименьшее число на уровне и+ 1 равно наибольшему на уровне и; следовательно, столбцы являются неубывающими независимо от того, как переставлены числа в любой отдельной строке. 3.
На самом деле в процессе слияния первая серия на Т2-'Тб всегда будет нисходящей, а на Т1 — восходящей (по индукпии). 4. Такой метод требует нескольких операций "копирования" на втором и третьем проходах; дополнительные затраты приблизительно равны (1об 2)/(1об р) проходам, где р— «отношение роста" (см. табл. 5.4.2-Ц. 5. Если и — цепочка, обозначим через и ее обращение. л Уровень Т1 Т2 Тз Т4 Т5 2 3 4 3 4 12 12 12 4 3 2 3 4 3 2 3 2 3 4 3 4 5 4 3 32 232 1232 1232 1232 323432 12323432 12323432 2323432 Е« В А„, + 1, А„зА„з + 1, А«-зА«-зА -з + я я я А„-4А„зА„-гА«-з + 1, л я л я я А«зА„«А«-зА„з.4„ Е„ А„ где Яю = Ч -з(Ю -з + 1)(Я«-3+ 2)(4«з„-4+ 3)(4«з«-4+ 4), п > 1, 14р = 0 и цепочка Я = е при и < О.
Цепочки А„, В„, ... содержат те же элементы, что и соответствующие цепочки из раздела 5.4.2, но в другом порядке. Заметим, что соседние числа слияний всегда различаются на 1. Начальная серия должна иметь тип А тогда н только тогда, когда число ее слияний четно, Р— если нечетно. Простые схемы распределения, такие, как в алгоритме 5.4.2Р, уступают в эффективности размещению фиктивных серий в позиции с большими числами слияний; поэтому, вероятно, выгодно вычислять 44«между фазами 1 и 2, чтобы облегчить управление процессом размепзения фиктивных серий. п+1 В.(А„"+Ц С (А,",+Ц Р„(лл+Ц Е«(А,",+Ц А„"+1 Имеем 2 3 4 3 5 4 3 2 3 4 3 2 3 2 1 2 3 4 3 4 4 3 2 3 4 3 2 3 2 2 3 4 3 4 5 44 3 2 3 4 3 6.
р1'> =(+1,+1,— 1,+1) „(з) 1+1 р Щ> = ~.ь1, — 1, +1, +» р<П = [-1, +1, +1, +Ц р<е~ = < 1, 6, О, О) Число 34 является, вероятно, наименьшим числом Фибоначчи г, для которого многофазный метод не дает оптимального слияния с обратным чтением для Г„начальных серий на трех лентах. Это дерево имеет длину внешнего пути 178, что на 2 лучше, чем в многофазном методе, для которого соответствующий параметр равен 176. 8. Для Т = 4 дерево с длиной внешнего пути 13 не является Т- Ио-деревом, и любое дерево с длиной внешнего пути 14 включает однопутевое слияние. 9. Используя результат упр.
2.3.4.5-6, можно рассмотреть полное (Т вЂ” 1)-арное дерево; степень "последнего" внутреннего узла лежит между 2 и Т вЂ” 1. Если в нем имеется (Т вЂ” 1)г -т внешних узлов, то ) т/(Т вЂ” 2Ц из них находятся па уровне е — 1, а оставшиеся— на уровне Ф 11. Верно, что доказывается индукцией по числу начальных серий. Если правильное распределение о' серий и две соседние серии находятсн в одинаковом направлении, то существует нужное распределение меныпего, чем Я, числа серий, но его не существует прн о = 1. 12. Условия (а) и (Ь) очевидны. Если имеется какая-нибудь конфигурация в (4) для некоторого имени ленты А н некоторых г С 7' ( й, то узел у должен быть в поддереве ниже узла 1 и слева от узла к по определению прямого порядка.
Следовательно, случай "у — Г не может иметь места и А должно быть "специальным" именем, так как оно появляется на внешней ветви. Но это противоречит тому, что специальное нмя, как мы предположили, находится на крайней слева ветви ниже узла б 13. Узлы, пронумерованные 4, 7, 11, 13, можно преобразовать во внешние, и по отношению к ннм не нужно использовать однопутевое слияние. В результате длина вне~инесе пути будет на единицу болыпе, чем в случае многофазного дерева.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
