Д. Кнут - Искусство программирования том 3 (2-е издание) - 2001 (Часть 2) (1119371), страница 72
Текст из файла (страница 72)
ПУсть9(п, Ь) = Н,-1+2 „,<ь 9/(9/+г). гдеди т опРеделены в теоРеме Н. Подставьте д вместо / в формуле (6). 20. (Сформулировать зто на бумаге труднее, чем объяснить на пальцах.) Предположим, что й-упорядоченный массив Лм..., Кл был Л-рассортирован, и пусть 1 < 1 < /»' — Й; наша цель — показать, что К, < К;+». Найдем и, е, такие, что ( ш и и 1+ й ш в (па модулю Ь), 1 < и,е < Ь.
Применим теперь лемму Е при хг = К„еу нь, уз = К„+Н Оь. Затем первые г элементов К„, К„+», ..., К„ер Оь из у» будут соответственно < последним г элементам К„е», К +»+»,, К е»ер и» из хы где г — наибольшее целое число, такое, что и + Й + (г — 1)Ь < 1»'. 21. Если хй+уй = х'Ь+у'Й, имеем (х-х')Ь = (у'-у)Й, так что х' = х+ГЙ ну = у — Гй для некоторых целых Ь Пусть Л'Ь + Й'Й = 1; тогда и = (пй')Л + (пй')Й, так что любое целое г» имеет единственное представление в виде и = хй + уй, где О < х < Й, а и — порождаемое тогда и только тогда, когда у > О. Пусть аналогично ЬЙ вЂ” Ь вЂ” Й вЂ” в = х'Ь + у'Й; тогда (х + х ) Ь + (у+ у')Й ж ЬЙ вЂ” Ь вЂ” Й.
Следовательно, х+ х» ы Й вЂ” 1 (по модулю Й) и должно быть х+ х' = Й вЂ” 1. Отсюда у+ у' = -1 и у > 0 тогда и только тогда, когда у' < О, Симметричность этого результата свцлетельствует о том, что точно -'(Ь вЂ” 1)(Й вЂ” 1) положительных целых можно представить в предлагаемом виде. Этот результат впервые штучек Сильвестром (Зу)тевгег) (МагйетаМса1 Япьзг)опэ, втгй гйе»г Яа)пбопэ, агат Гйе 'Ебвсабала) Тгтеь' 41 (1884), 21).
22. Чтобы избежать громоздких формул, рассмотрим е = 4 в качестве "полномочного» представителя общего случая. Пусть и» вЂ” наименьшее числа, которое можно представить в виде 15аа+31а~+. и контруэнтное Й (по модулю 15). Тогда нетрудно подсчитать, чта Й = 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14, и» = 0 31 62 63 94 125 126 127 158 189 190 221 252 253 254. Следовательно, 239 м 2 (2 — 1) — 1 — наибольшее среди чисел, которые нельзя представить » в таком виде, а суммарное количество таких чисел есть х» = (п» 1+из 2+ '' +пы 14)/15 = (2+ 4+ 4+ 6+ 8+ 8) + 8+ (10+ 12+ 12+ 14+ 16+ 16) + 16 = 2хз + 8 . 9. В общем случае х, = 2х, ~ + 2' '(2' '+1), Ответы на другие вопросы — глютветственно 2м + 2* + 2 и 2' '(2' + е — 1) + 2.
23. Каждое из Х чисел имеет не более ((Ь,.~» — 1)(Л е» вЂ” 1)/Ь,1 инверсий в своем поен массиве. 24. (Решение получено совместно с В. Праттом (Ъ'. Ргасс). Построим Ь-возвратную пере- становку множества (1,2,..., К) следующим образом. Начав с пустых позиций аы,. ак, выполним при у' = 2, 3,4,... шаг у. Слева направо заполняем пустые позиции а„используя наименьшее число, которое еще не появилось в перестановке, всякий раз, когда (2" — 1)2 — 1 есть положительное целое чиаю, которое можно представить в виде, описанном в упр. 22.
Процесс продолжается до тех пор, пака не будут заполнены все позиции. Так, 2-возвратной перестановкой при 1»' = 20 будет 6 2 1 9 4 3 12 7 5 15 10 8 17 13 11 19 16 14 20 18. При всех й > Ь Ь-возвратная перестановка (2" — 1)-упорядачена. Если 2" < у < Ж/(2" — 1), то на уьм шаге заполняется ровно 2 — 1 позиций, причем (Й + 1)-я нз них добавляет, по » крайней мере, 2" ' -2Й к числу перемещений записей, требуемых для (2" ' — 1)-сортировки этой перестановки. Следовательно, число перемещений, необходимых для сортировки Ь- возвратной перестановки со смещениями Ь = 2* — 1 при К = 2"+'(2" — Ц, заведомо больше 2»" 4 > — 'Мзгз. В.
Пратт обобщил это построение для обширного семейства анютагнчных последовательностей, включая (12), в своей докторской диссертации (Ягап!огб 1)штегУгу, 1972). Некоторые эвристические методы, позволяющие найти такие перестановки, которые нуждаются даже в большем числе перезаписей, найдены Х. Эркио (Н, ЕгЫо), ШТ 20 (1980), 130-136. См, также %е!зз. Яебйеийс1г, Х А!бог!гЛшз 11 (1990), 242-251, где предлагается дальнейшее усовершенствоваиие построения Празта 25. Лл.г~ [этот результат получен Е Б. Манном (Н. В. Мапп), Есопошегйса 13 (1945), 256[, так как перестановка должиа пачииаться либо с 1, либо с 2 1.
Имеется ие более [Лг/21 инверсий: общее число инверсий равно Х вЂ” 1 2Ю Рл + —. Ря-ь (См. упр. 1.2.8-12.) Обратите внимание иа то, что Еле! перестаиовок можно удобно представить азбукой Морзе (последовате.гьиостью точек и тире), где тире соответствует инверсии (см. упр, 4.5.3-32). Следовательно, мы нашли общее число тире во всех последовательностях точек и тире, имеющих длину 5!. Приведешпяе выкладки показывают, что случайная 3- и 2-упорядоченная перестановка имеет грубо -'(!г '+Зф э)Х = ф 'Х/~/5 щ,276/т инверсий.
Но если случайная перестановка является З-рассортированной, а затем 2-рассортированной, то, как показано в упр. 42, она имеет Х/4 инверсий; если же сиачала оиа является 2-рассортированной, а затем— З-рассортированной, то она имеет - !э/3 инверсий. 26 Да; пример самого короткого из иих — 4 1 3 7 2 6 8 5. Здесь имеется 9 инверсий.
В общем гшучае конструкция аггее = ЗЛ + 4з при -1 < з < 1 дает 3-, 5- и 7-упорядочеиные массивы, которые имеют приблизительно -"Л! инверсий. Когда )э' шой 3 = 2, эта конструкпия — наилучшая из возможных. 27. (а) См. Х А!6ггйЛтэ 15 (1993), 101-124. Более простое доказательство, которое показывает, что с может быть любой константой < -', было пезависимо получено Ч. Г. Плакстоиом (С. С. Р)алгол) и Т. Сьюэлом (Т. Впе!), Х А!Зопсйшз 23 (1997), 221-240.
(Ъ) Это очевидно, если т > 1сэ(!в Х/ 1п 1и Л!)~. В противвом случае №~щ~д > !э(!и Ю)~. Р Э. Кифер (Н. Е, СурЛег) [ЯСОМР 22 (1993), 62-71[ нашел более строгое ограничение й(Х(!ой Х) / !о8 !ой%) для случая, если смещения удовлетворяют иеравевству Л,ь, > Л:., при всех в и если последовательность сортировки формируется так, как описано в упр. 5.3.4-2.
На сегодняшний день неизвестно иетривиальиое выражение нижнего асимптотического предела для среднего значения времеви выполнения. 28. 209 109 41 19 5 1, как следует из (11). Но возможна и лучшая последовательность смещений (см. упр. 29). 29. В результате эксперимеитов Ш. Триболе (С. ТНЪо!ес) получил в 1971 году последовательности 373 137 53 19 7 3 1 (В„ч — 7210) и 317 101 31 11 3 1 (В,, 8170). [В первой из иих время сортировки равно ж 127720и по сравнению с щ 128593в, когда те же давиые сортировались с последовательностью гмещений (11).) В общем случае Триболе предлагает выбирать Л, равными простому числу, ближайшему к №~'. Эксперименты, прояедеииые в 1972 году Шелби Седжелом (БЛе!Ъу 5!ебе!), показывают, что наилучшее число смещений в последовательпости для Л' < 10000 при таком методе выбора последовательности равно ! = З!л(Ж/5.75).
Еще одна хорошая последовательность, найденная Робертом Л. Томлиисоном (мл.) (ЙоЪегг Ъ. Топз!шзоп, Зг.), — 199 79 31 11 5 1 (В, - 79э0). Среднее время в этом варианте — = 127260и — оказалось лучшим из известных на сегодняшний день результатов. Как следует из ллительиых экспериментоя, проведенных Кэрол М. Мак-Найми (Саго!е М. Мс."эашее), наилучшей последовательностью из трех смешений 61шет 45 7 1 (В„ 18240). Победительницей в "клжюе четырех смещений", как показали ее эксперименты, оказалась последовательность 91 23 7 1 (В„, ш П865), однако в довольно широком диапазоне значений смещений результаты получаются примерно одинаковые.
30. Число точек с целыми координатами в треугольной области (х!п2+9!пЗС!пЬГ, х>0, Р>0) Равно ф((оЗгйг)(!оЗзФ)+О(!оЗ)г'). Во время Ь-сортировки массив уже 2Ь- и ЗЬ-упорндочен (см. теорему К); следовательно„ можно использовать результат упр. 25. 31. 01 ЗТХЕТ ЕИТЗ Т 1 08 18 104 Н,З Т ОЯ ЕИИ2 -1ИРНТ-И,4 Т 04 ЗТ2 ЗГ(0:2) Т 05 ЗТ2 7Р(0:2) Т ОО ЗТ2 4Р(0:2) Т 07 ЕИТ2 0,4 Т 08 1НР 9Р Т ОУ 2Н 1.04 ХИРЗТ+И, 1 ФТ вЂ” Я вЂ” В + А И 4Н СМРХ ХИРСТ+И-Н,1 ЬГТ вЂ” Я вЂ” В+ А 11 308 8Р ЖТ вЂ”  — В+ А 18 ЗН 101 ХЕРСТ+И-Н,1 В 18 ЗТХ ХИР0Т+8,1 В 14 7Н ЗТЬ 1ИРУТ+И-Н,1 В 15 ХИС1 0 4 В 16 8Н 1ИС1 0,4 ЖТ вЂ” В*А 17 11ИР 23 ЬгТ вЂ” В+ А 18 0ЕС2 1 Я 19 98 ЕИТ1 -И.2 Т + Я 80 12Р 33 Т + Я 81 0ЕСЗ 1 Т 88 13Р 13 Т $ Здесь А — число правосторонних максимумов, как А в программе !) — число левосторонних минимумов; обе величины статистически ведут себя одинаково.
В результате упрощешш внутреннего цинла время выполнения сократилось до Тг)Т+ 7А — 28+ 1+ 15Т машинных циклов и, как ни странно, оно не зависит от В ! При Ф = 8 смещениями будут 6, 4, 3, 2, 1, и имеем Аь, = 3.892, В„,, = 6.762; суммарное время работы в среднем составляет 276.24и (ср. с табл. 5). Обе величины— А и  — достигают максимума на перестановке 7 3 8 4 5 1 6 2. При Х = 1000 имеется последовательность нз 40 смещений: 972, 364, 763,729,...,8,6,4,3, 2, 1; змпирнческне тесты, подобные тем, которые приведены в табл. 6, дают А ш 875, В ш 4250 и общее время выполнении — около 268000и (примерно вдвое больше, чем для программы !) с последовательносгью смещений из упр.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
