Д. Кнут - Искусство программирования том 3 (2-е издание) - 2001 (Часть 2) (1119371), страница 71
Текст из файла (страница 71)
Присвоить Я+-Л;, й+- СОНЕТ(К;], СОНЕТ(К)) +- й — 1, Лт э- Л, Л+- Я, )' э- а. Затем, если 1 )Э г, повторить этот шаг; если ) = г, присвоить Л) +- В, г +- г — 1 и вернуться к шагу 1)б". 1 Для того чтобы убедиться в состоятельности этой процедуры, обратите внимание, что ~ирод началом шага Пб все записи Л„которые еще не находятся на своих окончательных местах и для которых ) > г, должны продвинуться влево; когда г = О, не может существо- вать ни одна такам запись, поскольку кечемр двигаться вправо.
Алгоритм, конечно, очень элегантен, но, к сожалению, нестабилен при наличии равяых ключей. Он тесно связан с построением Фоаты в теореме 5.1.2Е, РАЗДЕЛ 5.2Д 1, Да. Равные элементы никогда не меняются местами, 3. Да, но в случае, если имеются равные элементы, время работы увеличится и процесс сортировки будет выполняться в прямо противоположном нэлравлеиви по сравнению с устойчивой сортировкой. 3.
Предполагается, что следующая программа из 8 команд — самая короткая программа сортировки для машины И11, хотя она и не может быть рекомендована из-за низкой скорости выполнения. Считается, что числа находится в ячейках 1,...,)э' (т, е. 1ИРОТ ЕОО 0); в противном случае нужна еще одна команда. 2Н Ерь 0,1 В СМРК 1,1 В )Ы 1Р В МОТЕ 1,1 А Еть 0,1 А ЕТКИТ ЕИТ1 И А+1 1Н ОЕС1 1 В+ 1 ЛР 2В В+1 И Замечание.
Чтобы оценить время выполнения, заметим, что А равно числу инверсий. а величина  — довольно простая функция таблицы инверсий и (в предположении, что элементы ввода различны и расположены в случайном порядке) имеет производящую функцию '"-'( + И +" +""') (1+ „з+ заэ+ з+гч~) (1+ я-~+ гл-з+ + я(к-ц7эу ~, Среднее значение В равно Ф вЂ” 1+ 2 ~~,(5 — 1)(27г — 1)76 = (М вЂ” Ц(4Ф~ + 57+ 36)/36; следовательно, среднее время выполнения — примерно э Ю и. г з 4. Рассмотрим таблицу инверсий В~...Вл двиной исходной перестановки в смысле упр. 5.1.1-7. Величина А на единнпу меныпе числа элементов В;, которое равно,у — 1, а В равно сумме элементов В . Следовательно, обе велнчинм —  — А и  — достигают макеимума, когда исходная перестановка равна Х...
2 1; обе величины достигают минимума, когда исходная перестановка равна 1 2... Р7. Следовательно, минимальное возможное время выполнения достигается прн А ж 0 и В ж 0 и равно (1057 — 9) и; максимальное время выполнения будет достигнуто при А = М вЂ” 1 и В = (~~) и равно (4.5М~ + 2.557 — 6) и. Ь. Искомая производящая функция равна произведению вы э и производящей функции для величины 9 — ЗА. Рассмотрев, как в предыдущем упражнении, таблицу инверсий и вспомнив, что отдельные элементы таблицы инверсий не зависят один от другого, находим искомую производящую функцию сш~ э)(~<~<и((1+ ээ + .
+ зээ 'э + зэ™)д). Дисперсия равна 2.25Р7з + 3.375%э — 32.625Ж + 36Нк — ОВ<ч ~. 6. Организуйте область вывода как циклический список, в котором позиция Р7 будет соседней по отношению к позиции 1. Следующий элемент, который нужно вставить, берется с левого или правого конца текущей серии нерассортировэлных элементов в зависимости от того, оказаэся лн предыдущий вставленный элемент соответственно справа или слева от центра области рассортированшах элементов, В конце обычно требуется "прокрутить" эту область, переместив каждую запись на 5 позиций по кругу, где к — некоторое фиксированное значение.
Это можно эффективно выполнить способом, аналогичным рассмотренному в упр, 1.3.3-34. 7. Среднее значение для )аз — Я равно -'()1-Я+)2-7)+ +) -Я)=-'Д'2)+(","'Ц; у ру у, у —.'(("+,') + ("з')) = -'( ' — 1). 8. Нет; рас~мотрите, например, последовательность ключей 2 1 1 1 1 1 1 1 1 1 1. 9. Для табл. 3 А = 3+ 0+ 2+ 1 = 6, В = 3 + 1+ 4+ 21 = 29; для табл. 4 А = 4+2+2+0 = 8, В = 4+3+8+10 = 25; следовательно, время выполнения программы П в этих двух случаях равно соответственно 786э и 734и. Хотя число перезаписей сократилось с 41 до 25, эта программа не может соперничать с программой Б по времени работы, поскольку при 1Ь' = 16 тратится много времени на вспомогательные операции, необходимые для организации четырех проходов. При сортировке 16 элементов лучше выполнить только два просмотра: двухпроходный вариант программы П начинает превосходить по скорости программу Я примерно при Ж = 13; и все же на коротких наборах входных данных они почти равноценны (а прн малых значеннвх Ф, возможно, существенную роль играет длина программы).
10. Вставить "1801 1ИРОТ; ЗТ1 ЗР(0:2)" между командами в строках 07 и 08 и заменить строки 10 — 17 следующими строками; ЗН Сйра 1ИРОТ+И-Н,1 ДгТ вЂ” Я ЗОН 8Р 57У вЂ” Я За счет увеличения програмыы иа четыре команды удается сэкономить 3(С- Т) машинных циклов, где С вЂ” число случаев, когда Кл > Кл л.
В табл. 3 и 4 экономия времени составляет соответственно около 87 и 88 циклов; эмпирически значешле С/(МТ вЂ” 5) можно выбрать равным приблизительно 0.4, если А,~~/Ь, ш 2 и приблизительно 0.3, если Ьл ю/Л. 3, так что это усовершенствование стоит затраченных усилий. (С другой сторошя, аналогичное изменение программы Я нежелательно, так как экономия в этом случае пропорциональна всего лишь 1об Х, если только заранее неизвестно, что входные данные достаточно хорошо упорядочены.) 12. Замена ( символом ( всегда приводит к изменению количества инверсий на А1 в зависимости от того, где выполнена замена — нал или под диагональю. 13.
Припишите вес (1 — Я сегменту от (1, /-1) до (1,7). 14. (а) Поменяйте местами л и 7' в сумме для Аз„и слсвките зти две суммы. (Ь) Взяв половину данного результата, видим, что ~1+7) (2п — 1 — 1) ~- к ~2л+А) (2ц — 21 — А) О<г<1 ,лйо следовательно, 2 Аз х" = 2 „~ йхлотл/(1 — 4х) = х/(1 — 4в)л где о = (1- а71: 4х)/2- Это доказательство сообщил автору Леонард Карлиц (Ьеопагб Сагйсх).
Еше адно доказательство может основываться на взаимосвязи межлу весами Лля горизонтальных и вертикальных серий (см. упр. 13). Другой вариант доказательства малино сформулировать прн немощи тождества, которое рассмотрено в ответе к упр. 3.2.2-1б при /(А) =- А; однако непонятно, как, используя комбинаторику, просто вывести формулу А = (и/2) 2" ~. 1$. Прин>0 0„(з) = х"д„ А-( ) = р ( ) + "д (х); л ч р ( ) = ~ „ Ых)а.- ( ); А (а) = ~ Ал( )А — (х). Полагая С(в, с) = ~„„у„(х)и~®', находим, что вхС(вьх)С(вх,с) = С(кьв) — 1. Из этого представления можно вывести, что, если 1 = л/à — 4в = 1 — 2ю — 2вт — 4ю" —, имеем С(в,1)=(1 — 1)/(2 );С(к,1)=1/( 1)-(1-1)/(2 )'С(в,1)=1/(21') — 1/(21);Се(в Ц= 2/(вг~) — 2/(в 1) + (1 — 1)/юз; С'(вй 1) = 2/1~ — 1/Гз; С" (ю, Ц = 1/1~ — (1 — 2и!)/1л+ 10вт/Гл.
Здесь нижние штрихи обозначают дифференцирование по первому параметру, а верхпие— по второму параметру. Аналогично из формулы в(хС(, ) +С( ~х))В(в,х) = Н(ю, ) — 1 4Н ЕИТ2 бн ЯТ бн НТХ 0802 12ИР СИРА л. 7Н ЗТА И-Н.1 1ИРНТ,2 1ИРОТ+Н,2 0,4 7Р ТИР07,2 БН 1ИРНТ+Н,2 Р/Т вЂ” Я вЂ” С В В в   — А В-А )ЦТ-З-С ! Н'(ш,1) = ш/1~, Нл(в,1) = -в!/г~ — ш/1~+ 2ш/Сэ+ (2в!~+ 20!с~)/Ф~. Все эти манипуляции формулами выполнены вручную, но современные программные средства позволяют проделать то же самое значительно быстрее на компьютере, В принципе, таким способом можно получить все моменты этого распределения. Произж~дящая фуикцгп! 9 (с),также представило!, ~ вллнни энг'! МмВЙО лгть ш! всем деревьям с и+ 1 узлами (см.
упр. 2.3,4.5-5). Интересно отметить, что С(ш,з) раина Г( — !ел,з)/Р(-ш,з), где Е(з,д) = 2 „>о в"9" /Д„" !(1 — д ); коэффициент при дмз" в Г(з, д) равен числу разбиений гл = р, + ° + р„, таких, что р; > рзе! + 2 при 1 < ! < и и р„> 0 (см. упр, 5.1.1-16). 16. Ясно, что при Ь = 2 максимум достигается на пути, проходящем через правый верхний угол решеточной диаграммы, и равен ~(п/2) +1) При произвольном значении Ь соответствующее число равно (.Ь =©Г")" (.") "' где д и ! определяютси теоремой Н; перестановка, в которой а егь = 1 + 9(Ь вЂ” !) + (г — !)(! < г) при 1 < !' < Ь и у' > О, максимизирует число инверсий в каждой из (!) пар упорядоченных подпоследовательиостей.
Максима!нное число перемещений получится, если в формуле (6) подставить / вместо /, 17. Единственная 2-упорядоченная перестановка множества (1, 2,..., 2п) с ("'"') инверсиями — это я+1 1 и+2 2 ... 2п и. Применяя данную идею рекурсивно, получим перестановку, в которой добавлена единица к каждому элементу последовательности (2 — 1) и 1 О, где 71 обозначает операцию записи целого в виде 1-разрядного двоичного числа с л л последующей записью его двоичных разрядов в обратном порядке (справа налево)! 18. Вынесем за скобки общий множитель и положим Ь! = 4Ж/я; требуется минимизировать сумму 2 ",, ЬЫ /Ь! ! при условии, что Ьс = 1. В результате дифференцирования получается соотняошение Ь! ж 4Ь! ! Ь!!, которое имеет решение (2' — 1) 18 Ь! = 2 +'-2(1+ 1)+ )8Ь!.
Минимальное значение исходной оценки равно (1 — 2 !)к! гм! ЫЬ!'~ Г! М/ /2'+!' '!Г1~ '1, при ! -э оо эта величина быстро сходится к №/пФ/2 . Ниже приведены типичные "оптимальные" значения Ь при !!! = 1000 (см. также табл. 6): Ье 5764, Ь! 6.13, Ьа = 1; Ьз 135.30, Ьг ж 22,05, Ь! 4,45, Ьо = 1; Ь! ж 284,46, Ьз 67.23, Ьэ 16.34, Ь! ш 4.03, Ьс = 1; Ьэ ж 9164.74, Ьэ ж 12294.05, Ьг 7П9.55, Ье ж 2708.95, Ьэ 835.50, Ь! ш 232.00, Ьз 61.13, Ьт и 15.69, Ь! ш 3.97 Ьо = 1 19.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
