Д. Кнут - Искусство программирования том 3 (2-е издание) - 2001 (Часть 1) (1119456), страница 20
Текст из файла (страница 20)
Предположим, мы построили некоторый глучайный путь на этом диграфе, выбрав случайным образом начальную ячейку (»,у), и случайно выбирали следующие дуги до тех пор, пока не ока- зались в угловой ячейке, из которой нет выхода. Каждый случайный выбор выполняется равновероятно, а) Пусть (а, Ь) — угловая ячейка Т и пусть У = (»е,..., »») и,У = (У»,,Ур) — - »»ножества строк и столбцов, причем»е « »» = а и Уе « Ур = Ь. Диграф содержит (»ьм) путей, множества строк и столбцов которых суть У и,У; пусть Р(У,.У) — вероятность выбора определенного случайного пути. Докажите, что Р(У, У) = 1/(н И„»...
»Ь»,» б м . »Л, ), где и = [Т]. Ь) Пусть У(Т) -- и!/[[Ьп, Докажите, что случайный путь завершается в угловой ячейке (о, Ь) с вероятностью Я(Т '! ((а, Ь)))/У(Т). с) Покажите, что результат (Ь) доказывает теорему Н и предоставляет способ формн1ювания случайной диаграммы формы Т, причем все диаграммы У(Т) равновероятны.
39. [Муу] (И. И. Пак, А. В. Стояновский, 1992.) Пусть Р— массив (пм, и ), который заполнен некоторой перестановкой множества целых чисел (1,..., и), и = и, + .. + и Следующая процедура, которая аналогична алгоритму "просеивания", описанному в раз- деле 5.2.3, может быть использована для преобразования Р в диаграмму.
Она также определяет массив Я такой же формы, который может послужить для комбинаторного доказательства теоремы Н. Р1. [Цикл по ((,у).] Выполнить шаги Р2 и РЗ для каждой ячейки (»,у) массива в обратном лексикографическом порядке (т, е, снизу вверх и справа налево в каждой строке), затем прекратить выполнение процедуры.
Р2. [Обработать Р в (», у).] Присвоить К»- Рз и выполнить алгоритм Б' (см, ниже). Р3. [Изменение !'„».] Присвоить !'„»,»»- Ян»ь,!+1 для У < Ь < э н присвоить Я„» — » -г. 3 Ниже описан тот же алгоритм, что и алгоритм Б Шуценберже, но шаги Б1 и Б2 слегка модифицированы — - распространены на более общий случай.
Б1'. [Инициализация.] Присвоить г»- », э»- у. Б2'. [Выполненоу] Если К Я Ррь»м и К < Рп,ь», присвоить Р„»- К и завершить процесс. (Алгоритм Б предполагает особый случай: » = 1, У = 1, Л = ос.) Например, алгоритм Р обрабатывает массив формы (3, 3, 2) следующим образом. если просматривать содержимое массивов Р и Я в начале кшкдого шага Р2, причем значения Р„выделены полужирным шрифтокн РРП~ УГ ФР 6 4 1 Е 4 4 1 З 4 Окончазнльный результат имеет внд а) Если Р— это просто массив 1 х н, алгоритм Р сортирует его н превращает в Какой вид при этом будет иметь массив ь)? Ь) Ответьте на тот же вопрос, но в случае, если Р имеет внд н х 1, а не 1 х н.
с) Докажите, что в общем случае получим -Ь 1 5 ЯН С гка 1:) Разработайте алгоритм, обратный по отношению к алгоритму Р, задавая любую пару массивов (Р,О), таких, что Р— диаграмма, а Я удовлетворяет условиям п, (с), [Указание. Пост1юйте ориентированное дерево, вершины которого — ячейки (1,1), а дуги— (г',у) -> ((,у' — 1), если Р;и ц > Рн цз., (1,1) -+ (1-1,у), если Р;<, Ю < РН гур гле Ь;, — число ячеек, расположенных ниже ячейки (1,1), и кн — число ячеек справа от нее. Таким образом, число возможных значений ЯН в точности равно Ьу размеру ((, у)-го уголка.
д) Теорема Н будег доказана по построению, если мы сможем показать, что алгоритм Р определяет олнозначное соответствие межлу н! способами заполнения исходной формы н парами результирующих массивов (Р, Ц), где Р есть диаграмма„а элементы в Я удовлетворяют условиям п. (с). Значит, желательно найти процедуру, обратную алго- О -ы ритму Р. Для каких исходных перестановок ачгоритм Р сформирует массив Д = (е р ) формы 2 х 2? е) Какую исходную перестановку алгоритм Р преобразует в массивы В примере (е) мы имеем дерево Его составные элементы н представляют собой ключ к обращению алгоритма Р.] 40. [ЯМ28] Предположим, что некоторая диаграмма )Онга построена путем последовательного размещения чисел 1, 2, ..., и таким способом, что выбор очередной доступной ячейки для каждого следующего числа равновероятен. Например, с вероятностью 1 зз з з з 1 т з 1 2 1 2 з 4 звк бУдет полУчеиа диагРамма (1).
Докажите, что с большой вероятностью результирующая форма (пм пз,..., и ) будет иметь пз ж ~/бп и т/$+,,/пи~, ж „lт нри О < Й < тл. 41. [до] (Весперлдок е бкбзиоглеке.) Некоторые бестолковые читатели часто возвращают книги в библиотеку и ставят их на полки где попало, Измерить вносимый при этом беспорядок можно, рассмотрев минимальное количество повторений простейшей процедуры перемещения данной книги, которое необходимо для того, чтобы все книги заняли надлежащие им места. Пусть я ж а1аз... а„— перестановка множества (1, 2,..., и). Операция удалениявставкн превращает я в а~...а, 1а<+~...аз счет+~...а или а~...ага;оте~ ...а; ~ а„1...а для некоторых 1 и у, Пусть 41з(к) — минимальное число операций удаления-вставки, которое рассортирует и и приведет его в порядок.
Можно ли выразить 41з(х) в терминах простых характеристик ят ь 42. [ЗО] (Беспорядок генов.) Молекула ДНК растения Ьобейа 1егеепз имеет гены в последовательности дг д1дздедздзде, где дг обозначает отражение слева направо дт. Те же самые гены существуют и в табаке, но в порядке дздздздедздедь Покажите, что для того, чтобы получить из дздздздэдздедг последовательность дг дздздэдздзде, необходимо пять операций и я "перебрасывания" подцелочек. (Операция перебрасывания превращает а~В-~ в пол у, если а, о и у являются цепочками.) 43. [уб] Продолжая предыдущее упражнение, покаэките, что по крайней мере и+1 операций перебрасывания необходимо для сортировки любого варианта компоновки дпдз...д„. Постройте примеры, которые требухи л + 1 операций для всех и > 3.
44. [Мду] Покажите, что среднее число перебрасываний, необходимых для сортировки случайной компоновки и генов, больше, чем и — Н„, если все 2" и( компоновок генов равновероятны. 5.2. ВНУТРЕННЯЯ СОРТИРОВКА Нлчнгм обсуждение "хорошего" процесса сортировки с маленького эксперимента. Как бы вы решили следующую задачу программирования? "В ячейках памяти й+1, й+2, 5+3, й+Ф и 5+5 содержится пять чисел. Напишите программу, которая переразмещает„если нужно, эти числа так, чтобы они расположились в порядке возрастания." (Если вы уже знакомы с какими-либо методами сортировки, постарайтесь, пожалуйста, на минуту забыть о них; вообразите, что вы решаете такую задачу впервые, не ичея никакого представления о том, как к ней подступиться.) Прежде чем читать дальше, настолтельно просим вас найти хоть какое- нибудь решение эпюй задачи.
Время, затраченное на решение приведенной вылив задачи, окупится с лихвой, когда вы продолжите чтение этой главы. Возможно, ваше решение окажется одним из следующих. А. Сортировка методом вставок. Элементы просматриваются по одному, и каждый новый элемент вставляется в подходящее место среди ранее упорядоченных элементов, (Именно таким способом игроки в бридж упорядочивают свои карты, беря по одной.) В. Обменная сортировка. Если два элемента расположены не по порядку, то они меняются местами.
Этот пропесс повторяется до тех пор, пока элементы не будут упорядочены, С. Сортировка посредстаом амбара. Сначала выделяется наименьший (илн, быть может, наибольший) элемент и каким-либо образом отделяется от остальных, затем выбираетгя наименьший (наибольший) из оставшихся и т. д. О. Сортировка путем подсчета.
Каждый элемент сравнивается со всеми остальными; окончательное положение элемента определяется после подсчета числа меньших ключей. Е. СЬециальнал сортиротса, Она хороша для пяти элементов, указанных в задаче, но не поддается простому обобщению, если элементов больше. Р. Сгюсоб ленгааа. Вы не откликнулись на наше предложение и отказались решать задачу. Жаль — вы упустили свой шанс...
Если вы дошли до этого места, то и так уже слишком много знаете. О. Новая сутермепюдика сортировки. Это существенно усовершенствованные известные методы. (Если вы нашли такую методику, пожалуйста, немедленно сообщите об этом автору.) Если бы данная задача была сформулирована, скажем, для 1 000 элементов, а не для 5, то вы моглн бы открыть и более тонкие методы, о которых речь пойдет ниже. В любом случае, приступая к новой задаче, разумно найти какую-нибудь очевидную процедуру, а затем попытаться улучшить ее. Развитие вариантов А, В и С приводит к появлению важных классов методов сортировки, которые представляют собой усовершенствованные сформулированные выше простые идеи. Было изобретено множество различных алгоритмов сортировки, и в этой книге рассматривается около 25 из ннх. Такое пугающее количество методов на самом деле — лишь малая толика всех алгоритмов, придуманных на сегодняшний день; многие уже устаревшие методы мы вовсе не будем рассматривать или упомянем лишь вскользь.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
