Д. Кнут - Искусство программирования том 3 (2-е издание) - 2001 (Часть 2) (1119371), страница 84
Текст из файла (страница 84)
Аг < В„+, зз-з, Аз > Вгз-», А» > Взз-»ьзз-г, А» > Взз-»+ з-з+зз-з, но тогда остается еще ровно д» з элементов! Обратна, если п = у» — 1, то этот путь приводит к желаемому результату. (Асза Хп»отша»зса 1 (1971), 145-158.) 12. Первое сравнение должно быть либо ем Хз, где 1 < Й < з, либо (симметрично) ~3: Х -з, где 1 < Ь < у. Б первом случае при исходе а < Хз остается выполнить еще В (Ь вЂ” 1,1) сравнений; исхода > Хз прнводит к задаче сортировки а < Б, У» « . У -ь, а < К-з+», Б >1„-з-»ч где г; =Х,-м 1$.
См. Сашрнгегз»л Ь»пшбег ТЬеогу (7»еи Уогрл АсЫеш)с Ргезз, 1971), 263-269, 14. 5ТСОМР 9 (1980), 298-320. Полное решение для случая М(4,п) получено спуств непродолжительное время в работе 3. Бсйчг!Ге, Мопсшб, Тйеог. Сошр. Ясб 14 (1981), 19 — 37, где также предлагается решение для случая М(5, и). 15. Удваивать гл до тех пор, пока результат не превзойдет и. Для этого придется выпол- нить (!8(п/ог)) + 1 операций удваивания.
16. Привсех (га,п), за исключением (гл,ц) = (2,8), (3,6), (3,8), (3,10), (4,8), (4,10), (5,9), (5, 10). При этих значениях число сравнений на единицу больше оптимального. 17. Предположим, т < и, н пусть г = !8(п/гл) — 6, Тогда !8 (ы+") > !8пы — !8т! > т (8 и — (т !8 т — т+ 1) = т(г + д) + т — 1 = Н(т, гг) + рт — (2~ т ! > Н(т, и) 4 йгл — 2г т > Н(т, и) — гп. (Неравенство т! < пг 2' являетсв следствием того, что й(гл — й) < (гп/2) прн1<Й<т) 19. Слейте сначала (Аы..., А ) с (Вг, Вм..., Вг!„гз1), Тогда останется вставить нечет- ные элементы Ви-г в последовательность а; элементов А, 1 < г < (и/2), где аг +от+ + аг„гг! < гл. При выполнении этого последнего действия на каждое значение г придется выполнить а; операций, так что лля завершения сортировки достаточна выполнить еше не более т сравнений, 20.
Применить неравенство (12). 22. В работе В.. М!с)гэе! Таппег, ЯСОМР 7 (1978), 18-38, показано, что в алгоритме нфрактальных вставок"' используется в среднем не более 1.06 )8 (™'"") сравнений. В работе Ь. Ко(!4г, Сошрогегэ и Аг!!бс!а! 1пс. 5 (1986), 335-344, проанализирована поведение ьв среднем"' алгоритма Н. 23.
Соперник имеет матрицу Х размера и к и, элементы которой к; вначале все равны единице. Когда алгоритм спрашивает, имеется ли равенство А; = Вг, соперник устанавли- вает ко равным нулю, Он отвечает "нет" до тех пор, пока перманент матрицы Х не станет равным нулю. В этом случае соперник отвечает "да" (ему ничего не остается делать, иначе выполнение алгоритма немедленно завершится!) и исключает из матрицы Х строку ! и столбец /; полученная матрица (и — 1) х (и-1) будет иметь ненулевой перманент, Соперник продолжает и дальше действовать таким образам, пока у него не останется матрица 0 х О. Если перманент близок к нулю, момгно перекомпоновать строки и столбцы таким образом, что г = ! = 1 и все единицы будут на главной диагонали матрицы.
Таким образом перманент обращается в нуль, есля км +- 1; значит, мы должны получить яыяы = 0 для всех я > 1. Отсюда следует, что, по крайней мере, и нулей удаляются прн первом ответе "да" соперника, а и — 1 — при втором ответе и т. д. Выполнение алгоритма завершится лишь после получения и положительных ответов на неизбыточные вопросы н после того как мы зададим, по меньшей мере, и+(п — 1)+ +1 вопросов (1АСМ 19 (1972), 649-659). Анапогичньге рассужденяя привелут нас к загглючевию, что необходимо и+(и — 1)+ .+ (н — т+ 1) вопросов для того, чтобы выяснить, что А С В при )А( = т < и ы )В(, 24.
Грубое предварительное слияние потребует ие более т + 9 — 1 слияний, а камгдая последующая процедура вставки — не более г. Эта верхняя оценка не может быть умею щена. Таким образом, максимальное число сравнений будет тем же, что н в алгоритме Н (см. (19)). 26. В общем, сложность этой задачи такова же, как и для отдельного случая, когда камгдый элемент яц — это либо О, либо 1 и к = -'. Тогда каждое сравнение эквивалентно анализу бита ка и мы стремимся определить всю матрицу, просматривая только младшие разряды.
Любая задача сортировки (1) соответствует матрице 0-1, если установить кп = (Аг >В +~-,). (В работе 52 Ь!и!а1, М. Яа)гэ, 1. А18оНгйлгэ 6 (1985), 86-103, этот вывод приписывается Дмг. Ширеру (1. Я!геагег). Аналогичный результат связывает сортировку и поиск при любом частичном упорядочении.) РАЗДЕЛ 5.3,3 1. Игрок ХХ проиграл игроку дб,поэтому известно,что игрок ХЮ глабее,чем игроки ОБ, ХХ и 12. 2. Пусть я есть Х-й в порядке убывания элемент н пусть Я есть множество всех элементов р, таких, что выполненных сравнений недостаточно для доказательства того, что к < р и р < я. Суп»ествуют перестановки, удовлетворяющие всем выполненным сравнениям, но в них все элементы Я меньше, чем з, действительно, мы можем потребовать, чтобы все элементы Я были меньше, чем и, н вло.кить полученное частичное уиорядочеине в лннейпое упорядочение.
Аналогично существуют допустимые перестановки, в которых все зле»»энты о больше, чем г. Следовательно, мы не можем знать положение я, если Я ие пусто. 3. Соперник может считать проигравшего в первом сравнении слабейшим среди всех игроков. 4. Предположим, что наибольшие (» — 1) элементов — это (ам...,а»,), Любой путь определения наибольших Х-эле»пщтов на дереве сравнений, совместимый с этим предположением, должен включать„по меньшей мерв, и-1 сравнений для определения наибольшего из оставшихся п — Х + 1 элементов. Каждый нз таких путей должен иметь не менее и — 1 точек выбора альтернатив, т. е. нх в сумме существует не менее 2" '. Таким образом, каждый из и' выборов наибольших (Х вЂ” 1) элементов должен появиться не менее чем в 2" ' листьях дерева. б.
Действительно, ИО(п) < Х)(п) + Я(Х вЂ” 1), как следует из упр. 2. 6. Пустьд(1м1м... „1,) = »и-2+~!б(2п+2О р +2~ )1, идопустнм,что( = ддля1»+Х»+ .+Х„+2гл < Хт'. Докажем, что,х = д, если Х»+Х»+ +1 +2гл = А'. Мы можем считать, что 1» > Хэ » 1м.
Существует лишь несколько способов выполнения первого сравнения. Сщраи»егия АЦ,1) при 3 < Х». Сравнить наибольший элемент группы 3 с наибольшим элементом группы Х», Это дает соотношение У(11,.,1 ) < 1+у(1м- -,Хх — м(х+1,11+м,,Х»»мХ»+1 1 ) =д(Хп ° °,Хг-м(х,(хеп...,Х»-м(1,1»»м,Х ) > д(Хм,Х ).
Стратегия Во, й) прн 1» > О. Сравнить наибольший элемент группы 3 с одним из меньших элементов группы и. Это дает соотношение у(Хм...,1 ) < 1+ п»ах(о,~д) = 1 +Хд, где и = д(Хм.,Х -мХ»+м,Х ) < д(Хп,1 ) — 1, хд д(Хп--.,Х»»мХ»-1,1»+м,Х ) > д(П,,Х ) — 1. Соцкпвегвл С(Х',й) при 3 < й, ХХ > О, Х» > О. Сравнить один из меньших элементов группы 3 с одним из меньших элементов группы й. Соответствующим соотношением будет ПХм..., Х ) < 1 + д(Хм, .., Х»-м Х» — 1, Х»+м °, Х, ) > д(Хп ., Х, ).
Значение Х(Хм..., Х,~) найдем, взяв минимум правой части среди всех этих стратегий; следовательно, 1(Хм...,Х ) > д(Хп...,Х ). Если т > 1, то стратегия А(гв — 1,гл) показывает что Х(Хм...,Х~) < д(1п.,.,1 ), поскольку д(Хм.,.,1»м1 ) =д(1„...,1 м1»), если Х» » ° Х . (Доказательс»пео. (Хб(М+ 2')1 = ~Ъ|(М+ 2")1 при О < а < Ь, егли М есть положительное кратное 2".) Егли щ = 1, используйте стратегию С(1, 1). (В статье С.
С. Кислицына определена оптимальная стратегия А(щ — 1, т) и вычислено х (Х, 1,...,1) в замкнутом виде; общая формула для 1 и это упрощенное доказательство были получены Флойдом в 1970 году.) у. При 3 > 1, если Х + 1 находится в и', с- равно 1 плюс число сравнений, необходимых для выбора сведующего в порядке убывания элемента и'. Аналогично в случае, если 3 + 1 находнтсв в а", с1 всегда равно О, так как деревья в конце всегда выглядят одинаково. 8. Другими словами, существует ли расширенное бинарное дерево с и внешними узлами, такое, что сумма расстояний от корня до Х вЂ” 1 наиболее удаленных внутренних узлов меньше, чем соответствующая сумма для полного бинарного деревад Ответ на этот вопрос отрицательный, поскольку (как нетрудно показать) к-й в порядке убывания элемент д(о) больше или равен Щп — к)„) при всех а.
9. (Для всех путей используются шесть сравнений, однако зта процедура не оптимальна для Чз(5).) печно 10. (Медиана найдена вручную путем проб и ошибок; использовано упр. б, чтобы упростить нахождение полезных линий.) 11. См. )пГоттасюп Ргосеззшб Х ейетз 3 (1974), 8-12. 12. После удаления наименьшего из (Л»,Хэ»Х»,Хэ) получаем конфигурацию плюс и — 3 изолированных элементов; третий нз ннх может быть найден еще за 1»э(п — 1) — 1 шагов. если а > 2; (а-2. Ь+1, с+1, »1), (а-1, Ь, с+1, »!) или (а — 1, Ь+1, с, »4), (, 5-1, с, »(+Ц, (о, Ь, с-1, »(+1), если а > 1; если Ь> 2; если с > 2. Отсюда сле»п»ет» что требуется ] 1»а] + Ь+ с — 2 сравнений, чтобы из (а»Ь,с,»() получить (О, 1, 1, о+5+с+д — 2).
[Сас САСМ 18 (1972), 462-464. В работе БОСЯ 16 (1975), 71-74, Пол доказал. что этот алгоритм также минимизирует среднее число сравнений.] 17. Используйте (6) сначала для наибольшего элемента, затем — для наименьшего. Обратите внимание на то, что !и/2] сравнений общие для обоих случаев. 18. 1А(п) < 18п — 151 при всех достаточно больших п, 21. Шаг О. Постройте два дерева турниров с выбываннем размерами 2ь и 2ь '+'. Шлг 2 для 1 < 1 < б (К этому моменту уже выведено 1' — 1 наиболыпих элементов. Оставшиеся элементы вместе с набором фиктивных, каждый из которых равен — со, появятся теперь в двух деревьях, А и В, где А имеет 2» листьев, а  — 2" '+».) Пусть о — победитель в А, и предположим, что а выиграл у ае, а», ..., аь», где о» вЂ” победитель среди 2' элементов.
Аналогично пусть Ь н Ьо, Ь», ..., Ьь»~»-» победитель и обладатель второго места в В. Если» = 1, вывести шах(а, Ь) и прекратить выполнение. В противном случае *'нарастить" другой уровень в нижней части В, вставив 2"""+» фиктивных элементов, каждый из которых считается проигравшим в первой встрече с участником В. (Наша стратегия — влить В в А, если возможно, 'заменив им поддерево 13.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
