Д. Кнут - Искусство программирования том 3 (2-е издание) - 2001 (Часть 1) (1119456), страница 76
Текст из файла (страница 76)
б показаны приблизительные данные о ходе выполнения этой процедуры, когда В не слишком мало. В столбце "Проходы/фазы" примерно покэзано, какая часть всего файла перематывается во время каждой половины фазы и какая часть файла записывается за время каждой полной фазы. Метод раси!еплснил лент превосходит стандартный многофазный ззстод на шсспзи или более лептах и, вероятно, также на пяти лентах, по крайней мере для больших о. Если Т = 4, то указанная процедура стала бы, по существу, эквивалентной сбалансированному двухпутевому слиянию без совмещения времени перемотки, так как шт +з было бы равно О при всех и. Поэтому элементы табл. б при Т = 4 были получены посредством небольшой модификации, состоящей в том, что полагалось оз = О из = 1, из =0 ио = О,сс = 1 иены = и„з+о„з, и„= и„з+ь„т при п > 2.
Это позволяет построить очень интересную схему сортировки (см. упр. 25 и 26). рЯ серий, то и = а !п 5+ Ь + О(Я ') и р = с 1п Я + «(+ 0(8 '), где а=(1па), 6= — а!и! — /! -1, сжа 1.— 9'( ')/ ' -4'( ') ' (6+1)а — р'(а ~)/р(а ')+6"( ')/9'(а ~) — 9'(а ') .«. [ЯМ99] Пусть ар — главный корень многочлена /о(х) из упр. 5. Каково асимптотическое поведение а при р -«аау 6. [М96] (Э. Нетто (Е. Кеыо), 1961.) ПУсть 6«и«о! есть число способов выРаженим «и в аиде упорядоченной суммы целых чисел (1, 2,..., р).
Например, если р = 3 и и« = 5, то имеется 13 способов: 1+1+1+1+1 = 1+1+1+2 = 1+1+2+1 = 1+1+3 = 1+2+1+1 = 1+2+2 = 1 +3+1 =2+1+1+1 = 2+1+2 =2+2+1 =2+3 =3+1+1 = 3+2. Покажите, чта )9 о являются обобщенными числами Фибаначчи. 9. [мй6] пусть к~~ю — число по«ледовательнастей из нулей и единиц, таких, что в них нет р последовательных единиц. Наприыер, если р = 3 и и« = Ъ, имеется 24 варианта: 60066, 00061, 66616, 66611, 6619), 60161, 00110, 01660, 01001,..., 110П. Покажите, что К о~ являются обобщеннымн чнсвами Фибоначчи. 10. [М97] (Сис«лема счисления с обоби«синими числами Фибоиоччи.) Докажите, что кал«дое неотрицательное целое и имеет единственное представление в виде сунны различных чисел Фибоначчи р-го порядка г о при у > р, удовлетворяющее условию, что не используются никакие р-последовательные числа Фибоначчи.
11. [М94] Доках«ите, что и-й элемент цепочки О в (12) равен количеству различных чисел Фибоначчи в представлении элемента и — 1 числами Фибоначчи пятого порядка (см. у р. 16). О 1 О 0 0 0 0 1 6 6 ь 12. [М!6[ Найдите зависимость между степенями матрицы 0 О 0 1 0 0 6 0 0 1 1 1 1 1 1 и точным фнбоначчиевым распределением в (Ц. ь 13.
[99] Докажите следующее интересное свойство точных фибоначчневых распределений: если окончатю«иный вывод оказывается иа ленте номер Т, то число серий на всех других лентах иечстпиое; если окончательный вывод оказывается на некоторой лепте, отличной ат Т, то число серий будет иечеп«иим на втой ленте и че«пиым на остальных (см. (1)).
14. [М66] Пусть Т (х) = 2 а>о Т„ох~, где Т (и) — миогочлены, определенные в (16). а) Покажите, что для каждого а существует число и(!«), такое, что Ты < Тзь « . Т„„м>т,„,„„„д >" . Ь) При условии, что Тыь < Т„ь и и' < г«, докажите, что Т„.ь < Т ь для всех )«> 1'. с) Докажите, чта существует неубывающая последовательность (М„), такая, чта Е (5) = пйпу>«Е1(5) при М < 5 < М«еп но Ео(а) > «п(п!>«Е>(5) при 8> М о«(см.
(19)). 16. [М48] Верно ли, что условие Е„«(гп) < Е„(п«) влечет за собой Е„(тп) < Еь ю(гп) < Еоет(т) < ° . (Такой результат сильно упростил бм вычисление табл. 2,) 16. [НМ48] Определите асимптотическое поведение многофезного слияния с оптимальным распределением фиктивных серий. 17. [32] Верно ли, что серии для оптимального миогофазиого распределения можно разместить таким образом, что распределение Я+ 1 начальных серий получится путем добавления одной серии (иа соответствующую ленту) к распределению 5 иачальиых серий? 18.
[Уб] Верно ли, что оптимальное многофазное распределение дает наилучшую возможную схему слияния в том смысле, что суммариое количество обрабатываемых начальных серий минимально, если требуется, чтобы начальные серии размещались ие более чем на Т вЂ” 1 лентах? (Временем перемотки преиебречь.) 19. [3?] Составьте таблицу, аналогичную (1), для миогофэзиого метода сортировки Карона для шести лент. 20. [ЛЩ] Какая производящая функция для кароиовской миогофазиой сортировки иа шести лентах соответствует (7) и (16)? Какие соотношения, аналогичные (9) и (27), определяют строки чисел слияний? 21. [?7] Что должно появиться иа уровне 7 в (26)'? 22. [Мй?] Каждый член последовательности (24) приблизительно равен сумме двух предыдуших членов. Наблюдается ли зто явление для остальных членов последовательности? Сформулируйте и докажите теорему о Ä— 1„-~ — Г -э.
ь 23. [3э] Какие изменения необходимо выполнить в (25), (27) и (28), если (28) заменить иа еюы = в -~ + э„- ~ + в„-э, ив = е„-э + э -э + в -з + и„-э + е„-э? 34. [НА?] Вычислите асимптотическое поведение миогофазиой процедуры с расщеплением лепт, если элемент еюм опРеделен как сУмма пеРВых 7 члеиов и„-~ + е„-~ + . + в„г + е„-г при различных Р = Т вЂ” 2 и О < д < 2Р. (В тексте раздела рассматривается только случай, когда о = 2 [Р/2]; см. упр. 23.) 35. [? 9] Продемонстрируйте, как многофазное слияние с расщеплением лент, упомянутое в конце этого раздела, сортировало бы 32 иачэльиые серии.
(Проанализируйте каждую фазу, как в тексте, в примере с 82 сериями иа ~пести лентах.) 26. [Мй?] Проанализируйте ход выполнения многофазного слияния с расщеплеиием левт иа четырех лентах при Я = 2" и при 5 = 2" + 2" ' (см. упр. 25). 27. [ЗУ[ Если начальные серии распределены иа лентах в соответствии с точным распределением„то многофээчая стратегия превращается просто в "слияние до опустошения'. Сиачала сливаем серии со всех непустых входных лент, пока одна из иих ие станет пустой; затем испгиьзуем эту ленту как следующую выводную, а предыдущую выводную леи*у— как вводную. Верио ли, что стратегия "сливать до опустошеиия" всегда позволяет выполиять сортировку независимо от того, как распределены начальные серии, при условии, что мы распределяем их, по крайней мере, на две ленты? (Одна лента, конечно, будет оставлена пустой, чтобы оиа могла служить первой выводной лентой.) 28.
[М36] В предыдущем упражнении определена весьма большое семейство схем слияния. Покажите, что миогофазиая схема — наилучшая из иих в следующем смысле. если имеется шесть лент и мы рассматриваем класс всех начальиых распределекий (а, Ь, с, И, е), таких, что стратегия "сливать до опустошения" требует и или меньше фаз для сортировки, то а+ 6+ с+ И+ е ( Ф„, где Ԅ— соответствующее число для многофазной сортировки (Ц. 29. [М(7] В упр. 28 показано, что миогофазиое распределение оптимально среди всех схем "сливать до опустошения" в смысле минимальности числа фаз, Но является ли оио оптимальным также в смысл» мииимальиости числа проходов? Пусть числа о и Ь взаимно простые, и предположим, что о+Ь есть число Фибоиаччи Р„. Верно ли следующее предположение, высказанное Р.
М. Карпом (В.. М, Кэгр): число начальных серий, которые обрабатываются схемой "сливать до опустошении", ивчииаквцейсв с распределения (а, Ь), больше илн равна ((и — 5)Г,+1+(2а+2)Р~)/5» (Указанное значение достигается, когда а — Рч-1, Ь = Р» — » ) 30. (48) Составьте твблипу, аналогичную табл.
2, для мнагафвзнага слияния с расщепле- нием лент. 31. [Мйй) (Р. Кемп (Н, Кегар).) Пусть Кэ(п) — число а-узловых упорядоченных дере- вьев, в которых каждый лист находится на расстоянии 4 ат корня. Например, в изабра- лсенных ниже деревьях К«(8) = 7. Покажите, чта К,1(п) является обобщенным числом Фнбаначчи, и найдите однозначное соответствие между»акими деревьями и упарядачеш1ым разбиением, которое рассматри- валась в упр. 8. Обработанные начальные серии 190 190 190 190 190 Т1 Т2 ТЗ Т4 Т5 1вз 14а 141 1тэ 11$ — «14 2« 31» 4'4 1ааз 144 123 92 «51 «15' 29' 41' 50' 190' Проход 1 Проход 2 Проход 3 Проход 4 Проход 5 Зи 55' Каскадное слияние подобно многофазному начинается с точного распределения серий по лентам, хотя правила точного распределения отличны от правил из раздела 5.4,2. Каждая строка таблицы представляет полный проход по веем данным.
Проход 2, например, получается посредством выполнения пяхипутевого слияния с (Т1,Т2,ТЗ,Т4,Т5) на Тб, пока Т5 не станет пустой (при этом на Тб помещаются 15 серий относительной длиной 5), затем четырехпутевого слияния с (Т1, Т2., ТЗ, Т4) на Т5, затем трехпутевого слияния на Т4, двухпутевого слияния на ТЗ и, наконец, однопутевого слияния (операции копирования) с Т1 на Т2. Проход 3 получается таким же образом, путем выполнения сначала пятипутевого слияния, пока одна лента не станет пустой, затем — четырехпутевого и т. д.
(Похоже, что разделу книги следовало бы присвоить номер 5.4,3.2.1, а не 5.4.3!) Ясно, что операции копирования излишня и нх можно было бы опустить, Однако фактически в случае для шести лент это копирование отнимает только небольшую часть всего времени. Элементы, которые получаются в результате простого копирования, отмечены в приведенной выше таблице звездочкой.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
