Д. Кнут - Искусство программирования том 3 (2-е издание) - 2001 (Часть 1) (1119456), страница 56
Текст из файла (страница 56)
Каким образом можно резко сократить число таких случаев 7 7. [21] Докажите неравенство (П). 8. [24] Докажите, что М(2,8) < 6. Для этого придумайте такой алгорнтла слияния двух элементов с восемью другими, который бы выполнял не более шести сравнений. 9. [27) Докажите, что три элемента можно слить с шестью элементамн не более чем за семь шагов. 10. [ЯЯ) Докажите, что пять элементов можно слить г девятью не более чем за двенадцать шагов. [Укеэаааие. Опыт введения соперника подсказывает, что начать нужно со сравнения Аа: Вэ, а затем, если Аа < Вэ, попытаться сравнить Аэ: Вэ.] 11.
[МЯО) (Ф. Хуан и Ш. Линь.) Пусть яэь = [2ь Н], «ы+а = [2" 1т2] при к > О, так что (Яе,ра,йэ, ° .) = (1,1,2,3,4,6,9,13,19,27,38,54,77,...). Докажите, что для слияния двух элементов с яа элементами требуется в худапем случае более чем 1 сравнений, однако слить два элемента с Яа — 1 можно не более чем за 1 шагов. [Указание. Покажите, что если и = уа или и = Яа — 1 н если нам нужно слить (Аа, Аэ) с (Ва, Вэ,..., В ) за 1 сравнений, то наилучшее первое сравнение — зто Аэ ' Вэ,, ] 12. ]МЯ1] Пусть В„(а, Я) — наимепыпее число сравнений, необходимое для сортировки различных объектов (о, ау, Хм..., Л ), если заданы соотношения а < аЯ, Ха < Лэ « .
Х„, и < Хааа, аа > Х„„.. (Условие а < Хсеа или аэ > Х„а теряет смысл, если а > и или Я > и. Поэтому В„(п, и) = М(2, и).) Ясно, что В„(0,0) ш О, Докажите, что В (а,у) = 1+пил( шш шах(В„(0-1,2), В„ь(а — к, Я)), а<э(! ашп апах(В (а, Ус-1), Ве ь(а,у-й))) абс Яа при 0 < а < аа, О < Я < н, а'+ Я > О. 13. [МЯЯ] (Р. Л. Грэхем (К. 1, Ога1ааап).) Покажите, что решение рекуррентного соотношения нз упр.
12 монако выразить пате;ауюпаим образом, Определим функцию П(х) при О < х < оо такимй правилами: 1, если О<х<-; э э — а 1+ 1С(8х — 5), если Уэ < х < -"; эб(2х — 1), если 1 < х < 1; О, если 1<я<со. (Рис 38 ) Поскольку В (а Я) = В (Я а) н В (О, а) = М(1,У), шэжно считать, ато 1 < а < у < и Пусть р = [18 а], 9 = [)8 Я], г = [18 и] и пусть 1 = и — 2" + 1. Тогда В (а, Я) ш р+ 9+ Я (а, Я) + Т (а, Я), где функции 5 и Т„принимают значении 0 илн 1а тогда и только тогда, когда тогда и только тогда, когда где и ш 2эС(1~2э) и аа = 2~ эС(1~2» э) 9<силн(а — 2э >виу — 2" >в), р<гили(1> — 2" иа — 2" >и), 1,0 о.в 0.77 0.5 ОА о.в О.! 0.О О.О ОЛ О.2 О.В ОЛ О.В О О О.7 О.В 0.9 1.0 1.1!.2 1Л Рнс. 38.
Функция Грэхема (см. упр, 13). (Это, быть может, самое сложное рекуррентное соотношение нз всех, которые, возможно, когда-либо будут решены!) 14. [41] (Ф. К. Хуан.) Пусть Ьз» = ] е 2 ] — 1, Ьз»+» = Ьэа + 3 ° 2" ", Ьые» = [»7 2» — Щ при Й > 3 и начальные значения подобраны так, что (Ьа,Ь!,Ьм, ..) = (1,1,2,2,3,4,5,7,9,11,14,18,23,29,38,48,60,76, ), Докажите, что М(3, Ь1) > 1 и М(3, Ь, — 1) < 1 при всех С, определяя таким образом точные значения М(3, и) для всех и.
16. [Ы] На шаге Н1 алгоритма бинарного слияния может потребоваться вычислить значение [18(п/т)] прн и > т. Как можно легко вычислить это значение, не применяя операций деления и взятия логарифма", 16. [18] При каких т и и, 1 < т < и < 10, оптимален алгоритм бинарного слияния Хванга и Шень Динку 17. [М25] Докажите неравенство (21), [Указание. Это неравенство не очень жесткое.) 18, [М49] Исследуйте сре»!исс число сравнений, выполняемых алгоритмом бинарного слияния. ь 19.
[23] Докажите, что функции М удовлетворяет неравенству (22). 20. [29] Покажите, что если М(т, и+1) < М(т+1, и) при всех и» < п, то М(т, и+1) < 1 + М(т, и) при всех т < и. 21, [М47] Докажите или опровергните соотношения (23) и (24). 22. [М43] Исследуйте минимальное средксе число сравнений, необходимых для слияния и» элементов с и элементами. 23. [М31] (Э. Рейнгольд(Е. Вешбо!й).) Пусть(А», .,А„)и (Вм...,В ) — множества, солержашие по и элементов. Рассмотрите алгоритм, который пытается проверить наличие р»ес»»стев между множествами исключительно путем сравнений равенства влементав зтнх множеств.
Таким образом, в процессе выполнения алгоритма задаются вопросы наподобие "А» = В 7" при некоторых» и 1 и выбирается дальнейший путь вычислений в зависимости ат тога, был ли ответ положительным или отрицательным, Определив подходящего соперника, докажите, что любой талой алгоритм в наихудшем случае будет вынужден выполнить не менее -'п(п+ 1) сравнений. 24. (хх) (Ю. Л. Лалер (Е.
1.. 1.аэ'1ег).) Каково максимальное число сравнений, необходимых дэя следующего алгоритма слияния лэ элементов с о > пэ элементами? "Устюювить 1 э — (18(о/гп)) и использовать алгоритм 6.2АМ для слияния Аь Аэ, ..., А, с Вэч Вэ.эч ..., Вэ эч где д = (и/2'). Затем эстээить каждый элемент А.
на свое место среди Вэ." э 26. [26) Предположим, что (х;.) есть матрица пэ х и с неубывающими строками и столбцамя: хо < хп+щ при 1 < 1 < пэ и хп < х,пап при 1 < 1 < и. покажите, что м(ш, и) есть мянилэальное число сравнений, необходимых дэя того, чтобы выяснить, присутствует ли данное число х в матрице, если эсе сравнения выполняются между х и некоторым элементом матрицы. х5.3.3, Выбор с минимальным числом сравнений При поиске наилучших возможных процедур для выбора 1-го элемента в порядке убывания из л элементов мы встречаемся с классом задач, подобных рассмотренным в предыдущем разделе.
История постановки и поиска решений этой проблемы восходит к занимательному (хотя и серьезному) эссе преподобного Ч. Л. Доджсоиа (С. 1,. Подяэоп) о турнирах по теннису, появившемуся в Я. 1апэеэ'э Сэхесэе 1 августа 1883 года (с. 5-8). Доджсон, который, разумеется, более известен как Льюис Кэррол, рассматривал несправедливые правила, по которым присуждались (и до сих пор присуждаются) призы в турнирах по теннису, Рассмотрим, например, рнс. 39, на котором показана схема типичного турнира с выбыванием между 32 игроками, помеченными 01, ОМ,..., 66. В финале игрок 01 одерживает победу над игроком 06, поэтолэу ясно, что игрок 01 — чемпион и заслужил первый приз, Несправедливость проявляется в том„что игрок 06 обычно получает второй приз, хотя он может и не быть вторым по силе игроком.
Выиграть второй приз можно, даже если играешь хуже половины игроков турнира. В самом деле, как заметил Доджсон, второй по силе игрок выигрывает второй приз в том и только том случае, если первоначально он и чемпион находились в противоположных частях турнирной таблицы; для турнира с 2" участниками зто происходит с вероятностью 2" '/(2" — 1), так что почти в половине случаев второй приз получает не тот игрок! Если проигравшие в полуфинале (игрок 25 и 17 на рис, 39) соревнуются за третий приз, то весьма маловероятно, что третий по силе игрок получит третий приз. Поэтому Доджсон решил найти такую схему турнира, которая правильно апределяет второго и третьего по силе игроков в предположении, что соблюдается закон транзитивности, (Иначе говоря, если игрок А побеждает игрока В, а В побеждает С, то можно считать, что игрок А победит С.) Доджсон придумал процедуру, в которой проигравшим дается возможность сыграть еще несколько игр, пока не станет определенно известно, что онн слабее других трех игроков.
Пример схемы Доджсона приводится на рис. 40. Здесь изображена сетка игр дополнительного турнира; его следует провести вместе с турниром, схема которого показана на рис. 39. Доджсон попытался составить нары игроков, у которых до сих пор были равные результаты, и исключить матчи между игроками, побежденными одним и тем же участником. В таком конкретном примере игрок 16 проигрывает игроку 11, а игрок 16 проигрывает игроку 19 в нервом туре; после того как игрок 16 проигрывает игроку 10 во втором туре, игрок 16 исключается, так как теперь известно, что он слабее игроков 11, 1х и 10. В третьем туре исключается встреча игроков 10 и Я, Чемееон = 01 Тур 5 (Полуфинал) 01 05 Тл 4 ш 26 Тур 3 01 02 25 2У Г вЂ” ' — ? à — '-1 à — '-? Г-? — ? Тур 2 01 08 02 ?Ц 25 26 2У 80 Г~? Г!? Г ? Г?? Г ! ! ? ! ? Г \ Тур 1 01 07 02 1О 02 08 04 ОУ 25 28 26 27 22 82 60 Ш 05 17 05 11 17 18 Г ? à — ' — ? Г-? — ? Г-? — ? 05 06 11 И 17 20 18 21 Г"Ч Г'1 Г"Ч ГЬ? ГЬ? Г"1 ГЬ? ГЬ? 05 И 06 Ц !! И 12 18 17 26 20 28 И 16 21 22 Рнс.
39. Турнир между 32 игроками с выбыванием. Второе место = 02 Тур б 05 тур 7 Ой ОУ 17 à — 1 Г'-? 05 11 17 25 à — !-? Г"? 02 26 И 18 И Г ? Г ? Г ? РЭ 04 26 80 И 14 Г?? Г ? И16ЦИ 06 06 07 Г'-? 06 йу 07 йУ Г?? ! ! ? Г ~ ! 06 27 22 81 07 08 Г 1 Г ? Г?~ Г! ? 27 28 28 Я! Ш 22 07 10 06 ОУ Тур б 02 Тур 5 Ой ГЬЭ ! Тур 4 02 20 12 Г'-? Г ? тур з йО 21 ?й 10 Г? тур г 1У 22 Рис. 40.
Сетка теннисного турнира Льюиса Кэррола (в дополнение к сетке, представлен- ной на рнс. 39). На математическом семинаре в 1929 — 1930 годах Гуго П1тейнгауз (Нпйо БсешЬанз) сформулировал постановку задачи нахождения аанинмааьиоао числа поединков, требуемых для определения первого и второго игроков в турнире, если всего так как они оба были побеждены игроком 18, но нельзя автоматически исключить проигравшего во встрече игроков 19 и 91. Было бы приятно сообщить, что схема турнира, предложенная Льюисом Кзрролом, оказалась оптимальной, но, к сожалению, это не так.
Из за??иси в его дневнике от 23 июля 1883 года явствует, что он составил зто эссе примерно за шесть часов и чувствовал, что, "поскольку [теннисный~ сезон приближается к копну, будет лучше сделать так, чтобы оно (эссе] появилось побыстрее, чем чтобы оно было хорошо написано". В его процедуре делается больше сравнений, чем необходимо, и она не сформулирована достаточно четко, чтобы квалифицировать ее как алгоритм. С другой стороны, в ней имеются некоторые очень интересные аспекты, если судить с точки зрения параллельных вычислений. Предложенную схему можно считать отличной турнирной сеткой, поскольку Кэррол включил в нее несколько драматических эффектов; например, он определил, что два финалиста должны пропустпть пятый тур и сыграть допоаннтельный матч в турах б и 7.
Однако организаторы турниров, по-видимому, сочли его предложение излишне логичным, и потому система Кэррола, скорее всего, никогда не испытывалась. Вместо этого практикуетсн метод "'рассеивания" более сильных игроков, чтобы они попали в разные части дерева. имеется и > 2 участников. В работе Л. ЯсЬгеюг, Масйеиэ Ро!эка 7 (1932), 154-160, приведена процедура, требующая самое большее п — 2+ ()йп! матчей. В ней использован, по существу, тот же метод, что и на первых двух стадиях процесса, который мы назвали сортировкой посредством выбора из дерева (см. раздел 5.2.3, рис. 23), однако не выполняли дополнительных сравнений с -оо.
В работе также утверждается, что п — 2+ (16п) — наилучшее возможное значение, но приведенное доказательство было ошибочным, квк и еще одна попытка доказательства, предпринятая в работе Я. 3!прес)п', Со!)о9шшп Масйешас!сшп 2 (1951), 266 — 290. Прошло 32 года, прежде чем С. С. Кислицыным было опубликовано правильное, хотя и очень сложное, доказательство [Сибирский математический журнал 5 (1964), 557-564). Пусть Ъ~(п) обозначает минимальное число сравнений, требуемых для определения 1-го в порядке убывания элемента из и элементов, 1 < $ < п, и пусть И'с(п) равно наименьшему числу сравнений, необходимых для определения наибольшего, второго,... и 1-го элементов всех сразу. Вследствие симметрии имеем ь!(п) = Рв+~- (и), очевидно также, что (2) (3) (4) У~(п) = И'д(п), И(п) < И;(и), И'„(и) = И'„~(п) = 3(п). Как следует из леммы 5.2.3М, (5) Ъ~(п) = и — 1.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
