Д. Кнут - Искусство программирования том 3 (2-е издание) - 2001 (Часть 1), страница 6

[М85] (Э. Т. Паркер (Е, Т. Рагйег).) Леонард Эйлер высказал предположение [р?оза Асса Асяс(. Яс! Реггоройгалш 13 (1795), 45-63, $3; написана в 1778], что уравнение ие + с'+ ш~ + хе+ у не имеет нетривиальных решений среди целых неотрицательных чисел и, е, иь х, у, ю Одновременно он предположил, что уравнение х[+. +х,", г=я„ и АРЕВЗ, АЗРЕВ, РАВЕЗ, РАМЕ, РЕАВЗ,. РВАЗЕ, РВЕЗА, ЗАРЕЗ, ВЕАРЗ, ЗРАЕВ, ЗРАВЕ, ЗРЕАВ, к которой можно еще добавить французское слово АРВЙЗ.] не имеет решения в положительных целых числах при и > 3, ио зто предположение было опровергнуто уже в наше время, когда с помощью компьютера было найдено тождество 2?з+84з+11Оз+133з = 144 [см. Ь.

1, Ьапбег, Т. Е. РагЬ!и, агк1 3. Ь. Яе!?г!г!Ее, МагЬ. СошР. 21 (1967), 446-459]. Множество аналогичных примеров было обнаружено и при и = 4 Н. Д. Элкисом (ЬЬ П. Е!Ыее) [ЛХахЬ. Сошр. 51 (1988), 825-835], Подумайте, как можно было бы использовать сортировку для поиска примеров, опровергающих предположение Эйлера при и = 6. ь 19. [24] Файл содержат болыпое количество 30-разрядных двоичных слов: хц...,хю Придумайте хороший способ нахождения в нем всех иар с азаимие дополняющими злемеишами [х„ху). (Два слова называются взаимно дополняющими, если второе содержит нули во всех разрядах, в которых были единицы в первом слове, и наоборот; таким образом, они взаимно дополняющие тогда и только тогда, когда их суагма равна (11... 1) ы если они рассматриваются как двоичные числа.) ь 20.

[Еб] Имеется файл, содержащий тысячу 30-разрядных двоичных слов хм.,., х,еее. Как бы вы стали сосшвяять список всех пар (х„х!), таких, что хс отличается ог хг не более чем в двух разрядах? 21. [ЗЗ] Как бы вы поступили, если бы вам нужно было найти все пятибуквенные анаграммы, такие как САВЕТ, САВТЕ, САТЕВ„СВАТЕ, ВЕАСТ, ВЕСТА, ?ВАСЕ; СВОЕЬ, ЬОСВЕ, ОЬСЕВ; ООЗВТ, ВОЮТ, БОВОТ? [Или если бы вы, допустим, захотели узнать, существуют ли в английском языке наборы из десяти или более анаграмм, кроме замечательной серии 22. [Мв8) Пусть даны описания весьма болыпого числа ориентированных грж)юв. Как можно сгруппировать изомерфмме графы'> (Два ориентированных графа называются изоморфными, если существует взаимно однозначное соответствие между нх вершинами и взаимно однозначное соответствие между их дугами, причем зти соответствия сохраняют инцнлентность вершин и дуг.) 23. [Щ В некоторой группе нз 4 090 человек каждый имеет оксио 100 знакомых.

Был составлен список всех пар людей, знакомых друг с другом. (Это отношение симметрично, т. е, если х знаком с р, то и 9 знаком с т. Поэтому в списке содержится примерно 200 ООО пар.) Прилумайте алгоритм, который по заданному Ь выдавал бы все клаки из й человек. (Клико — это группа людей, в которой все знают друг друга.) Предполагается, что не бывает слишком больших клик (размером более 25).

ь 24. [30) Три миллиона человек с различными именами были уоюжены рядом непрерывной цепочкой от Нью-1'1орка до Калифорнии. Каждому из них дали листок бумаги, на котором он написал свое имя н имя своего ближайшего западного соседа. Человек, находнвгпийся в крайней западной точке цепи, не понял, что ему делать, и выбросил свой листок. Остада 2 999 999 листков собрали в большую корзину и отправили в Национальный архив, в Вашингтон, округ Колумбия. Там содержимое корзины тщательно перетасовалн и записали на магнитиме ленты. Специалист по теории информации определил, что имеется достаточно сведений для восстановления списка людей в исходном порядке.

Программист нашел способ сделать это менее чем за 1 000 просмотров лент с данными, используя лишь последовательный доступ к файлам на лентах и небольшой объем оперативной памяти. Как ему это удалось? [Пругими щювамн. как, имея расположенные произвоньным образом пары (хи хпы), 1 < 1 < Х. где все хч различны, получить последовательность х~хз... хь, применяя лишь методы послеловвзельной обработки данных, которые пригодны для работы с магнитными лентами? Это сортировка в случае, когда трудно определить, какой из двух ключей предшествует другому:, мы уже поднимали этот вопрос в упр. 2.2.3-25.) 20.

[МУ1] (Дискретные лоеара~фмм.) Пусть известись что р — - простое число (довольно болыное), а а — первообразный корень по модулю р. Следовательно. для любого Ь в диапазоне 1 < Ь < р существует единственное и, такое, что о" шог( р = 6, 1 < и < р. (Это и называется индексом 6 по модулю р по отношению к а,) Как по заданному Ь найти и менее чем за Яп) шагов.

[Указашш. Пусть гп = [т/р), Попытайтесь решить уравнение а "' ш Ьа ю (по модулю р) при О < им из < пь) «5.1. КОййБИНАТОРНЫЕ СВОЙСТВА ПЕРЕСТАНОВОК Пйгйстлиовкой конечного множества называется некоторое расположение его элементов в ряд. Перестановки особенно важны при изучении алгоритмов сортировки, так как они служат для представления неупорядоченных исходных данных.

Чтобы исследовать эффективность различных методов сортировки, нужно уметь подсчитывать количество перестановок, которые вынуждают повторять иокоторый шаг шпъритма определенное число раз, Мы уже не рвз встречались с перестановками в предыдущих главах. Например, в разделе 1.2.5 обсуждались два основных теоретических метода построения и! перестановок и объектов; в разделе 1.3.3 были проанализированы некоторые алгоритмы, связанные с циклической структурой и мультипликативными свойствами перестановок; в разделе 3.3.2 изучались их серии монотонности. Цель настоящего параграфа — описать другие свойства перестановок и рассмотреть общий случай.

когда допускается наличие одинаковых элементов. Попутна мьь многое узнаем о комбинаторной математике. Свойства перестановок настолько красивы, что представляют и самостоятельный интерес. Удобно будет дать их систематическое изложение в одном месте, а не разбрасывать материал по всей главе. Читателям, не имеющим склонности к математике, а также тем, кто жаждет поскорее добраться до самих методов сортировки, рекомендуетгя перейти сразу к разделу 5.2, потому что настоящий раздел неиосрвдсшввнного отношения к сортировке почти ие имеет, «5.1.1.

Инверсии Пусть аг ав...а„— перестановка множества (1,2,...,и). Если 1 с у и а, > а,, то пара (а,,а ) называется инверсией перестановки; например, перестановка 3142 имеет три инверсии: (3,1), (3,2) и (4,2). Каждая инверсия — это пара элементов, "нарушающих порядок"; следоватечьно, единственная перестановка, ие содержащая инверсий. — зто рассортированная перестановка 1 2...и. Такая связь с сортировкой и является главной причиной нашего интереса к инверсиям, хотя это цонятие уже использовалось, когда мы анализировали алгоритм динамического распределения памяти (см.

упр. 2.2.2-9). Понятие инверсии ввел Г. Крамер в 1750 году в связи со своим замечательным правилом решения линейных уравнений (Хпгг. а 1'Ала)уге дев 1лялев СоигЬев А1йеЬг)йцев (Оепеуа, 1750), 657-659; см. также ТЬошаз Мшг, ТЬ«огу оЕ Вегеглц'- лаигв 1 (1906), 11-14]. В сущности, он определил детерминант и х и-матрицы следующим образом: х!1 х12 " хг« бес; = ~~, ( — 1)ы~(ю«ь "«" ~х х ... х ми гаг .

- ««„р хш х«г ° - ° х«в где сумма берется по всем перестановкам аг аг...а„из (1, 2,..., и), а 1ну(аг ог... а„) — число инверсий в перестановке. Таблица инверсий Ь| Ьг... Ь„перестановки аг аг... а„образуется, если определить Ь как число элементов слева от у, которые больше, чем ~. Другими словами, ьг — число инверсий, второй элемент которых равен 1 Отсюда, например, следует, что таблицей инверсий перестановки 591826473 будет (2) 236402210, поскольку 5 и 9 расположены левее 1; 5, 9, 8 — левее 2 и т. д. Всего эта перестановка имеет 20 инверсий.

По определению числа Ь всегда удовлетворяют неравенствам 0<5| <и — 1, 0<Ь»<п — 2, ..., 0<Ь„~ <1, Ь„=О. (3) Пожялуй, наиболее важный факт, касающийся перестановок и установленный Маршаллом Холлом (Маг»Ьай Най), состоит в том, что таблица пиверслй елпстенным образом определяет соответствуюшую перестановку. [См. Ргос. Яу»пр. Аррйед Ма»Ь.

6 (Ашег!сап Ма»Ь. БосМу, 1956), 203.[ Нз любой таблицы инверсии Ь, Ьз... Ь„, удовлетворяющей условиям (3), можно однозначно восстановить перестановку, которая ее перелила, путем последовательного определения относительного расположения элементов и, п-1,..., 1 (в этом порядке). Например, перестановку, соответствующую (2), можно построить следующим образом: выпишем число 9, затем разместим 8 после 9, поскольку Ь» = 1. Аналогично установим 7 после и 8, и 9, поскольку Ьг = 2.

Так как Ь» = 2, то 6 должно следовать за двумя уже выписанными нами числами; таким образом, имеем промежуточный результат Продолжим, приписав 5 левее, поскольку Ь» ж 0; поместим 4 вслед за четырьмя из уже записанных чисел, а 3 — после шести выписанных чисел (т. е. в правый конец) и получим 5986473. Вставив аналогичным образом 2 н 1, придем к (1). Такое соответствие важно, потому что часто можно заменить задачу, сформулированную в терминах перестаяовок, эквивалентной ей задачей, сформулированной в терминах таблиц инверсий, которая, возможно, решается проще.

Рассмотрим, например, самый простой вопрос сколько существует перестановок множества (1, 2,..., и)? Ответ должен быть равен числу всевозможных таблиц инверсий, а их легко пересчитать, так как Ь~ можно выбрать и способами, Ь» независимо от Ь» — и — 1 способами, ..., а ܄— единственным способом; итого получаем п(п-1)...1 = и! различных таблиц инверсий, Таблицы инверсий пересчитать легче, потому что значения Ьь полностью не зависят друг от друга, в то время как а» должны быть все различны.