Д. Кнут - Искусство программирования том 1 (1119450), страница 49
Текст из файла (страница 49)
15. [М12] Существует ли.перестановка. для которой каноническая циклическая форма без скобок и линейная форма совпадают? 16. [М15] Пусть задана пврестановка 1324 в линейной форме. Преобразуйте ее в каноническую циклическую форму, а затем удалите скобки. Повторяйте эту процедуру до тех пор, пока не придете к исходной перестановке.
Какие перестановки получатся в ходе выполнения этого процесса? 17. [М24] (а) В тексте раздела показано, что среди всех перестановок из п элементов существует всего и! Н циклов. Если эти циклы (включая единичные) записать по отдельности на и! Н листочках бумаги, а затем выбрать наугад один из этих листочков, то чему будет равна средняя длина выбранного таким образом цикла? (Ь) Запишем л! перестановок на и! листочках бумаги, наугад выберем число й и таким же случайнылс образом вытянем один из листочков. Чему равна вероятность того, что цикл, содержащий элемент й, является си-циклом? Чему равна средняя длина цикла, содержащего элемент й? ь 18.
[М27] Чему равна р„з, вероятность того, что перестановка п объектов имеет ровно й циклов длины т? Какой будет соответствующая производящая функция б' (г)? Чему равно среднее число т-циклов и каким будет среднее квадратичное отклонение? (В тексте раздела рассматривается только случай, когда си = 1.) 19. (НМ21] Пользуясь обозначениями из (25), покажите, что число перестановок Р~о в точности равно значению п1(е, округленному до блнгюойшего целого, для всех л > 1. 20. [М20] Пусть все единичные циклы выписаны явно. Сколько существует различных способов представления в виде циклов перестановки, имекзщей ас циклов длины 1, аг циклов длины 2,... (см. упр.
5)? 21. [М22] Чему равна вероятность Р(и;амссз,.. ) того, что перестановка п объектов имеет ровно ас циклов длины 1, аг циклов длины 2 и т. д.? ь 22. [НИХ] (Следующий подход, предложенный Л. Шеппом (Ь. ЯЬерр) и С. Ф. Ллойдом (Б. Р. Ь!оус!)., дает удобный и мощный метод решения задач, имеющих отношение к циклическим представлениям случайных перестановок. Вместо того чтобы считать число объектов л фиксированным, а число перестановок--переменным> будем предполагать, что мы независимо выбираем величины анас, аз..., рассмотренные в упр. 20 и 21, в соответствии с некоторым распределением вероятностей. Пусть ш — любое действительное число между 0 и 1.
а) Предположим, что выбраны случайные переменные ам аз,аз,... согласно правилу, которое гласит: "Вероятность того, что а = 1с, равна 1'(ш,т,й)", где 1(ш,т,(с)— некоторая функция. Определите функцию 7(ш, т, й) так, чтобы выполнялись следующие два условия: (!) 2 з>о 1'(ш,т,й) = 1, где 0 < со с 1 и т > 1; (й) вероятность того, что аз + 2аг + Заз + = и н что аз = йм ссз = 1сг, сгз = 1сз, .... равна (1 — ш)ш"Р(и;йнйг,йз,...), где Р(и;йнйг,йз, ) определяется в упр. 21. Ь) Очевидно, что перестановка, циклическая структура которой илсеет вид ам сгг, аз,..., переставляет ровно аз + 2аг + Заз + объектов. Покажите, что если а„с > 1, выбираются случайно в соответствии с распределением вероятностей из п, (а), то вероятность того, что ас + 2аз + Заз + ..
ш л, равна (1 — ш)ш", а вероятность того, что сумма аз + 2аз + Заз + . бесконечна, равна нулю. с) Пусть ф(ам аз,... ) — произвольная функция от бесконечного числа аргументов ан аз,.... Покажите, что если а„з > 1, выбираются в соответствии с распределением веРоЯтностей нз п, (а), то сРеднее значение ф Равно (1 — ш) 2 „>о ш"ф . Здесь ф обозначает среднее значение ф для всех перестановок и объектов, а переменная а, представляет число 1-циклов в перестановке. [Например, если ф(амаг, .) = ас то значением ф„ будет среднее число единичных циклов в случайной перестановке л обьектов.
Из (28) следует, что фе ш 1 для всех и.] с1) Используйте этот метод для нахождения среднего числа циклов чеииьой длины в случайной перестановке п объектов. е) Используйте этот метод для решения упр. 18. 23. [НМ48] (Голомб (Со!оспЬ), Шепп (БЬерр) и Ллойд (Ь!оус!).) Обозначим через ! среднюю длину самого сзлинного цикла в перестановке и объектов. Покажите, что 1о Лп-ь -Л, с где Л 0.62433 — константа.
Докажите, что!!ш„ь, (1„— Лп — ьЛ) = О. 24. [М41] Найдите дисперсию величины А, которая является одной из характеристик времени выполнения алгоритма 1 (см. упр, 14). 25. [МРЗ] Докажите соотношение (29). ь 26. [ЛЩ] Обобщите принцип включения и исключения, чтобы получить формулу для числа элементов, которые имеются ровно в г из подмножеств Нь,Нг, .,Ям.
(В тексте раздела рассматривается только случай г = 0.) 27. [М80] Используйте принцип включения и исключения для подсчета количества таких целых чисел п в интервале 0 < и < атстг... тс, которые не делятся ни на одно из тг,тг,...,тс. Здесь ть, гиг, ..., ть и а — положительные целые числа, такие, что т Лты если г ф/с. 28. [МЯ1] (И. Каплански (1. Кар!апэ!су).) Если "перестановку Иосифа", определенную в упр.
1.3.2 — 22, выразить в циклической форме, то получим (1 5 3 6 8 2 4)(7), где п = 8 и ьп = 4. Покажите, что в общем случае эта перестановка представляет собой произведение (пп — 1 ... 21) '(пп-1 ... 2) '...(пп — 1) 29. [М85] Докажите, что циклическую форму перестановки Иосифа при сп = 2 можно получить, сначала выразив "двойную" перестановку (1, 2,...,2и), которая переводит 1 в (21) шос((2и + 1), в циклической форме, а затем рассмотрев циклы в обратном порядке и убрав все числа, которые больше и. Например, при п = 11 двойная перестановка будет иметь вид (1 2 4 8 16 9 18 13 3 6 12)(5 10 20 17 11 22 21 19 15 7 14), а перестановка Иосифа — (7 11 10 5)(6 3 9 8 4 2 1). 30.
[ЛЩ] Используя упр. 29, покажите, что фиксированными элементами перестановки Иосифа прн т = 2 будут в точности числа (2~ ' — 1)(2п + 1)/(2 — 1) для всех таких положительных с(, прн которых это выражение дает целые числа. 31. [НМЯЯ] Обобщая упр. 29 и 30, докажите, что й-м казненным для произвольных т и и будет тот, кто находится в позиции х, где х можно вычислить следующим образом: положить х +- кт, а затем присваивать х ь- [(т(х — и) — 1)/(сп — 1)) до тех пор, пока х < и. В результате среднее число фиксированных элементов для 1 < п < ььс и фиксированного т при 1ь" -+ оо будет стремиться к ~„> с (т — 1)ь/(тс ы — (т — 1)) .
[Так как это значение лежит между (т — 1)/т н 1, перестановка Иосифа имеет немного меньше фиксированных элементов, чем случайные перестановки.] 32. [М85] (а) Докажите, что для любой перестановки я = ьсьггг . гсгч+с вида гс = (2 3)'г(4 5)" ... (2 2т+1)" (1 2)" (3 4)"... (2гп-1 2т)" где каждое еь — либо О, либо 1, имеет место [яь — 1с[ < 2 для 1 < й < 2т + 1, (Ь) Для любой заданной перестановки р элементов (1, 2,..., п] постройте перестановку я указанного вида, такую, чтобы произведение рл давало единственный цикл.
Таким образом, каждая перестановка "близка" к циклу. ЗЗ. [МЮЯ] Пусть гп = 2г, а п = 2г'"'. Покажите, как построить последовательность перестановок (а,с,а,г,...,а,„; бгь,б г,... „6ь ) для 0 < 1 < т, имеющих следующее свойство "ортогонвльности". (1 2 3 4 5), если г = 1; аьсбгьа,гбгг... а,„бг„= ~ если ь ~ г. Каждое агг и )7гь должно быть перестановкой чисел (1, 2,3, 4, 5).
° 34. [М25] (7рансвонирующие 6лохи данных.) Одной из самых распространенных перестановок, использующихся на йрактике, является переход от об к ба, где и и 9 — это подстроки массива. Другими слрвами, если хек~... х ~ — — о и х хж+ю .. х еэ-г = А то нужно заменить массив хех~ ... х е ~ = а19 массивом х х ег...
х е„ачхоя~... х ,9сс Это перестановка на множестве (О, 1,..., т + н — 1), которая переводит х в (к + т) шод (гн+ п). Покажите, что каждая такая перестановка "с циклическим сдвигом" имеет простую циклическую структуру,и используйте эту структуру для разработки простого алгоритма получения нужной перестановки. 33. [МЯО] В продолжение предыдущего упражнения положим хехю .. х~~.,„+„-~ — — сгд7, где а, 9 и 7 — строки длины 1, гн и н соответственно, и предположим, что нужно заменить о97 на ч19а. Покажите, что соответствующая перестановка имеет подходящую циклическую структуру, которая позволяет получить эффективный алгоритм. [Упр.
34 рассматривалось как частный случай при пз = 0.] Указание. Рассмотрите замену (пй)(719) на ( уй)(сь9). 36. [27] Напишите для М1Х подпрограмму, реализуюшую алгоритм, который приведен в ответе к упр. 35, н проанализируйте время его выполнения.
Сравните этот алгоритм с более простым методом, в котором осуществляется переход от п97 к (о97) = 7 19 а я я я н и к 7Щ где пи обозначает полное обращение строки и, т, е. строка читается в обратном порядке. 1.4. НЕКОТОРЫЕ ФУНДАМЕНТАЛЬНЫЕ МЕТОДЫ ПРОГРАММИРОВАНИЯ 1.4.1. Подпрограммы Когда мекоторукз задачу нужно выполнить в нескольких различных местах программы, то, как правило, нежелательно каждый раз повторять ее код. Чтобы избежать этого, данный код (называемый подпрограммой) можно поместить только в одном месте и добавить несколько дополнительных команд, чтобы после завершения работы подпрограммы должным образом возобновить выполнение внешней программы. Передача управления между подпрограммами и основной программой называется связью с подпрограммами.
Каждый компьютер имеет свои специфические способы установления эффективной связи с подпрограммами, которые обычно подразумевают применение специальных команд. В И1Х для этой цели используется регистр 5. Рассматривая данную тему, будем ориентироваться на машинный язык И1Х, но аналогичные рассуждения применимы н к вопросам связи с подпрограммами для других компьютеров.
Подпрограммы используются с целью зкономии места в программе, но их применение не приводит непосредственно к экономии времени. Это происходит неявно вследствие того, что программа занимает меньше места в памяти, например меньше времени тратится на загрузку программы, уменьшается количество проходов в программе либо более эффективно используется высокоскоростная память на машинах с несколькими уровнями памяти. Дополнительным временем, которое тратится на вход в подпрограмму и выход из нее, обычно можно пренебречь.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
