Книги, научные публикации Pages:     | 1 | 2 | 3 | -- [ Страница 1 ] --

УНИВЕРСИТЕТ Б. Н. ИВАНОВ дискретная математика АЛГОРИТМЫ И ПРОГРАММЫ Москва Лаборатория Базовых Знаний 2003 32.973.3 20 Рецензенты:

кафедра математического моделирования и информатики (зав. кафед рой доктор физико-математических наук, профессор А. А. Буренин);

доктор физико-математических наук, профессор В. В.

Иванов Б. Н.

Дискретная математика. Алгоритмы и программы: Учеб.

И20 собие/Б. Н. Иванов. Ч Знаний, 2003.

Ч 288 ил.

ISBN 5-93208-093-0 Книга посвящена современному курсу дискретной математики. Теоретиче ские основы курса сопровождаются практически значимыми алгоритмами, реа лизованными в конкретных компьютерных программах. Книгу можно рассматри вать в качестве хорошего справочника методов и алгоритмов дискретной матема тики, широко применяемых в практическом программировании.

Пособие рассчитано на студентов специальностей, учебные планы которых предполагают изучение каких-либо разделов курса дискретной математики, в первую очередь на математиков-прикладников, а также программистов, занятых разработкой прикладного программного обеспечения.

ББК 32.973. Серия Технический университет Учебное издание Иванов Борис Николаевич ДИСКРЕТНАЯ МАТЕМАТИКА. АЛГОРИТМЫ И ПРОГРАММЫ Художник Н. Лозинская Компьютерная верстка В.Носенко Подписано в печать 22.04.01. Формат Гарнитура Ньютон. Бумага офсетная. Печать офсетная.

Усл. печ. л. 18,0. Тираж 3000 экз. Заказ Издательство Лаборатория Базовых Знаний Телефон (095)955-0398. E-mail: lbz@aha.ru Лицензия на издательскую деятельность № 066140 от 12 октября 1998 г.

Отпечатано с готовых диапозитивов в полиграфической фирме г. Вологда, ул. Челюскинцев, 3.

й Б. Н. Иванов, ISBN 5-93208-093-0 й Лаборатория Базовых Знаний, Предисловие Глава 1. Комбинаторные схемы 1.1. Правило суммы 1.2. Правило прямого произведения 1.3. Размещения с повторениями 1.4. Размещения без повторений 1.5. Перестановки 1.6. Сочетания 1.7. Сочетания с повторениями 1.8. Перестановки с повторениями, мультимножества 1.9. Упорядоченные разбиения множества 1.10. Неупорядоченные разбиения множества 1.11. Полиномиальная формула 1.12. Бином Ньютона 1.13. Инверсии 1.14. Обратные перестановки Глава 2. Представление абстрактных объектов 2.1. Представление последовательностей Смежное представление Характеристические векторы 2.1.3. Связанное размещение 2.2. Представление деревьев 2.2.1. Представление деревьев на связанной памяти 2.2.2. Представление деревьев на смежной памяти 2.3. Представление множеств Глава 3. Методы подсчета и оценивания Производящие функции Линейные операции Сдвиг начала вправо 3.1.3. Сдвиг начала влево 3.1.4. Частичные суммы Дополнительные частичные суммы 3.1.6. Изменение масштаба 3.1.7. Свертка 3.2. Линейные рекуррентные соотношения 3.3. Неоднородные линейные рекуррентные соотношения. 3.4. Обобщенное правило произведения 3.5. Принцип включения и исключения 3.6. Ладейные многочлены и многочлены попаданий 3.6.1. Ладейные многочлены 3.6.2. Многочлены попаданий Содержание Глава 4. Генерация комбинаторных объектов Поиск с возвращением 4.2. Перестановки различных элементов 4.3. Эффективное порождение перестановок 4.4. Порождение подмножеств множества 4.5. Генерация размещений с повторениями 4.6. Порождение сочетаний 4.7. Порождение композиций и разбиений 4.8. Генерация случайных перестановок Глава 5. Сортировка и поиск Сортировка вставками 5.2. Пузырьковая сортировка 5.3. Сортировка перечислением 5.4. Сортировка всплытием Последовательный поиск 5.6. Логарифмический поиск 5.7. Сортировка с вычисляемыми адресами Глава б. Введение в теорию графов. Алгоритмы на графах Основные понятия и определения ПО 6.2. Представления графов Матрица смежности графа 6.2.2. Матрица инцидентности графа 6.2.3. Матрица весов графа 6.2.4. Список ребер графа 6.2.5. Структура смежности графа Метод поиска в глубину 6.4. Отношение эквивалентности 6.5. Связные компоненты 6.6. Выделение компонент связности 6.7. Эйлеровы графы 6.8. Остовные деревья Жадный алгоритм построения минимального остовного дерева 6.8.2. Алгоритм ближайшего соседа построения остовного дерева 6.9. Кратчайшие пути на графе 6.10. Потоки в сетях Клики, независимые множества 6.12. Циклы, фундаментальные множества циклов Листы и блоки 6.13.1. Листы 6.13.2. Блоки 6.13.3. Поиск блоков в глубину Содержание Двудольные графы 6.14.1. Условия существования двудольных графов 6.14.2. 6.14.3. Алгоритм определения максимального 6.14.4. Системы различных представителей Связь системы различных представителей и двудольных графов 6.14.6. Задача о назначениях 6.15. Хроматические графы 6.16. Диаметр, радиус и центры графа Глава 7. Введение в теорию групп. Приложения 7.1. Определение группы 7.2. Гомоморфизм групп 7.3. Смежные классы 7.4. Строение коммутативных групп 7.5. Строение некоммутативных групп 7.6. Симметрическая группа подстановок Действие групп на множестве 7.8. Цикловой индекс группы 7.9. Теория перечисления Пойа 7.10. Цикловая структура групп подстановок 7.10.1. Цикловой индекс группы, действующей на себе... 7.10.2. Цикловой индекс циклической группы 7.10.3. Цикловой индекс симметрической группы Глава 8. Элементы теории чисел Наибольший общий делитель 8.2. Наименьшее общее кратное 8.3. Простые числа 8.4. Сравнения, свойства сравнений 8.5. Полная система вычетов 8.6. Приведенная система вычетов 8.7. Функция Эйлера 8.8. Функция Мёбиуса. Формула обращения Мёбиуса Задачи и упражнения Ответы Литература Предметный указатель к дискретной математике относят такие ти математического как комбинаторика, теория чисел, математическая логика, теория алгебраических систем, теория графов и сетей и т.д. Дискретная математика всегда оставалась наиболее динамичной областью знаний. Сегодня наиболее зна чимой областью применения методов дискретной математики является область компьютерных технологий. Это объясняется не обходимостью создания и эксплуатации электронных вычисли тельных машин, средств передачи и обработки информации, автоматизированных систем управления и проектирования. На грани дискретной математики и программирования появляются новые дисциплины, такие как разработка и анализ вычислитель ных алгоритмов, нечисленное программирование, комбинатор ные алгоритмы, алгоритмизация процессов. Дискретная математика и примыкающие к ней дисциплины изучаются во всех университетах и институтах, где осуществляется подготовка специалистов в области программирования, математики, а также по экономическим, техническим и гуманитарным направлениям.

Цель написания учебного пособия Ч научить студентов не то лько основам дискретной математики, но и показать ее роль в со временных компьютерных технологиях, вооружить читателя ме тодами, применяемыми для решения широкого круга задач. По собие написано в доступной форме, достаточно полно и строго.

Особое внимание в книге уделяется вопросу практической компьютерной реализации. В каждом конкретном случае содер жится достаточно информации для применения рассматривае мых методов на практике. В этом отношении много полезного найдет читатель, более склонный к программистской работе и интересующийся предлагаемыми алгоритмами в силу их практи ческого использования. Для любого заинтересованного читателя рассматриваемый в пособии набор приемов и правил алгоритми ческого характера может составить хорошую основу формирова ния культуры разработки, анализа и программной реализации ал горитмов.

Комбинаторные схемы этой главе будет сделан обзор комбинаторных формул, наиболее важных для вычислительных задач. Мы не ставим себе целью сделать этот обзор всеобъемлющим, а хотим сосредоточить внимание читателя на таких формулах, которые он мог бы недо оценить или даже совсем не заметить. Заинтересованному чита телю рекомендуется обратиться к специальной литературе.

Введем некоторые важные обозначения. Множества будем обозначать заглавными буквами. Множества состоят из элемен тов, которые будем обозначать малыми буквами. Так, запись а что элемент а принадлежит множеству А. Такие мно жества будем изображать перечислением элементов, заключая их в фигурные скобки. Например, х, Количество элементов в множестве называется мощностью и записывается как | А \.

Пусть имеются два множества А и В. Рассмотрим все пары ментов при условии, что первый элемент берется из множества а второй Ч из множества В. Полученное таким образом множест во называется прямым произведением множеств В. На помним некоторые операции над множествами, которыми время от времени будем пользоваться.

а Ч прямое произведение множеств.

А | х еА v х Ч объединение множеств.

А - | х л х Ч пересечение множеств.

А \В - | х еА л х Ч разность множеств.

0 Ч пустое множество.

Ч универсальное множество.

A =U\ А = | х дополнение множества.

1.1. Правило суммы Пусть Аи ВЧ конечные множества такие, что А = и В \ = п. Тогда I = т + п.

Предисловие Практическая компьютерная реализация большого количест ва рассматриваемых задач потребовала включения в книгу специ альных разделов дискретной математики, таких как представле ние абстрактных объектов, сортировка и поиск, порождение ком бинаторных объектов. Однако увеличение объема материала по собия только лишь усилило многие вопросы, позволило уточнить их суть, а также придать общее звучание разделам курса, которые на первый взгляд никоим образом не связаны. Книгу можно рас сматривать в качестве хорошего справочника методов и алгорит мов дискретной математики, широко используемых в разработ ках прикладного программного обеспечения.

Уровень математической подготовки, требующийся для пони мания материала книги, может меняться от главы к главе. Мини мум необходимых познаний в программировании соответствует уровню первокурсника, уже научившегося писать довольно про странные программы. Необходимый уровень математического образования соответствует типичной подготовке студента, про слушавшего ряд основных математических курсов, таких как ма тематический анализ, аналитическая геометрия, линейная алгеб ра.

Учебное пособие ориентировано на семестровый лекционный курс, читаемый автором на механико-математическом факульте те Дальневосточного государственного технического университе та. Без сомнения, книга может составить хорошую основу примыкающих к дискретной математике, таких как информати ка, алгоритмизация процессов, анализ вычислительных алгорит мов.

Учебное пособие предназначено прежде всего для студентов специальности Прикладная математика, а также студентов дру гих специальностей, изучающих дискретную математику и про граммирование. Книга будет полезна преподавателям, аспиран там и научным работникам, применяющим методы дискретной математики в прикладных задачах.

1.3. Размещения с повторениями Интерпретация. Если элемент а можно выбрать т спосо бами, а элемент b Ч способами, то выбор элемента х можно осуществить т + п способами. Пусть Ч попар j но непересекающиеся множества, Xj = 0, где Тогда, оче k k видно, выполняется равенство 1.2. Правило прямого произведения Пусть А и В Ч конечные множества, | | и п, тогда = Интерпретация. Если элемент а можно выбрать т способа ми и если после каждого такого выбора элемент b можно вы брать п способами, то выбор пары поряд ке можно осуществить \А х - = т Х п способами. В этом случае гово рят, что выбор элементов множества А не зависит от способа вы бора элементов множества В. Пусть теперь Ч произвольные множества, Тогда Задача. Найти число маршрутов из пункта пункт пункт К. Из 5 дорог, из KB NЧ 3 дороги.

Решение. Введем два множества: S= дороги из Мв К, дороги из KB N. Теперь дорогу из Мв но представить парой где 1, 2, 3, 4, 1, 2, 3. Значит, S х Т Ч это множество всех дорог из N, количество которых равно 1.3. Размещения с повторениями Задача формулируется следующим образом. Имеются пред меты п различных видов Из них составляют всевоз можные расстановки длины k. Например, становка длины Такие расстановки называются размещения ми с повторениями из п по k (элементы одного вида могут повто ряться). Найдем общее число расстановок, среди которых две расстановки считаются различными, если они отличаются друг 1. Комбинаторные схемы от друга или видом входящих в них или порядком этих предметов. При составлении указанных расстановок длины k на каждое место можно поставить предмет любого вида. Рас смотрим множества такие, что = =... - =. Тогда все размещения с повторениями составят мно жество По правилу прямого произведения по лучаем, что общее число размещений с повторениями из л по равно Задача. Найти количество всех пятизначных чисел.

Решение. Введем пять множеств: = = Тогда все пятизначные числа составят прямое произведение указанных множеств х х х х Соглас но правилу прямого произведения, количество элементов в мно жестве х х х х равно =90000.

Размещения без повторений Имеются различных предметов Сколько из них можно составить расстановок длины k? Две расстановки счита ются различными, если они отличаются видом входящих в них элементов или порядком их в расстановке. Такие расстановки называются размещениями без повторений, а их число обо значают При составлении данных расстановок на первое место можно поставить любой из имеющихся п предметов. На второе место теперь можно поставить только любой из п Ч оставшихся. И, наконец, на место Ч любой из п Ч k + оставшихся предметов. По правилу прямого произведения по лучаем, что общее число размещений без повторений из л по равно Напомним, что = 1.

Задана. В хоккейном турнире участвуют 17 команд. Разыгры ваются золотые, серебряные и бронзовые медали. Сколькими способами могут быть распределены медали?

Решение. 17 команд претендуют на 3 места. Тогда тройку при зеров можно выбрать способами = 4080.

1.6. Сочетания 1.5. Перестановки При составлении размещений без повторений из п по k мы по лучали расстановки, отличающиеся друг от друга либо составом, либо порядком элементов. Но если брать расстановки, которые включают все п элементов, то они могут отличаться друг от друга лишь порядком входящих в них элементов. Такие расстановки называются перестановками из п элементов, а их число обознача ется Следовательно, число перестановок равно РД Перестановки я = элементов 1, п записывают и в Л матричной форме, где верхняя это рядковые номера п позиций элементов в перестановке;

нижняя строка Ч же набор чисел 1, я, взятых в каком-ли бо порядке;

Ч номер элемента месте перестановки. По рядок столбцов в перестановках, записанных в матричной не является существенным, так как в этом случае номер позиции каждого элемента в перестановке указывается явно в верхней строке. Например, перестановка (3,2,4,1) из четырех элементов может быть записана как Задача Сколькими способами можно расположить на шахматной доске 8 ладей, чтобы они не били друг друга?

Решение. Условие не могли бить означает, что на каждой го ризонтали и вертикали может стоять лишь одна ладья. Ввиду это го, каждому расположению ладей на доске соответствует переста ( 1 2 новка я. Верхняя строка перестановки Ч это но мера горизонталей, нижняя Ч вертикалей, пересечение которых определяет положение ладей на доске. Следовательно, число рас становок равно числу перестановок 8! из 8 элементов.

1.6. Сочетания В тех случаях, когда нас не интересует порядок элементов в а интересует лишь ее состав, то говорят о сочетани ях. Сочетаниями из п различных элементов по k называют все возможные расстановки длины k, образованные из этих элемен тов и отличающиеся друг от друга составом, но не порядком эле 12 Глава Комбинаторные схемы ментов. Общее число сочетаний обозначают через или [ Определим это число. Составим все сочетания из п по k. Затем пе реставим в каждом сочетании элементы всеми возможными спо собами. Теперь мы получили расстановки, отличающиеся либо составом, либо порядком, т.е. это все размещения без повторений из п по k. Их число равно Учитывая, что каждое сочетание дает размещений, то по правилу произведения можно записать Тогда С* или С*, и п 1 2 Задача о прямоугольниках. Сколько различных прямоугольников можно вырезать из клеток доски, размер кото рой т х л?

Решение. Прямоугольник однознач- т но определяется положением его сто рон. Горизонтальные стороны могут за нимать любое из т + 1 положения. Тогда число способов их выбо ра равно Вертикальные стороны можно выбрать спосо бами. По правилу прямого произведения заключаем, что количество прямоугольников равно 1.7. Сочетания с повторениями Имеются предметы п различных видов. Число элементов каж дого вида неограниченно. Сколько существует расстановок дли ны k, если не принимать во внимание порядок элементов? Такие расстановки называют сочетаниями с повторениями, количество и обозначение которых следующее = Выведем данную формулу.

Пусть а, исходные различные типы элементов, количество которых п. Рассмотрим произвольное сочетание с по вторениями из данных типов элементов. Так как порядок элементов в сочетаниях не учитывается, то расста новку можно записать и так: \ bb...b \ \ dd...d, где элементы каждого из типов упорядочены и завершаются вертика Сочетания с повторениями льной чертой, за исключением последней серии элементов. Дли на такой расстановки с учетом вертикальных линий составляет k + = + kЧ 1, где k Ч количество элементов в расстанов ке;

п Ч 1 Ч число вертикальных линий. Очевидно, что любую та кую расстановку можно задать выбором из п + k Ч 1 места п Ч место для положений вертикальных линий. Это можно сделать способами. Промежуточные места между линиями запол няются соответствующими типами элементов.

Задача. Трое ребят собрали в саду 63 яблока. Сколькими спо собами они могут их разделить между собой?

Решение. Поставим в соответствие каждому делению яблок между ребятами сочетание с повторениями следующим спосо бом. Типами элементов в нашем случае будут ребята. Таким обра зом, имеем три типа элементов = из которых предстоит составить все различные расстановки длины k = 63. Наличие в расстановке какого-либо из элементов а, Ъ, с отвечает принад лежности данного яблока соответствующему мальчику. Порядок элементов в такой расстановке не играет роли. При делении яб лок между ребятами не важно, какое из них попадет тому или иному число способов разделить яблоки между ребятами равно = =2080.

Задача. Найти количество целочисленных решений системы +... = k, 0, 1, п;

п Решение. Рассмотрим следующую интерпретацию решения уравнения. Каждое значение... + представим как сумму единиц, количество которых Индекс у отмечает ее принадлежность к разложению числа Таким образом, мы вве ли п типов различных элементов значение каждого из них равно единице. Теперь любое решение исходного уравне ния можно представить как сумму, составленную из k произволь ных единиц множества Суммируя подобные едини цы с одинаковыми индексами, можно составить соответствую щие слагаемые решения исходного уравнения. Данное соответ ствие является взаимно однозначным, откуда и следует, что число решений системы равно числу сочетаний с повторениями Глава Комбинаторные схемы 1.8. Перестановки с повторениями, мультимножества Задача формулируется следующим образом. Имеются предме ты k различных видов. Сколько существует перестановок из элементов первого типа, элементов второго типа и т. д., эле ментов типа? Рассмотрим, например, мультимножество а, а, Ь, с, d, в котором содержатся 3 элемента а, 2 эле мента Ь, 1 элемент с и 4 элемента d. Мультимножество Ч это то же самое, что и множество, но в нем могут содержаться одинаковые элементы. Повторения элементов можно указать и другим спосо бом: М = - а, 2 Х 1 Х с, 4 Х Таким образом, искомые перестановки с повторениями Ч это перестановки элементов мультимножест ва. Если бы мы рассматривали все элементы множества М как различные, обозначив их то полу чили бы 10! перестановок, но после отбрасывания индексов мно гие из них оказались бы одинаковыми. Фактически каждая пере становка множества М встретилась бы ровно поско льку в любой перестановке М индексы при буквах а можно рас ставить 3! способами, при Ч 2! способами, при с Ч одним способом, а при d Ч соответственно 4! способами. Поэтому число перестановок множества М равно. В применении к обще му случаю те же рассуждения показывают, что число перестано вок любого мультимножества (перестановки с повторениями) равно полиномиальному коэффициенту где = + +... + Ч общее число элементов.

Перестановки с повторениями имеют тесную связь с сочета ниями. Определим количество этих перестановок следующим об разом. Из всех п мест перестановки место занимают элементы первого типа. Выбор мест для них можно сделать способами.

Из оставшихся п Ч мест элементы второго типа занимают места, которые можно выбрать способами. Те же рассужде ния показывают, что элементы типа можно расположить в перестановке способами. Согласно правилу прямо Упорядоченные разбиения множества го произведения, число перестановок с повторениями равно Задача. Сколько существует различных перестановок из букв слова Уссури?

Решение.

1.9. Упорядоченные разбиения множества Подсчитаем число разбиений конечного множества S, где | S \ = п, на k различных подмножеств = и... и попарно не пере k = 1, k и. Последовательность последо вательность подмножеств. При формировании упорядоченной последовательности на первое место подмножество мож но выбрать способами, на второе место подмножество можно выбрать из оставшихся п Ч элементов способами и т. на последнее место множество можно выбрать из оставшихся п - - -...- элементов _ способами. По правилу прямого произведения получаем, что общее число упорядоченных разбиений множества S на k подмножеств равно Ч л и f и что совпадает с числом перестановок с повторениями.

Замечание 1. Установим взаимно однозначное соответствие между упорядоченными разбиениями множества и перестанов ками с повторениями. Каждой перестановке с повторениями можно поставить в соответствие упорядоченное разбиение мно жества номеров элементов в перестановке на под множества где Ч множество номеров элементов типа в перестановке. Очевидно, что данное соответствие между перестановками с повторениями и разбиениями является взаимно однозначным.

Глава Комбинаторные схемы Замечание 2. Упорядоченные разбиения множества S на по парно непересекающиеся подмножества и... и = до пускают интерпретацию в терминах корзин и шаров. Обозна чим элементы исходного множества | S \ = шарами. Под разби ением исходного множества, теперь множества шаров, на различ ные упорядоченные подмножества будем понимать разложение шаров по различным корзинам (упорядоченные шаров положить в корзину шаров положить в корзину и т. шаров положить в корзину где + +... + = п. Как установлено, число таких разложений равно Задача. В студенческой группе, состоящей из 25 человек, при выборе старосты за выдвинутую кандидатуру проголосовали человек, против Ч 3, воздержались Ч 3. Сколькими способами может быть проведено такое голосование?

Решение. Имеем три различные корзины: за, против, воз держались, в которые необходимо разложить 25 шаров, соответ ственно 19 Ч в первую, 3 Ч во вторую, 3 Ч в третью. Количество таких разложений определяется выражением Х 1.10. Неупорядоченные разбиения множества Подсчитаем, сколькими способами можно разбить множество S, где | S | = п, на подмножества, среди которых для каждого 1, п имеется О подмножеств с элементами. Тогда верно, п что Данное разбиение позволяет представить исход ное множество следующим образом:

7=1 7=1 i=lj=l где не пересекаются и = = | \ = дого /' = п. Порядок подмножеств в разбиении не является существенным. Так, например, разбиения множества 2, 3, 4, 5} вида 1.10. Неупорядоченные разбиения множества считаются одинаковыми.

Обозначим число неупорядоченных разбиений множества S через Рассмотрим схему формирования упорядо ченных разбиений для представления п _ л!

Воспользуемся интерпретацией формирования упорядочен ных разбиений как разложения различных шаров по различным + +... корзинам так, что в каждую из корзину кладут шаров. Теперь откажемся от упорядоченности подмножеств в разбиении. Пусть все корзины имеют различное число шаров, та кие корзины можно рассматривать как различные (они отлича ются числом шаров). В этом случае упорядоченные и неупорядо ченные разложения шаров совпадают. Пусть теперь в разложении существуют корзин с одинаковым количеством шаров. При упорядоченном разложении такие корзины рассматриваются как различные. Однако при неупорядоченном разложении обмен ша рами таких корзин можно рассматривать как соответствующую перестановку указанных корзин, что не приводит к новым разло жениям. Если количество корзин с одинаковым числом шаров равно то неупорядоченных разложений будет в меньше, чем упорядоченных. Тогда общее число неупорядоченных разби ений будет в раз меньше, чем упорядоченных. Следо вательно, ' Заметим еще раз, что если выполнено разбиение числа п на подмножества различной длины (мощности), то они сов падают с неупорядоченными разбиениями. В этом случае все _ Глава Комбинаторные схемы Задача. Сколькими способами из группы в 17 человек можно сформировать 6 коалиций по 2 человека и 1 коалицию из 5 чело век?

Решение. Требуется разбить из 17 человек на непере секающиеся и неупорядоченные группы людей. Откуда искомое число равно 6 )=.

Задача. Сколькими способами можно разделить колоду из карт пополам так, чтобы в каждой пачке было по два туза?

Решение. 4 туза можно разбить на = 3 различные коалиции по две карты в каждой (неупорядоченные разбиения), т.е. только способами можно разделить тузы пополам. Далее, каждая полови на любого из этих трех разбиений тузов выполняет роль различных двух куда необходимо разложить пополам оставшиеся карты. Разложение 32 оставшихся карт уже будет упорядоченным, так как корзины различные, число разложений равно Со 16! 16!

гласно правилу прямого произведения, общее число вариантов колоду пополам.

Полиномиальная формула Формула.....

Х называется полиномиальной, где суммирование выполняется по всем решениям уравнения + + + = в целых неотрицате льных числах, я, 0, = k. Для доказательства выполним умножение + Чтобы привести подобные в полученном выражении, необхо димо подсчитать количество одночленов вида 1 К го разбиения + +... + = Для получения же одночлена необходимо выбрать в качестве множителя в 1.12. Бином Ньютона _ _ скобках при раскрытии выражения + +... + Это можно сделать способами. Из оставшихся Ч не раскрытых ско бок необходимо выбрать в качестве множителя в скобках.

Это можно сделать способами и т. д. Тогда количество од ночленов при раскрытии выражения будет числу ченных разбиений.

1.12. Бином Ньютона Частный вид полиномиальной формулы = (1.12.1) называется биномом Ньютона.

Рассмотрим несколько задач, в основе решения которых ле жит бином Ньютона.

п Задача 1. Доказать тождество Решение. Воспользуемся формулой (1.12.1) бинома в которой положим а = 1 и Ъ = 1, тогда (1+1)" п Задача 2. Доказать тождество Решение. Воспользуемся формулой (1.12.1), где положим а = и = т Ч 1.

Задача 3. Доказать тождество = Х Решение. Воспользуемся формулой в которой положим = тогда = С* =0. Группируя и отрицательные члены равенства, установим 20 Глава Комбинаторные схемы Так как =2, то дая из сумм составляет половину числа 2".

Задача 4. Доказать Решение. Воспользуемся формулой из которой, пола гая а = 1 и Ъ = получим + = Дифференцирование последнего равенства дает Пусть 1, тогда = что доказывает искомое тождество.

1.13. Инверсии Перестановки особенно важны при изучении алгоритмов сор так как они служат для представления неупорядоченных исходных данных. Чтобы исследовать эффективность различных методов сортировки, нужно уметь подсчитывать число переста новок, которые вынуждают повторять некоторый шаг алгоритма определенное число раз.

Пусть Ч перестановка элементов множества Если а > то пара называется инверсией перестановки. Например, перестановка 3142 имеет три инверсии (3, 1), (3, 2), (4, 2). Каждая инверсия Ч это пара элементов, нару шающих следовательно, единственная перестановка, не содержащая инверсий, Ч это отсортированная перестановка (1, л).

Таблицей инверсии перестановки называется по следовательность где Ч число элементов, расположенных левее/ Другими словами, dj Ч число инверсий, у которых второй элемент равен/ таблица инверсий пе рестановки 591826473 будет поскольку 5 и расположены левее 1;

5, 9, 8 Ч левее 2 и т. д. Всего 20 инверсий.

По определению О п - 1,..., О 1, = 0.

1.14. Обратные перестановки М. Холл установил, таблица инверсий единственным обра зом определяет соответствующую перестановку. Из любой табли цы инверсий можно однозначно восстановить переста новку, которая порождает данную таблицу, путем последователь ного определения относительного расположения элементов п Ч (в этом порядке). Например, перестановку, соответст вующую таблице инверсий (2,3,6,4,0,2,2,1,0) = можно построить следующим образом: выпишем число 9;

так как = то 8 стоит правее Поскольку = то 7 стоит правее 8 и 9. как = 2, то 6 стоит правее уже выписанных чисел;

та ким образом, получили расположение 9,8,6,7. Припишем теперь 5 слева, потому что = 0;

помещаем 4 вслед за четырьмя из уже записанных чисел, 3 Ч после шести выписанных чисел (т. е. в правый конец) и получаем 5,9,8,6,4,7,3. Вставив аналогичным образом 2 и 1, придем к перестановке (5,9,1,8,2,6,4,7,3).

Такое соответствие между перестановками и таблицами ин версий важно, потому что часто можно заменить задачу, сформу лированную в терминах перестановок, эквивалентной ей задачей, сформулированной в терминах таблиц инверсий. Рассмотрим, например, еще раз вопрос: сколько существует перестановок множества Ответ должен быть равен числу всевозмож ных таблиц инверсий, а их легко пересчитать, так как можно выбрать п различными способами, можно независимо от вы брать п - способами и т.д., Ч одним способом. Тогда различ ных таблиц инверсий п(п Ч = Таблицы инверсий пере считать легко, потому что все dj в то время как менты перестановки должны все быть различными.

1.14. Обратные перестановки Не следует путать линверсии перестановок с обратными пе рестановками. Пусть Ч различные шары, индексы которых свяжем с номерами шаров. Тогда исходное расположе ние шаров однозначно определяется тождественной переста е = (1, и). п = Ч произвольная пе рестановка номеров 1, л, где Ч номер шара на fc-м месте.

Такая перестановка отвечает расположению шаров. Вспомним (см. что перестановка 2 ХХХ п Данная ХХХ 22 Глава 1. Комбинаторные схемы форма записи позволяет рассматривать перестановку в качест ве оператора, который заменяет старые номера шаров Ч верх няя строка матрицы Ч на новые номера Ч нижняя строка мат рицы. Тогда результат двух последовательных изменений л = и ст = ст2,..., стД) исходной последовательно сти п номеров шаров можно рассматривать как операцию умножения перестановок р =... п Упорядочим столбцы перестановки а в соответствии с 2 ХХХ п новкой л = т.е. ст=!

1 9 п Тогда можно записать, р ст 2 л у Этой перестановке отвечает ХХ расположение шаров значение Ч это номер шара на месте.

( 1 Обратной к перестановке я называется пере = которая 1 2......

ся, если в исходной перестановке поменять местами строки, а за тем упорядочить столбцы в возрастающем порядке по верхним элементам, т.е. Ясно, что последовательное изменение порядка шаров согласно перестановкам л = и обратной приводит к исходному их рас положению, т.е. к тождественной перестановке 2 '.'.'.

перестановке (5,9,1,8,2,6,4,7,3) будет перестановка (3,5,9,7, таккя^Г т, 2 3 4 5 6 7 8 5 9 7 1 6 8 Сортированную последовательность элементов перестановки л = (я1, можно получить, заполнив в цикле вектор far k =l to do или = Обратные перестановки Ясно, что результирующие значения будут соответ ственно В цикле каждый элемент встает на свое упоря доченное место (см. Подобным образом выполним за полнение элементов перестановки однако в упорядоченное место элемента будем размещать его номер в исходной перестановке я = for n do k или Результирующий вектор будет обратной перестановкой к я = X. А. Роте впервые установил связь между обратными переста новками и инверсиями: обратная перестановка содержит ровно столько же инверсий, сколько исходная.

Представление абстрактных объектов ассматривая решение задачи с абстрактной точки зрения, как правило, избегают каких бы то ни было предположений отно сительно того, как мы намерены автоматизировать ее решение.

В идеале структура вычислительной машины должна соответ ствовать естественной структуре задачи, однако это требование часто не выполняется, хотя приспособляемость современной вы числительной техники такова, что она позволяет обойти эти огра ничения без труда. Языки высокого уровня при условии, что они должным образом сконструированы, предоставляют в распоря жение программиста, реализующего алгоритм, более удобную машину, смягчая несоответствие основной машины требова ниям алгоритма. Будем считать, что читатель знаком с элементар ными понятиями математики и основными типами данных: це лыми и вещественными числами, массивами, строками и т. д.

Представление последовательностей Любой заданный класс абстрактных объектов может иметь не сколько возможных представлений, и выбор наилучшего из них решающим образом зависит от того, каким образом объект будет использован, а также от типа производимых над ним операций.

Смежное представление В алгоритмах на дискретных структурах часто приходится встре чаться с представлением конечных последовательностей и операци ями с ними. С вычислительной точки зрения простейшим пред ставлением конечной последовательности..., является точ ный список ее членов, расположенных по порядку в смежных ячей ках памяти. В языках высокого уровня Ч это одномерные, двухмерные и т. д. массивы данных. Наряду с очевидными преиму ществами последовательное представление имеет и некоторые зна чительные недостатки. Смежное представление становится 2.1. Представление последовательностей если требуется изменить последовательность путем включе ния новых и исключения имеющихся там элементов. Включение между и нового элемента требует сдвига на одну позицию;

аналогично исключение сдвига же эле ментов на одну позицию влево, как показано в алгоритме Алгоритм 2.1. Включение и исключение элементов при размещении элемент z на i-e место } п = п + 1;

- п Ч 1 to i by Ч 1 do = Sj, = z.

элемент с i-го места } forj i to n Ч do Sj = n = n Ч 1.

В обоих случаях включение или удаление элементов при смеж ном представлении требует перемещения многих элементов. С точки зрения времени обработки такое перемещение элементов может оказаться дорогостоящим из-за сложности операций включения и удаления 0(п).

2.1.2. Характеристические векторы Важной разновидностью смежного размещения является слу чай, когда такому представлению подвергается подпоследовате льность некоторой основной последовательности В этом подпоследовательность можно предста вить более удобно, используя характеристический вектор Ч по следовательность из нулей и единиц, где разряд равен едини це, если принадлежит рассматриваемой подпоследовательно сти.

Например, для последовательности (1,2,3,4,5,6,7,8,9) характе ристический вектор подпоследовательности чисел, кратных 3, имеет вид (0,0,1,0,0,1,0,0,1).

Характеристические векторы полезны в том случае, когда формирование нужной подпоследовательности выполняется пу тем последовательного удаления из основной последовательно сти элементов, которые не входят в подпоследовательность. Глав ное неудобство характеристических векторов состоит в том, что они не экономичны.

Глава 2. Представление абстрактных объектов 2.1.3. Связанное размещение Неудобство включения и исключения элементов при смежном представлении происходит того, что порядок следования элементов задается неявно требованием, чтобы смежные элемен ты последовательности находились в смежных ячейках памяти. В результате многие элементы последовательности во время вклю чения или исключения должны передвигаться.

Если требование последовательного размещения элементов опущено, то операции включения и исключения можно выпол нить без того, чтобы передвигать элементы. При любом размеще нии элементов необходимо сохранять информацию о способе их упо рядочения. При связанном размещении последовательности каждому ставится в соответствие указатель /,, который указывает на следующую подобную пару элементов списку. Вводится начальный указатель который указывает на первый элемент последовательности. Последний указатель в списке является пустым или нулевым, это признак конца списка.

Графическое представление связанного списка можно изобра зить следующим образом:

Здесь каждый элемент связанного списка состоит из двух по лей. В поле DATA размещен сам элемент последовательности, а в поле NEXT Ч указатель на следующий за ним элемент. Связан ное представление последовательностей облегчает операции включения и удаления элементов из списка. Например, для иск лючения второго элемента достаточно переустановить указатели = Графически это изображается следующим образом:

до исключения после исключения Ч Чтобы в последовательность включить новый элемент после необходимо установить указатели: = и = начальное значение указателя установлено на но вый включаемый элемент. Графически включение нового эле мента изображается так:

2.1. Представление последовательностей включения Ч лосле включения Ч С помощью связанных распределений мы добились большей гибкости, но потеряли возможность работать с элементами по следовательности как с массивами, когда по номеру можно не посредственно обратиться элементу В связанном размеще нии такой возможности не существует, и доступ к элементам по следовательности не является прямым и эффективным. Напри мер, при поиске среднего элемента последовательности, даже при известной ее длине, требуется просмотреть по связанному списку половину последовательности. В алгоритмах 2.2 и 2.3 при водятся программы, реализованные на языках Pascal и С, связан ного формирования списка элементов последовательности. В программы включены операции работы со списком: печать эле ментов списка, включение новых элементов в список и удаление элементов из списка.

Существуют различные модификации представления после довательностей в виде связанных Следующие два при мера позволят, при желании, читателю самостоятельно продол жить получение и других модификаций связанных распределе ний, отличных от приводимых ниже.

Циклическая форма представления позволяет эффективно возвращаться с последнего элемента списка к первому.

Рис. 2.1. Циклический список Еще большая гибкость достигается, если использовать дважды связанный список, когда каждый элемент последовательности вместо одного имеет два связанных с ним указателя. В таком спи ске для любого элемента имеется мгновенный прямой доступ к предыдущему и последующему элементам. Следует помнить, что 28 Глава 2. Представление абстрактных объектов выбор того или иного представления последовательности в зна чительной степени зависит от типа выполняемых с элементами последовательности.

Рис. 2. Дважды связанный л список Алгоритм 2.2. Программа на 'е включения и исключения элементов из списка Program список uses type RECORD связанного s next на следующий END;

const first начала нового элемента function var newNode begin память новому нового новый элемент в начало procedure NodePointer begin из списка 2.1. Представление _ procedure Integer var :NodePointer;

i begin irst;

while do begin if i=k then begin { k-й элемент if then else из break;

end;

end;

procedure элементов var p :NodePointer;

begin while do begin Write end;

end;

Var begin из п for i:=l to n do WriteLn;

из списка PrintNodeList;

30 _ Глава 2. Представление абстрактных объектов Алгоритм 2.3. Программа на Си включения и исключения элементов из списка tinclude ttinclude typedef struct tagNode{ связанного списка int последовательности tagNode на следующий typedef Node Node начала списка NodePointer void нового списка NodePointer newNode;

newNode=new Node;

памяти элементу + 1;

нового списка return newNode;

} новый элемент в начало списка void NodePointer newNode } void int из списка //k-й элемент NodePointer int while ( i==k элемент найден first==current ) else списка delete current;

break;

2.2. Представление деревьев void void элементов // списка p=p->next;

void void int из п элементов for( ) элемент Связанное представление предпочтительнее лишь в том слу чае, если в значительной степени используются операции чения и исключения элементов.

2.2. Представление деревьев Конечное корневое дерево определяется как непу стое конечное множество упорядоченных узлов, таких, что суще ствует один выделенный узел, называемый корнем дерева, а оставшиеся узлы разбиты на т 0 поддеревьев Корневое дерево на рис. 2.3 содержит 9 узлов, помеченных буквами от а до л Узлы с метками e,f, с, g, r являются листьями, остальные узлы Ч внутренние. Узел с меткой а Ч корень. Поня тие дерева используется в различных аспектах. Деревья Ч наибо лее важные нелинейные объекты, используемые для представле ния данных в алгоритмах на дискретных структурах.

32 Глава 2. Представление абстрактных объектов Рис. 2.3. Корневое дерево с тремя поддеревьями Важной разновидность корневых деревьев являются бинарные деревья. Бинарное дерево пустое, либо состоит из выделен ного узла, называемого корнем, и двух бинарных поддеревьев: ле вого и правого Лесом называют упорядоченное множество деревьев. Тогда де рево можно определить как непустое множество узлов, такое, что существует один выделенный узел, называемый корнем дерева, а оставшиеся узлы образуют лес с поддеревьями корня.

Представление деревьев на связанной памяти Почти все машинные представления деревьев основаны на связанных распределениях. Каждый узел состоит из поля данных и некоторых полей для указателей. следующем примере пред ставления дерева каждый узел имеет по три поля указателей.

first Рис. 2.4. Регулярная связанная структура представления дерева Произвольное дерево с переменным числом поддеревьев все гда можно представить с помощью односторонних списков с ис пользованием звеньев, в которых в первом поле находится либо указатель, либо данные, а во втором Ч все гда указатель.

2.2. Представление деревьев first Рис. 2.5. Универсальная связанная структура представления дерева Применение указателей и связанных списков придает памяти гибкость, необходимую для представления различных структур.

Но при этом легко перестараться;

поэтому следует избегать слишком большого количества указателей;

сложность програм мной поддержки таких структур возрастает лэкспоненциально, теряется четкость основной структуры, которую пытаются пред ставить в памяти (последний пример представления дерева это наглядно подтверждает).

2.2.2. Представление деревьев на смежной памяти Представление деревьев на смежной памяти (одномерный массив) предполагает неявное присутствие ребер, переход по ко торым выполняется посредством арифметических операций над индексами элементов массива Ч смежной памяти. Формирова ние таких деревьев с помощью адресной арифметики можно осу ществлять двумя способами. Идея первого способа применима при любом постоянном количестве ребер, выходящих из вершин (регулярное дерево). Рассмотрим данный способ формирования на примере двоичного (бинарного) дерева.

Пусть имеется одномерный массив смежных элементов Неявная структура двоичного дерева определяется на рис. 2.6.

По дереву на рис. легко перемещаться в обоих направлениях.

Переход вниз на один уровень из вершины можно удвоив индекс k (индекс левого поддерева) или удвоив и прибавив (индекс правого поддерева). Переход вверх на один уровень из вер шины а[т] можно выполнить, разделив пополам и отбросив дробную часть. Рассмотренная структура применима к любому де реву с постоянным количеством ребер, выходящих из вершин.

2Ч 34 Глава 2. Представление абстрактных объектов a[2k] a[2k+l] a[m]... a[n] Рис. 2.6. дерево на смежной памяти с последовательной нумерацией вершин Другой способ, основанный на индексной арифметике, при меним только для двоичных деревьев. Пусть для представления де рева используется одномерный массив Корнем дере ва полагают элемент где индекс элемента корня рассчитыва ется по формуле т = т.е. середина массива. Левое под дерево располагается в массиве а правое поддерево Ч в массиве Корни поддеревьев рас считываются подобным же образом, как и корень основного де рева. Второй способ формирования двоичных деревьев на смеж ной памяти имеет довольно ограниченное применение. Основ ное его использование Ч поиск в сортированных таблицах и т.д.

В качестве примера использования представления регулярных деревьев на смежной памяти рассмотрим решение следующей за дачи.

Задача. Написать программу поиска всех а замкнутых маршрутов длины 15 по ребрам треугольника abc. Длину ребра принять рав ной 1. Начальная и конечная точка искомых маршрутов Ч вершина а. Длина маршрута п задается в текстовом файле исходных данных.

Результаты расчетов всех маршрутов сохранить в выходном тек стовом файле. Каждый маршрут представить как последователь ную комбинацию меток а,Ь,с посещаемых вершин треугольника при движении по нему. Каждый маршрут должен включать метку, где первой и последней меткой должна быть вершина а.

Пример файла исходных данных:

2.2. Представление деревьев Выходной файл для данного примера:

abcba ababa acaba abaca асаса acbca В алгоритме 2.4 представлена программа расчета всех искомых маршрутов длины я. Алгоритм делится на две части. В первой час ти (процедура выполняется формирование двоич ного регулярного дерева на смежной памяти рис. 2.7.

Алгоритм 2.4. Программа на поиска замкнутых маршрутов по треугольнику Program по треугольнику uses const память для type of Char;

var f z дерево движения по Procedure ) var begin первой вешины последней вешины while level<=n do for to do begin уровень case z[k] of begin end;

'b': begin end;

begin end;

end;

36 Глава 2. Представление абстрактных объектов end;

end;

Procedure begin for i:=l to n do первой вершины на последнем последней вершины на последнем for to m2 do от листьев к вершинам k:=i;

if then begin repeat k:=k div until end;

end;

Var n begin открыт для открыт для дерево сверху маршруты от листьев к end.

2.3. Представление множеств При проходе вниз вершины дерева заполняются метками а, с, соответствующими вершинам треугольника при перемещении по нему. Два ребра, выходящих из каждой вершины, показывают возможные варианты выбора дальнейшего маршрута продвиже ния по треугольнику. В каждом случае из вершин а, с можно попасть в любые две другие вершины. Индексы меток дерева про хода на рис. показывают соответствующее их место в массиве данных (смежной памяти).

с[4] а[5] а[6] а[8] b[9] b[10] c[ll] b[121 с[13] с[14] а[15] Л Л Л /\ /\ Л /\ с[17] с[20] а[21] а[22] с[24] а[25] а[26] b[27] a[28] b[29] b[30] с[31] Рис. 2.7. Двоичное дерево маршрутов по треугольнику на смежной памяти Во второй части алгоритма выполняется формирование иско мых маршрутов (процедура RouteTreeAbc), основой для построе ния которых служит дерево прохода на рис. 2.7. Для формирова ния всех маршрутов теперь достаточно подняться по нему от ли стьев с метками а вершины треугольника к корню, запоминая пройденные метки. Ясно, что число маршрутов будет равно числу вершин на последнем уровне (количество листьев) с меткой а.

2.3. Представление множеств Существуют два основных подхода к представлению множеств в памяти.

1. При первом подходе хранят описание каждого элемента, действительно присутствующего в множестве, как это дела ется, когда выписываются все элементы множества и заклю чаются в фигурные скобки.

2. При втором подходе изначально определяются все потенци ально возможные элементы множества, а затем для любого подмножества этого универсального множества для каждо го возможного члена указывается, принадлежит ли он на са мом деле данному подмножеству или нет.

Глава 2. Представление абстрактных объектов При первом подходе представления множеств используют как смежное, так и связанное размещение его элементов в памяти (рис. 2.8). Данные методы размещения подробно рассмотрены в п. 2.1 представления последовательностей.

с а Ъ X у г X # Рис. 2.8. Смежное и связанное представление множества в памяти Как и для последовательностей, наилучший метод представления множеств существенно зависит от операций, которые мы собира емся выполнять над ними. Типичные операции над множествами:

выяснить, имеется ли конкретный элемент в данном множестве;

добавить в множество новые элементы;

удалить элементы из мно жества;

выполнить обычные такие как объединение или пересечение двух множеств. Как прави ло, для представления множеств применяют связанную память.

При втором методе множество представляется в виде вектора на смежной памяти. Пусть U Ч универсальное множество (т. е.

все рассматриваемые множества являются его подмножествами), состоящее из п элементов. Любое подмножество ляется в виде характеристического вектора из элементов. Эле мент в этом векторе равен 1 тогда и только тогда, когда эле мент множества U принадлежит S, в противном случае он уста навливается равным 0 (рис. 2.9).

Представление в виде характеристического вектора удобнее тем, что можно определять принадлежность элемента множеству за время, не зависящее от его размера. Основные операции над мно жествами, такие как объединение и пересечение, можно осуществ лять как операции v над двоичными векторами. Недостаток это го представления заключается в том, что операции объединение и пересечение занимают время, пропорциональное мощности уни версального множества U, а не рассматриваемого множества S. Дан ное представление требует дополнительной памяти для хранения характеристического вектора, что для больших (размер универса льного множества бывает практически невыполнимо.

1 1 1 1 0 0 1 0 0 1 1 0 0 0 1 0 1 1 1 0 Рис. 2.9. Представление множества характеристическим вектором Методы подсчета и оценивания в предыдущих разделах комбинаторные формулы подсчета означают вычисление или определение свойств некоторой последовательности чисел, соответствующие той или иной задаче. В этом разделе предлагается полезный инст румент для работы с последовательностями. Идея состоит в чтобы каждой числовой последовательности сопоставить функ цию действительного или комплексного с тем, что обычные операции над последовательностями соответствовали простым операциям над соответствующими функциями. Аналитические методы работы с функциями оказы ваются проще и эффективнее, чем непосредственные комбина торные методы работы с последовательностями.

Производящие функции Пусть Ч произвольная последовательность. Сопо ставим последовательности функцию действительного или ком плексного переменного:

(3.1.1) Функция А(х) называется производящей функцией последовате льности Как правило, А(х) по форму ле прямыми методами является сложной задачей. Однако заметим, что последовательность может быть восстановлена по Выражение является в ряд Тей лора в окрестности точки = 0. Воспользуемся этим замечанием и приведем некоторые наиболее распространенные производя щие функции и соответствующие им последовательности.

40 Глава 3. Методы подсчета и оценивания Последовательности Производящие функции + (3.1.3) ~ о Я V ' * ' = Ч любое (3.1.6) -I = (3.1.7) = i любое (3.1.8) k любое (3.1.9) Задача. Найти число граней в кубе.

Решение. Обозначим через число граней в ном кубе, 0 k п. Тогда производящую функцию тельности можно записать как =. Индекс п для показывает размерность куба. Например, = 1, = 2 + х, = 4 + + Рассмотрим производящую функ цию последовательности для (п +1)-мерного куба. За метим, что (и куб можно получить из куба сдвигом последнего по (я +1)-му измерению. На рисунке показан пример получения трехмерного куба сдвигом по тре тьему измерению квадрата (двухмерного куба). От сюда видно, что (я куб включает два ста рых куба и каждая грань при сдвиге переходит в (k +1)-мерную грань. Из рассуж дений следует, что = + х Х где = 1.

Отсюда Производящие функции Воспользуемся разложением бинома Ньютона:

4= Сравнивая коэффициенты при степенях получим, что число граней в кубе равно = Например, = 8 + + Простейшие производящие функции будем ис пользовать как строительные кирпичики для получения произ водящих функций более сложных последовательностей. С этой целью рассмотрим наиболее важные из операций над производя щими функциями, т.е. способы получения новых производящих функций и соответствующих им последовательностей. Обозна чим через последовательности, а соответствующие им производящие функции Ч как С(х).

Линейные операции Если константы, то последовательность = a Х + p Х имеет производящую функцию = Х + (3 Х Например, последовательность соответствует производя щей функции, а последовательность \ Ч соответствует про 1-х изводящей функции тогда последовательность \ + Ч соот ветствует производящей функции.

3.1.2. Сдвиг начала вправо Пусть последовательность определяется через последова тельность следующим образом:

для k = 0, - 1 и = k = i, i + тогда В(х) = Действительно k=i 42 Методы подсчета и оценивания 3.1.3. Сдвиг начала влево Пусть последовательность определяется через последова тельность следующим образом: = k = тогда Действительно 3.1.4. Частичные суммы Пусть последовательность определяется через последова тельность следующим образом:

тогда Действительно Множество пар точек (k, по которым ведется суммирование, представлено на рисунке. Изме ним порядок суммирования (сначала по затем по k). Выражение для примет вид 3.1.5. Дополнительные частичные суммы Пусть последовательность определяется через последова тельность следующим образом:

0.

i=k 3.1. Производящие функции Действительно ) Множество пар точек (k, по которым ведется з суммирование, представлено на рисунке. Из- меним порядок суммирования (сначала по 1 2 3 4 k затем по К). Выражение для примет вид О Л О (= 3.1.6. Изменение масштаба 1. Пусть последовательность определяется через последо вательность следующим образом:

тогда = х Х Действительно и или 2. Пусть последовательность определяется через последо вательность следующим образом:

тогда Поскольку, то о 44 Глава 3. Методы подсчета и оценивания 3.1.7. Свертка Последовательность = ОД = 00 Действительно, = и = тогда ) СО 00 Далее обсудим наиболее общие приемы использования произ водящих функций на примере решения следующих задач.

Задача. Рассмотрим обобщенное биномиальное правило рас крытия выражений.

* где обобщенный биномиальный коэффициент ' V Тогда Рассмотрим полученное выражение при = 3.1. Производящие функции fci _ л 1 2* * fc.

Таким образом, Рассмотрим при 1.

где Следовательно, = Задача. Сколькими способами можно разбить выпуклый + 0) на треугольники диагоналями, не пересе кающимися внутри многоугольника?

Решение. Пусть Ч искомое число способов разбить (п + на треугольники. Перенумеруем вершины ис ходного многоугольника числами от 1 до л + 3. Заметим, что при любом разбиении найдется треугольник, содержащий ребро мно гоугольника с вершинами п + 2 и я + 3. Третья вершина этого тре угольника может быть любой из остальных Пусть это будет вершина k. Если удалить треугольник с вершинами п + 2, п + 3, k, то получим два многоугольника с числом вершин k + 1 и 46 _ Глава 3. Методы подсчета и оценивания п + 3 Ч k, которые можно разбить на треугольники и способами. Суммируя по k = 1, п + 1, получим (согласно пра вилам прямого произведения и суммы) искомое число разбиений исходного (я + на треугольники:

= л2 + + л4 + - + где п 0 и положили = 1.

Получили нелинейное рекуррентное соотношение для после довательности п О, для поиска которой удобно ввести но вую последовательность п 0, такую, что = Тогда рекуррентное соотношение перепишется в виде = Х + +... + ИЛИ Заметим, что правая часть является сверткой двух одинаковых последовательностей и (см. операцийс производя щими Ввиду этого, составим производящую функ цию правой части Пусть Ч производящая функция последовательности п 0, тогда последнее соотношение запишем как или х Х - = 0.

Ранее рассмотренное разложение обобщенного бинома Л -1 Л k запишем для случая 3.1. Производящие функции _ Поскольку результат V(x) должен быть рядом по то решение + по сторонним. Окончательно Отсюда я 0.

Ответ: число способов разбить выпуклый (л + на треугольники непересекающимися диагоналями равно, Задача. Найти = Определим четыре последовательности и их производящие функции:

= = = и А(х), Для решения задачи необходимо найти С этой целью опреде лим что позволит нам установить значения =. Последовательности и связаны лизменением значит = х Х Последовательности и так же связаны лизменением масштаба, следовательно, С(х) Последовательности и связаны частичной тогда Окончательно =.

Для получения коэффициентов воспользуемся разложением (3.1.9):

48 Глава 3. Методы подсчета и оценивания Теперь можно записать, что Сравнивая коэффициенты при одинаковых получим Таким образом, = Ч k.

Задача. Показать, что или СО Заметим, что - является производящей функцией последовательности Следовательно, иско k. k мая сумма равна k свя А(х) частичной суммой, то = Разложение (3.1.9) позволяет записать последнее выражение в следующем виде:

-Х) Задача. Пусть 7Ч целочисленные случайные величины и определены их ряды распределений. Характеристической функ цией распределения случайной величины X называется функция 3.2. Линейные рекуррентные соотношения Таким Ч это производящая функция последовате льности чисел Р(Х= k), где k= О,. Будем полагать случайными величинами Рассмотрим Y. Очевидно, что P(Z P(X + = i)P(Y =k Ввиду свойства свертки для производящих функций характери стическая функция с.в. Z может быть записана таким образом:

3.2. Линейные рекуррентные соотношения Рассмотрим последовательность = О, 1,. Будем го ворить, что задано однородное линейное рекуррентное соотно шение с постоянными коэффициентами порядка если для чле нов последовательности выполняется равенство где Ч постоянные величины. Выражение позво ляет вычислить очередной член последовательности по предыду щим Ясно, что, задав начальные значения можно последовательно определить все члены последовательно сти. Мы рассмотрим общий метод решения (т.е. поиска как функции от п) рекуррентного соотношения (3.2.1).

Для решения задачи достаточно найти производящую функ цию ВД = последовательности Введем обозначение для полинома = 1 Ч Ч Ч... Ч и рассмотрим произведение = Непосредственным умножением можно убедиться, что Ч это полином, степень которого не превышает Ч так как коэф фициенты при (п = О, в согласно уравнению (3.2.1), равны + +... + = 0.

50 _ Глава 3. Методы подсчета и оценивания Характеристическим полиномом соотношения назы вается (3.2.3) Выполним разложение на линейные множители ВД=(* где + +... + Сравнивая К(х) и запишем - Отсюда Данное разложение на множители используем для представле ния в виде суммы простых дробей:

Х Таким образом, является суммой функций вида Тогда выражение (3.2.4) примет вид С(х) Данное разложение является производящей функцией = последовательности Для определения необ ходимо найти коэффициент при в разложении (3.2.5).

Задача. Найти члены последовательности удовлетворяю щие рекуррентному соотношению = Ч = = 1.

Решение. К(х) = 1 - 5х + = С(х).

3.3. Неоднородные линейные рекуррентные соотношения _ Выполним данное умножение: (1 Ч 5х + + + +...) = = + Ч + Ч + +... = HO + = 1 Ч 4х.

Таким образом, С(х) = 1 Ч 4х.

Характеристический полином = 5х + 6 = (х Ч 2)(х Ч 3).

Отсюда. вели (1-2х)(1-Зх) 1-2х чин А В находим методом неопределенных коэффициентов:

А 2, = Наконец, принимая во внимание С другой стороны,. Поэтому, сравнивая коэффи при одинаковых степенях заключаем, что = 3.3. Неоднородные линейные рекуррентные соотношения Неоднородное линейное рекуррентное соотношение имеет вид (3.3.1) где величина в общем случае является функцией от п. Общее решение соотношения представляет собой сумму частного решения неоднородного уравнения (3.3.1) (т.е. любого решения, которое ему удовлетворяет) и общего решения соответствующего ему однородного соотношения (3.2.1), которое находится рас смотренным способом. Общих способов определения частного решения нет, однако для специальных значений Ъ существуют стандартные приемы определения Рассмотрим на примере в некотором роде универсальную процедуру, которая позволяет сразу находить общее решение неоднородного уравнения Задача. Найти если известно, что = + + 1) и Умножив левую и правую части рекуррентного соотношения на получим 52 Глава Методы подсчета и оценивания Суммирование последнего уравнения для всех п дает Свойства операций с производящими функциями позволяют данное выражение привести к виду Учитывая, что = 1, запишем Сравнивая коэффициенты при V, заключаем, что Задача. Найти число замкнутых маршру тов длины п по ребрам треугольника ABC.

Длину ребра принять равной единице. Нача льная и конечная точка маршрутов Ч верши на А.

Решение. Введем обозначения: Ч число замкнутых маршру тов длины п из вершины А в вершину А;

Ч число маршрутов длины л из А в вершину Ч число маршрутов длины п из вершины А в вершину С.

Очевидно, что из условия симметрии задачи = Величины же связаны системой рекуррентных соотношений:

= С учетом последнего равенства = = О, 1, система при водится к виду 3.4. Обобщенное правило произведения Выражая из первого уравнения и подставляя во второе, полу чим однородное рекуррентное соотношение относительно по следовательности Запишем его в принятых обозначениях, полагая = = + = О, где = О, 1,.

Решение данного соотношения получим согласно изложенной выше теории.

= = С(х) = Характеристический полином - х - 2 = (х - + 1).

Отсюда + \-2х + Перепишем в развернутом виде по степеням У:

00 00 1 вд=+2"*"+]г;

(-1)''*"=2г Сравнивая коэффициенты при заключаем, что число 2" маршрутов длины п равно 3.4. Обобщенное правило произведения Пусть Ч произвольные множества.

= множество весов, где под будем понимать любой из символов 1, х, у, z, и их произведения. В от личие от элементов, вес Ч это число либо переменная, которая может принимать любые числовые значения. Назначим каждому вес Во многих задачах требу ется определить количество элементов с определенными свойст вами, а не их вес. В этом случае полагают = Пусть Ч количество элементов множества с весом тог да = Ч сумма весов элементов множества Рассмотрим прямое произведение множеств S = 54 Глава 3. Методы подсчета и оценивания Положим вес элемента множества равным Пусть Ч количество элементов е S с весом тогда A(S) = Ч сумма весов элементов множества.

Теорема. = Доказательство.

Задача. Найти количество замкну А тых маршрутов длины 2л по ребрам Л трехмерного куба. Начальное и конеч А ное положение Ч вершина куба.

Решение. Исходное положение Ч вершина Каждый шаг движения по кубу Ч это выбор одного из трех ребер. Пусть 1 обозначает выбор ребра вдоль оси ОХ, 2 Ч вдоль оси 3 Ч вдоль оси OZ.

В соответствии с этим введем множества такие, что... = = 2, Тогда все маршруты длины соста вят множество x x... х Например, маршрут означает, что из пошли в затем в вернулись в и подня лись в Назначим веса элементам множества:

= z. По правилу обобщенного произведения сумма весов всех маршрутов длины равна = = (x + у + т.к. = x + у + z После возведения в степень получим, что (3.4.1) 3.4. Обобщенное правило произведения где Ч вес включающего шагов вдоль оси OX, j Ч вдоль k Ч вдоль OZ(i +j + k = 2л), Ч количество маршру тов с весом Заметим, что только маршрут, заканчивающийся в имеет вес с четными степенями i,j, k, т. к. в замкнутом маршруте, сде лав шаг вдоль оси, необходимо вернуться по этой оси. Для выде ления таких маршрутов положим х = = = 1 (х, у, Ч произво льные). Тогда выражение (3.4.1) примет вид (х + у + = + + + (3.4.2) где Ч число маршрутов, заканчивающихся в Ч Ч в Ч в Учитывая симметрию точек относительно можно за ключить, что = = = С. Тогда из системы (3.4.2) следует, что (3.4.3) Уравнение (3.4.3) содержит два неизвестных и С при = = z2 = Для их определения составим систему уравнений из выражения (3.4.3), полагая x y = = Это возможно, т.к. выполняется условие = = = Получим сис тему + Отсюда = -- число искомых маршрутов.

Задача. Найти число решений р, q уравнения 2р + 3q п, где р, q 1, Решение. Введем множества: = \р = = q = = О, 1, и x = \p,q = Назначим веса элементам данных множеств следующим образом:

и = = = Х = Веса элементов определены таким образом, что выполняется правило обобщенного произведения Легко за что степень веса любого элемента Е = (2р, дает одно из решений исходного уравнения 2р + 3q = п.

56 Глава 3. Методы подсчета и оценивания Раскроем выражение = HO + + + ХХХ + + ХХХ = =.........) = = (1 + где Ч число решений уравнения 2р + = п. Фактически, сум ма весов элементов множества S является производящей функцией числа решений уравнения 2р + = п. Таким образом, = -- у Разложим данное выражение на множители:

1-х 2 где Ч число решений уравнения 2р + = Сравнивая коэффициенты при одинаковых степенях, полу чим:

+ где я 1, 3.5. Принцип включения и исключения Пусть S = ~ произвольное множество элементов.

= весов, Ч вес элемента РД Ч свойства элементов или индикаторы свойств элементов.

3.5. Принцип включения и исключения ( _ обладает ' [О, если элемент не обладает свойством.

)= Х га(.у Ч сумма весов элементов со свойством fc ) Ч сумма весов элементов множества S, которые обладают каждым из свойств.

= суммирование выполняется по всем сочетаниям длины т из п свойств, количество сочетаний Таким образом, в суммируются веса только тех элемен тов, которые имеют как минимум т свойств. Пусть элемент s обла дает k свойствами тогда его вес в войдет раз.

Так, = = п членов и содержит + 1)/2 членов.

Распространим определение на т = 0, положив Ч сумма весов элементов исходного множества S.

определение выполнено корректно, так как сумма должна включать элементы, обладающие нуль свойствами и Действительно, любой из элементов множества воряет этим условиям.

Положим:

Ч сумма весов элементов, обладающих ровно т свойствами;

Ч сумма весов элементов, которые не имеют ни одного из указанных свойств.

Теорема. Сумма весов элементов, обладающих точно т свойст вами из п свойств равна или = (3.5.1) Доказательство. Для доказательства достаточно показать, что вклад веса произвольного элемента s e S в правую и левую 58 _ _ Глава 3. Методы подсчета и оценивания части (3.5.1) одинаковый. точно /свойствами.

Возможны следующие соотношения между / и т:

1) / < т, тогда не входит в и не входит в + для = О, Ч т. Равенство (3.5.1) примет вид 0 = 0.

2) / = т, тогда входит один раз в и один раз в 3) / > т, тогда (s) не входит в и левая часть равна 0. Пока жем, что в этом случае и правая часть выражения (3.5.1) равна нулю.

Вес со (s) в Щт + входит раз, т + i /. Правая часть для веса со (s) одного элемента s примет вид Заметим, что /!

да!/!

Следовательно, а исходная сумма составит t-m t-m 1= И в третьем случае выражение справедливо. Теорема дока зана.

Следствие.

= - + - +...

Задача. В группе 23 студента. Из них 18 знают английский язык, 9 немецкий и 6 Ч оба языка. Сколько студентов в группе не знают ни одного языка? Сколько студентов знают один язык?

Решение. Пусть множество всех студентов, \S \ = 23. Назна чим вес = 1 всем элементам s s S. Теперь под суммой весов будем понимать количество студентов.

Назначим свойства элементам s Ч знание английского языка, Ч знание немецкого языка.

ДО) Ч студенты, не знающие языков (не обладают 3.6. Ладейные многочлены и многочлены попаданий = - + = + = 18 + 9 = 27.

= 6.

Тогда = 23 - 27 + 6 = 2.

Е( 1) Ч студенты со знанием одного языка (обладают ровно одним свойством).

Задача. Найти число перестановок т шаров, в которых ровно шаров остаются на месте.

Решение. Введем обозначения. Ч свойство, состоящее в том, что при перестановке шаров шар остается на месте, = 1, т. Ч количество перестановок, обладающих ровно свойст вами, т.е. при перестановке шаров ровно из них остаются на сво их местах. Тогда по формуле включений и исключений запишем:

= i). Рассмотрим = где суммирование выполняется по всем сочетаниям длины из т свойств, количество сочетаний равно Ч количество перестановок из т Ч ша ров, так как г шаров должны оставаться на месте. Тогда значение и 3.6. Ладейные многочлены и многочлены попаданий Основная цель данного подраздела Ч показать возможности применения методов подсчета и оценивания при решении конк ретных задач. В то же время обсуждаемые здесь задачи сами по себе не лишены интереса, и в большей степени для тех, кто впер вые знакомится ними.

60 Глава 3. Методы подсчета и оценивания Ладейные многочлены Х Определение. Доской запрещенных позиций назы вается произвольный набор выделенных клеток шахматной доски, сохраняющих свое расположе ние относительно других клеток доски. Пример до ски запрещенных позиций показан на рис.

Рис. 3. Х Определение. Пусть С Ч доска запрещенных пози ций. Введем обозначения: Ч количество способов расста вить на доске запрещенных позиций так, чтобы они не били друг друга;

= 1 Ч количество способов расстановки О ладей на доске запрещенных позиций, т.е. способов не ставить ладьи на доску. Ладьи считаются неразличимыми. Производя щую функцию последовательности будем называть ладей ным многочленом доски С и обозначать = ' Задача. Найти ладейный многочлен для доски на рис. 3.2.

Рис. 3.2 Решение. Непосредственным подсчетом можно установить, что 1, = 1 и = 0, /' 2. Тогда R(x, = 1 + х.

Задача. Найти ладейный многочлен доски на рис. 3.3.

Решение. Непосредственным подсчетом можно установить, что = = 2, = 1 и = 0, 3. Тогда Задача. Найти ладейный многочлен доски на рис. 3.4.

Рис. 3.4 Решение. Непосредственным подсчетом можно установить, что = = 3, = 1 и = 0, /' 3. Тогда R(x, = 1 + + Определение. Доски и называются неза висимыми, если их клетки располагаются на различных горизонталях и вертикалях. При мер независимых досок показан на рис. 3.5.

3.6. Ладейные многочлены и многочлены попаданий Свойства ладейных многочленов Х Свойство 1. Правило произведения. Пусть R(x, и R(x, Ч ладейные многочлены независимых досок и Если доска то R(x, С) = R(x, Доказательство. Пусть Ч расстановка ладей на доске Ч расстановка ладей на доске Тогда тс = Ч переста новка ладей на доске С = и Верно и обратное. Пусть и Ч множество расстановок ладей на доске, соответственно и Тогда прямое произведение Ч множество рас становок ладей на доске С.

Обозначим веса расстановок: где Ч число ладей в перестановке = где Ч число ладей в перестановке Тогда вес перестановки равен = В соответствии с тем, как введены веса перестановок, ладей ные многочлены можно записать как сумму весов элементов мно жеств:

и Многочлены и С) удовлетворяют всем усло виям правила обобщенного произведения (см. в соответст вии с которым R(x, С) = R(x, Задача. Найти ладейный многочлен доски С на рис. 3.6.

Пусть Ч доска из одной клетки, R(x, = 1 + х. Ясно, что доска С состоит из независимых досок Отсюда следует, что Х Свойство 2. Правило суммы. Пусть С Ч доска РИС. 3. запрещенных позиций. Введем обозначения:

Ч доска с ладьей в клетке а Ч index);

Ч доска с уда ленной клеткой а (е Ч Тогда Для доказательства данного свойства вновь рассмотрим ладей ный многочлен как сумму весов перестановок. Все расстановки множества разобьем на два подмножества и, Ч пе рестановки с ладьей на клетке а;

Ч перестановки, которые не занимают клетку ос.

62 Глава 3. Методы подсчета и оценивания Тогда Множитель х перед скобкой Ч это вес ладьи в перестановке которая поставлена на выделенную клетку а.

Задача. Найти R(x, С) для доски на рис. 3.7.

Решение. Воспользуемся правилом суммы, по ко торому Отметим, что по виду полученного ладейного многочлена (производящей функции) можно сказать, что число способов расставить две ладьи на доску С равно 4.

Х Свойство 3 для прямоугольных досок. Пусть С Ч прямоугольная доска запрещенных по зиций размером т х п, т Ч число горизонта лей;

л Ч число вертикалей (рис. 3.8).

На квадратной доске размером k х можно способами расставить ладей. Различных досок k х k на доске т х п можно выбрать способами 3. Отсюда = способов расставить k ла дей на исходной прямоугольной доске. Тогда R(x, С) = = Задача. Найти R(x, С) для прямоугольной доски С размером Решение.

_ Коэффициент при показывает, что число способов поставить две ладьи на такую доску равно 3.6. Ладейные многочлены и многочлены попаданий 3.6.2. Многочлены попаданий Определение. Пусть дана квадратная доска размером л х л с запрещенными позициями (рис. 3.9). Обозначим через количество перестановок на квадратной доске л ладей, k из которых занимают запрещенные позиции.

Многочленом попадания называется произ водящая функция = последо Рис. 3. вательности Установим связь между многочленом попаданий и ладейным многочленом. Введем обозначения:

= Ч множество всех перестановок л ладей на до ске л х П = Ч множество весов;

Ч весовая функция, га (я) е Ч вес перестановки я е Ч запрещенных клеток на доске л х л;

Ч свойства перестановок;

я е обладает свойством если ее ладья занимает запрещенную Р ( \ О, в противном е.

= Ч сумма весов перестановок со свойством ) перестановок со свойствами...Р: ), суммирование выполняется по всем \ / J сочетаниям Длины k из т свойств, число сочетаний Принцип включения и исключения позволяет определить Так как нас интересует лишь количество перестановок, то будем полагать = 1. Нетрудно установить, что = - где Ч количество способов расставить на запрещенных по зициях доски я х и. Тогда (k) = (п (п -k 64 Глава 3. Методы подсчета и оценивания Заметим, что = 0 для всех k > п. С другой стороны, если т < то = О для всех k > т. Поэтому последнее выражение примет вид (л -k (л = (-1) + Найденное выражение ляет записать многочлен попаданий в виде Суммирование выполняется по координатам уз лов сетки на рис. 3.10. Замена переменных сумми рования k + i и в последнем выражении по зволяет упростить многочлен попаданий и приво k дит его к виду E(t) =, где суммирование уже выполняется по узлам сетки на рис. Таким образом, или Рис. 3. Для более компактной записи последнего выражения введем оператор Е~, действие которого распространим на функции це лочисленного аргумента:

- 1) и - k).

Например, = (л - 1)! и = (л -.

Заметим, что = (t- = Тог да многочлен попаданий перепишем в виде п =o где x = Таким образом, = R((t 3.6. Ладейные многочлены и многочлены попаданий Задача. Найти многочлен попаданий для доски 3 х 3 с запрещенными позициями на рис. 3.12. За прещенные позиции отмечены темным цветом.

Решение. Найдем ладейный многочлен доски за Рис. 3. прещенных позиций, которая состоит из двух неза висимых досок. Тогда R(x) Х = (1 + + Зх + = Значит = R((t- = (1 + + = 1 Х 3! + - 3! + 3! + [(t- l)s 3! = = 3! + - 1)2! + - 1! + (t - 0!.

Итак, E(t) = + + Анализ коэффициентов при показывает, что число пе рестановок, в которых ладьи не занимают запрещенных клеток, равно 1 (коэффициент при );

перестановок с одной ладьей на запрещенных позициях Ч 3 (коэффициент при перестановок с двумя ладьями на запрещенных позициях Ч 1 (коэффициент при перестановок с тремя ладьями на запрещенных позициях (коэффициент при ).

Глава Генерация комбинаторных объектов О комбинаторных алгоритмах часто необходимо порождать и исследовать все элементы некоторого класса комбинаторных объектов. Наиболее общие методы решения таких задач основы ваются на поиске с возвращением, однако во многих случаях объ настолько просты, что целесообразнее применять специализированные методы. Задачи, требующие генерации комбинаторных возникают при вычислении комбина торных формул. Например, часто приходится вычислять суммы, имеющие вид где суммирование выполняется по всем последовательностям удовлетворяющим некоторым ограничениям.

В алгоритмах порождения комбинаторных объектов нас преж де всего будет интересовать сложность алгоритмов, т.е. общее ко личество времени, требующегося для порождения всего множе ства объектов.

Поиск с возвращением Использование компьютера для ответа на такие вопросы, как сколько существует перечислите все возмож или лесть ли обычно требует исчерпывающего поиска множества решений. Метод поиска с возвращением по стоянно пытается расширить частичное решение. Если расшире ние текущего частичного решения невозможно, то возвращаются к более короткому частичному решению и пытаются снова его продолжить.

Идею поиска с возвращением легче всего понять в связи с за дачей прохода через лабиринт: цель Ч попасть из некоторого за данного квадрата другой заданный квадрат К путем последо Поиск с возвращением вательного перемещения по квадратам.

Трудность состоит в том, что существу ющие преграды запрещают некоторые к перемещения. Один из способов прохо да через лабиринт Ч это двигаться из начального квадрата в соответствии с и двумя правилами:

Х в каждом квадрате выбирать еще не исследованный путь;

Х если из исследуемого в данный момент квадрата не ведут не исследованные пути, то нужно вернуться на один квадрат назад по последнему пройденному пути, по которому при шли в данный квадрат.

Первое правило говорит о том, как расширить исследуемый путь, если это возможно, а второе правило Ч о том, как выходить из тупика. В этом и состоит сущность поиска с возвращением:

продолжать расширение исследуемого решения до тех пор, пока это возможно, и когда решение нельзя расширить, возвращаться по нему и пытаться сделать другой выбор на самом близком шаге, где имеется такая возможность.

Общий алгоритм В самом общем случае полагаем, что решение задачи состоит из вектора конечной, но неопределенной длины, удовлетворяющего некоторым ограничениям. Каждое где Ч конечное линейно упорядоченное множество. Таким обра зом, при исчерпывающем поиске должны рассматриваться эле менты множества Л, х х...х для = О, 1, в качестве возможных решений. В качестве исходного частичного решения примем пустой вектор () и на основании имеющихся ограничений какие элементы из являются кандида тами в Обозначим это подмножество кандидатов через В результате имеем частичное решение В общем случае для расширения частичного решения от до кандидаты на роль выбираются из с Если частич ное решение не представляет возможности для вы бора элемента то = 0;

возвращаемся и выбираем новый эле мент Если новый элемент выбрать нельзя, возвращаем ся еще дальше и выбираем новый элемент и т.д. Этот процесс удобно представлять в терминах прохождения дерева поиска в 68 Глава 4. Генерация комбинаторных объектов глубину. Процедура поиска с возвращением для нахождения всех решений формально представлена в алгоритме Алгоритм 4.1. Общий алгоритм поиска с возвращениями 1;

частичного while k > 0 do begin while 0 do begin частичное решение } = Ч выбранного then Сохранить решение;

k = 1;

частичное с k = kЧ частичное end.

Поиск с возвращением приводит к алгоритмам экспоненциа льной сложности, так как из предположения, что все решения имеют длину не более л, исследованию подлежат приблизительно элементов. В предположении, что все \ = констан ты, получаем экспоненциальную сложность Нужно помнить, что поиск с возвращением представляет собой только метод. Непосредственное его применение обычно ведет к алгоритмам, время работы которых недопустимо велико. Поэто му, чтобы метод был полезен, к нему нужно относиться как к схе ме, с которой следует подходить к задаче. Схема должна быть хо рошо приспособлена (часто это требует большой изобретательно сти) к конкретной задаче, так чтобы в результате алгоритм годил ся для практического использования.

4.2. Перестановки различных элементов Перестановки множества различных элементов относятся к часто порождаемым комбинаторным объектам. Без ограничения общности можно полагать, что элементами множе ства являются целые числа от 1 до п, т.е. рассматриваются пере становки целых чисел 1, п.

4.2. Перестановки различных элементов Порождение перестановок на основе метода поиска с возвра щениями выполняется в алгоритме 4.2. Заметим, что в процессе приспосабливания общего алгоритма поиска с возвращения ми к задаче порождения перестановок мы не вычисляли и не хра нили явно множества В этом случае легче и достаточно хра нить только наименьшее значение из т.е. и следующее зна чение вычислять по мере необходимости. Проверка условия 0 соответствует условию поскольку алгоритм устроен так, что перебор значений элемента выполняется в порядке их возрастания. Поэтому неравенство > п соответствует пустому множеству кандидатов = 0.

Алгоритм 4.2. Порождение перестановок методом поиска с возвращением = 1;

k = частичного k > 0 do begin while do begin = частичное решение } = 1;

выбранного while and do = + n then Перестановка Ч решение;

else begin k k + частичное while and do = end;

end;

k = k - 1;

уменьшить частичное end;

Function элемента перестановке flag= TRUE;

while i < k flag do begin if = then flag = FALSE;

i= i+ 1;

end.

70 Глава 4. Генерация комбинаторных объектов Программа на языке Pascal реализации рассмотренного мето да генерации перестановок приводится в алгоритме 4.3. Следует отметить, что в программе размерность (длина) и перестановок читается из файла и порождаемые перестановки также сохраня ются в файле. Попутно программа вычисляет время порождения всех перестановок с точностью до сотых долей секунды, которое сохраняется в конце файла сгенерированных перестановок.

Алгоритм 4.3. Программа на порождения перестановок методом поиска с возвращением Program uses Const Type of Longlnt;

Function Boolean;

( Поиск элемента sk в перестановке } Var i yes i:=l;

while (i0 do begin while do begin repeat следующего кандидата на место until or if then begin 4.3. Эффективное порождение перестановок for i:=l to n do end else первого кандидата на место while and Not do end;

Var a n f (Текстовый rSeclOO delta ) открыт для длины открыт для BackTrack rSecond, div delta mod 4.3. Эффективное порождение перестановок Последовательность я! перестановок на множестве в которой соседние перестановки различаются так мало, как только возможно, Ч лучшее, что можно надеяться с точки зрения мини 72 Глава 4. Генерация комбинаторных объектов мизации объема работы, необходимого для перестано вок. того чтобы такое различие было минимально возможным, любая перестановка в нашей последовательности должна отличать ся от предшествующей ей транспозицией двух соседних элементов.

Такую последовательность перестановок легко построить рекур сивно. Для = 1 единственная перестановка удовлетворяет на шим требованиям. мы имеем последовательность перестановок на множестве в которой после довательные перестановки различаются только транспозицией смежных элементов. Расширим каждую из этих (и Ч 1)! перестано вок, вставляя элемент п на каждое из я возможных мест. Порядок порождаемых таким образом перестановок будет следующим:

[ [ [ [ [ [ Данную последовательность перестановок можно порождать итеративно, получая каждую перестановку из предшествующей ей и небольшого количества добавочной информации. Это дела ется с помощью трех векторов: текущей перестановки я = обратной к ней = и записи направления в котором сдвигается каждый элемент если он сдвигается влево;

если вправо;

и 0, если не сдвигается).

4.3. Эффективное порождение перестановок Элемент сдвигается до тех пор, пока не достигнет элемента, боль шего, чем он сам;

в этом случае сдвиг В этот мо мент направление сдвига данного элемента изменяется на проти воположное и передвигается следующий меньший его элемент, который можно сдвинуть. Поскольку хранится об ратная к я, то в л легко найти место следующего меньшего эле мента. Алгоритм 4.4 представляет собой реализацию рассмотрен ного метода.

Корректность алгоритма доказывается индукцией по п. Алго ритм порождения всех перестановок линеен, сложность его определяется как + Алгоритм 4.4 Ч один из наиболее эф фективных алгоритмов для порождения перестановок.

Рабочая программа на языке Pascal реализации эффективного метода генерации перестановок приводится в алгоритме 4.5.

В качестве примера в алгоритме 4.6 приводится программа ре ализации эффективного метода генерации перестановок, напи санная на языке Си.

Алгоритм 4.4. Метод эффективного порождения перестановок = = т = n + = т while do Х ~ [т ;

р.

4.5. Программа на порождения перестановок эффективным методом Program генерация uses Const { n<=max_n } Type of Integer;

Var f { Генерация перестановок z[l],.../ } 74 Глава 4. Генерация комбинаторных объектов Procedure Var Const k Var p,d begin;

for i:=l to n do begin end;

z [ while do begin { Печать перестановки } for i:=l to n do while do begin end;

Var z n delta begin ) открыт для длины Close открыт для div delta mod 4.3. Эффективное порождение перестановок Алгоритм 4.6. Программа на Си порождения перестановок эффективным методом ttinclude void перестановок // z[l], z[2],..., z[n] int int FILE struct long delta;

unsigned long int int for( i++ ){ z перестановки i++ while ( ) 76 Глава 4. Генерация комбинаторных объектов delta*=60;

счета сек", 4.4. Порождение подмножеств множества Порождение подмножеств множества эквивалентно порождению двоичных наборов подмножеству, если и только если разряд равен единице. Таким образом, задача порождения всех подмножеств множества сводится к задаче порождения всех возможных двоичных последовательно стей длины п. Очевидно, что наиболее прямым способом порожде ния всех двоичных наборов длины п является счет в системе счисле ния с основанием 2, как показано в алгоритме 4.7.

Перевод этого алгоритма на язык подмножеств множества осуществляется согласно алгоритму 4.8, где добавлен фиктивный элемент Алгоритм Счет в системе счисления с основанием для порождения всех наборов for i = 0 to п do = 0;

while 1 do while = Алгоритм 4.8. Порождение подмножеств счетом в двоичной системе счисления Print(S), while do while e S do \. ~, 4.4. Порождение подмножеств множества Задача Счастливый билет. Дано п произвольных цифр: где и целое число Написать программу, которая расставляла бы между каждой парой цифр записанных именно в таком порядке, знаки +,- так, чтобы значением получившегося выражения было число т. Например, если соответственно 1, 9 и т = 5, то подойдет следующая расстановка знаков:

Если требуемая расстановка невозмож на, то сообщить об этом.

Исходные данные вводятся из текстового файла, имеющего сле дующую структуру:

Первая строка Ч целое число п.

Вторая строка Ч целое число т.

Третья строка Ч цифры через пробелы.

Результаты расчетов сохранить в текстовом файле.

Пример файла исходных данных:

6 5 8 8 4 7 5 2 3 4 5 7 8 Пример файла выходных данных:

6+5+8+8+4+7+5+2+3+4-5+7+8+9 = 6+5+8+8+4+7+5-2-3+4+5+7+8+9 = 6+5+8+8+4+7-5+2+3+4+5+7+8+9 = 6-5+8+8+4+7+5+2+3+4+5+7+8+9 = Время счета = 0.60 с.

Ясно, что для решения данной задачи достаточно выполнить полный перебор всех возможных вариантов расстановки знаков между каждой парой цифр выбрать те расстанов ки знаков которые удовлетворяют условию равенства суммы величине т. Всего позиций для расстановки равно п Ч 1, а значит для полного перебора необходимо проверить двоич ных наборов, если будет соответствовать 1, а Ч 0.

Программа решения задачи счастливый билет представлена алгоритмом 4.9. Процедура SubSet (подмножество) этой програм мы реализует рассмотренный выше алгоритм 4.7 счета в системе счисления с основанием 2 для порождения всех (п Ч наборов. Порожденные двоичные наборы используются в проце дуре (сумма) для формирования суммы, соответствующей данному набору знаков где соответствует 1, а Ч 0.

78 _ Глава 4. Генерация комбинаторных объектов Алгоритм 4.9. Программа на решения Счастливый билет Program uses Const Type of Longlnt;

Procedure var var ) Var S Longlnt;

i Integer;

begin for i:=l to do if then begin for i:=l to n-1 do begin if b[i]=l then else = - число Procedure var var Var b: Vector;

i begin for i:=l to n do while do begin Summa a,b, ;

while b[i]=l do begin end;

4.5. Генерация размещений с повторениями Var a f delta открыт для количества счастливой for i:=l to n do ) открыт для Second, SeclOO) 60 + delta div mod 4.5. Генерация размещений с повторениями Порождение множества всех размещений с повторениями длины k из элементов эквивалентно генерации множества чисел в системе счисления с основани ем и: на месте в размещении будет располагаться элемент если цифра в разряде соответствующего числа равна Всего размещений с повторениями п. для k = 2 и 3 все наборы длины два в системе счисления с основанием три можно записать: Тогда эквивалентные раз мещения примут вид Алгоритм использует фиктивный элемент при порож дении наборов длины k в системе счисления с основанием и, где 80 Глава 4. Генерация комбинаторных объектов е п Ч /' = О, k, т.е. Ч это цифры генерируемого числа в системе счисления с основанием п.

Алгоритм 4.10. Счет в системе счисления с основанием п для порождения всех наборов while 1 do +1.

4.6. Порождение сочетаний Обычно требуются не все подмножества множества а только те, которые удовлетворяют некоторым ограничени ям. Особый интерес представляют подмножества фиксирован ной длины k, сочетаний из п предметов по Как обычно, предполагаем, что основным множеством является множество натуральных чисел таким образом, будем порождать все сочетания длины k из целых чисел Так, например, сочетаний из шести предметов по три (т.е. трехэлементные подмножества множества записываются в лексиког рафическом порядке следующим образом:

123 135 234 124 136 235 125 145 236 126 146 245 134 156 246 Сочетания в лексикографическом порядке можно порождать последовательно простым способом. Начиная с сочетания следующее сочетание находится просмотром текущего со четания справа налево с чтобы определить место самого пра вого элемента, который еще не достиг своего максимального зна чения. Этот элемент увеличивается на единицу, и всем элементам справа от него присваиваются новые возможные наименьшие значения, как показано в алгоритме Алгоритм порождения всех сочетаний линеен, его сложность 4.6. Порождение сочетаний Алгоритм 4.11. Порождение сочетаний for i = 0 to k do = i;

j 0 do while Cj - do j = j -1;

Cj Cj Задача. Выпуклый Дано множество пар целых чисел Ч координаты точек на плоскости.

Написать программу выделения тех точек из заданного множест ва, которые являются вершинами выпуклого многоугольника, содержащего все точки. Исходные данные представле ны в текстовом файле, имеющем следующую Первым числом в файле является целое Ч количество точек. Последую щие числа определяют п пар целых Ч координаты точек. Ре зультаты признаки принадлежности исходных точек выпуклому многоугольнику: 0 Ч точка не принадлежит, 1 Ч точ ка принадлежит, сохранить в текстовом файле.

Пример файла исходных данных:

0 0 9 9 5 1 2 3 2 7 1 1 5 4 6 7 1 5 6 7 3 4 5 7 7 8 8 7 6 Выходной файл для данного примера:

10000 Решение. Если не применять специальных методов, то в каче стве решения можно использовать следующий алгоритм. Ясно, что точка является вершиной выпуклого многоугольника, если она не лежит ни в одном вершинами которых являются исходные точки без рассмат риваемой точки Всего треугольников из п точек можно со ставить + Тогда сложность задачи полного перебора угольников для каждой точки составит ). Реализация данного подхода представлена программой на языке Pascal в ал горитме 4.12.

82 Глава 4. Генерация комбинаторных объектов 4,12. Программа поиска точек выпуклой оболочки Program uses const type of Integer;

of Integer;

var f z вектор выпуклой обо Procedure var Const k Var begin Ч 1 Х Х Ч Г ? Х, Ч Х Г 1 Х Ч j for to n do begin if or (i=k2) or (i=k3) then continue;

if a=0 then continue;

signl =a div abs if a=0 then continue;

sign2 div abs if a=0 then continue;

sign3 =a div abs if and (sign2=sign3) then Procedure var Var i begin for i:=l to n do 4.7. Порождение композиций и разбиений сочетаний из п по Const k :Integer=3;

Var с begin for i:=l to k do j:=l;

while j<>0 do begin while c[j]=n-k+j do for i:=j+l to k do end;

Var i,n исходных begin Reset(f);

открыт для for i:=l to n do begin открыт для номера точек выпуклой for i:=l to n do end.

4.7. Порождение композиций и разбиений Рассмотрим задачу порождения разбиений положительного числа п в последовательность неотрицательных целых чисел + +... = Разбиение называется композицией числа п, если учитывается порядок чисел Как представляют инте рес композиции, в которых либо все 0, либо все > 0.

84 Глава 4. Генерация комбинаторных объектов Разбиение разбиением числа п, если все 0 и порядок чисел не важен. По разбиение числа я является мультимножеством (см. п.

Рассмотрим примеры разбиения числа п = 3.

(1, 2), (2, 1) Ч все композиции числа три из двух частей, > 0.

(1, 1, 1) Ч все композиции числа три из трех частей, > 0.

(О, 3), (1, 2), (2, 1), (3, 0) Ч все композиции числа три из двух час тей, (3), (1, 2), (1, 1, 1) Ч все разбиения числа три.

Композиции О Композицию 0, + = можно интерпретировать следующим образом. Каждое значение +... + 1/ представим как сумму единиц, количество кото рых Индекс у элемента показывает его принадлежность разло жению числа Таким образом, мы ввели k типов различных эле ментов значение каждого из них равно единице. Те перь любую композицию можно представить как сумму, составлен ную из п произвольных единиц множества Суммируя подобные единицы с одинаковыми индексами, получим соответ ствующие значения композиции. Данное соответствие является взаимно однозначным, откуда и следует, что число композиций равно числу сочетаний с повторениями = = Каждое из сочетаний можно интерпретировать как расстановку 1 и О длины п + k - в которой п единиц и k - 1 нуль, т.е. каждому соче танию ставим в соответствие (п + число из единиц и нулей;

и обратное. Суммируя в таком числе слева направо единицы между нулями (их k - будем получать соответствующие значения членов (их k) композиции. Например, одному из сочетаний 11011100111101111111010 соответствует композиция (2,3,0,4,7,1,0) числа 17.

Ясно, что методы предыдущего раздела генерации подмно жеств множества легко применить к последовательному порож дению рассмотренных композиций 0.

Композиции > О Удобное представление композиций получается из рассмотре ния целого числа п как отрезка прямой, состоящего из отрезков единичной длины. Линия разделена п - 1 точками, и композиция 4.7. Порождение композиций и разбиений получается пометкой некоторых из них. Элементами компози ции являются просто расстояния между смежными точками. На рисунке показано графическое представление композиции для числа п = 8. Очевидно, что каждая композиция чис ла соответствует способу выбора подмножества из п - 1 точек.

Каждой точке можно сопоставить двоичную цифру, и, таким об разом, композиции п будет соответствовать (п число. В этой интерпретации композиция из соответст вует (п - числу ровно с k - 1 единицами, и поэтому существует таких композиций.

Воспользуемся методами предыдущего раздела для генерации композиций > 0. Учитывая, что в композиции z\ + +...+ каждый из > 0, тогда для новых переменных = - 0) со ответствующая композиция будет для числа = - Генерация слагаемых 0 композиции подробно разобрана в предыдущем разделе, добавляя к каждому из по единице, получим слагаемые 0 композиции Разбиения Разбиения п отличаются от композиций п тем, что порядок компонент не важен, так что, например, не делается различия между, скажем, 2+1+1. Таким образом, разбиение п можно рассматривать как которое записы вается следующим способом:

где имеется вхождений z\, вхождений вхождений k и т. д. и и = Каждое разбиение удовлетворяет условию > >... > Рассмотрим пример генерации разбиений для п = Последовательность генерации разбиений данного примера далее будет положена в основу алгоритма порождения полного списка разбиений.

Идея приведенного списка разбиений состоит в том, чтобы пе реходить от одного разбиения к следующему, рассматривая са мый правый элемент разбиения. Если достаточно ве 86 Глава 4. Генерация комбинаторных объектов > 1), можно исключить два для того, чтобы добавить еще одно + 1 (или включить одно + если в момент его нет). Если = 1, то + достаточно велико для того, чтобы добавить Zk-\ + 1. Все, что остается, превращается в соответствующее число единиц и формируется новое разбиение.

,1} Алгоритм использует рассмотренный процесс для порож дения всех разбиений числа п.

Алгоритм 4.13. Генерация разбиений числа = п;

= т = + while k 0 do Х ' =1;

if Summa then = 4.7. Порождение композиций и разбиений Алгоритм 4.13 линеен, так как число операций, необходимых для перехода от одного разбиения к другому, ограничено кон стантой, не зависящей от и k.

Программа на языке Pascal реализации рассмотренного мето да генерации разбиений чисел приводится в алгоритме От метим, что в программе число для разбиения п читается из файла, а порождаемые разбиения сохраняются в файле. Попутно про грамма вычисляет полное время генерации всех разбиений с точ ностью до сотых долей секунды, которое сохраняется в конце файла сгенерированных разбиений.

Алгоритм 4.14. Программа на генерации разбиений числа п Program числа uses Const { } Type of Integer;

Var f z,m Procedure var Var i begin Write (f, ' { for i:=l to k do begin if then }' ) ;

Procedure числа Var begin;

88 _ Глава 4. Генерация комбинаторных объектов z while k<>0 do begin Print (т, z, k) if m[k]=l then begin [ k ] * z [ k ] end;

if z[k-l]=z[k]+l then begin end else begin if then begin k:=k+l end;

Var n для delta begin ) ;

открыт для числа Close открыт для SeclOO) rSeclOO) div delta mod Close 4.8. Генерация случайных перестановок 4.8. Генерация случайных перестановок Пусть тс = Ч произвольно выбранная перестанов ка целых чисел 1, п, например, я = (1, и) Ч тождествен ная. Случайную перестановку можно получить за линейное время из выбранной перестановки я = выполнив в ней п транспозиций (см. п.7.4).

Для промежуточных перестановок введем верхний индекс, значение которого будет соответствовать количеству выполнен ных транспозиций. Один из элементов в каждой транспозиции выбирается случайным образом. Индекс такого элемента уста навливается функцией которая порождает независимые случайные целые числа на отрезке [k, с равномерным распреде лением.

Положим = равной исходной перестановке я = получается из предыдущей перестановки = п. Между элементами перестановок,,..., ра венства где k=l, п.

Покажем, что после выполнения всех указанных п транспози ций равновероятно получение любой из п! возможных перестано = чисел доста точно проверить, что = а) = С этой целью введем со бытия k п.

Вероятности данных событий, согласно схеме формирования перестановок равны равны = k п.

90 _ Глава 4. Генерация комбинаторных объектов Условие в событии k = п, обеспечивает выбор элемента из множества которое совпадает с множеством Индекс же n) элемента является неза висимой случайной величиной с равномерным распределением на отрезке [k, n] целых чисел.

Теперь заметим, что ) = ст &я " = = 1 = = Рассмотренный метод генерации случайной перестановки представлен в алгоритме 4.15.

Алгоритм 4.15, Генерация случайной перестановки for to n do = k;

for k = 1 to n - 1 do или, если генерацию перестановки вести с конца, for k 1 to n do for k = n to 2 do Сортировка и поиск здесь вопросы можно отнести к наиболее часто встречающимся в задачах машинной обработки данных.

Почти во всех компьютерных приложениях множество объектов должно быть переразмещено в соответствии с некоторым заранее определенным порядком. Очевидно, что с сортированными дан ными легче работать, чем с произвольно расположенными. Сор тировка больших объемов данных составляет значительную часть коммерческой обработки данных, эффективные алгоритмы для сортировки важны и с экономической точки зрения. Эффектив ность оценивается с точки зрения требуемых памяти и времени, а также простоты программирования. Простота программирова ния предполагает и простоту понимания используемого метода, поскольку для того, чтобы написать хорошую программу, важно хорошо понять соответствующий метод. В наших же оценках мы будем учитывать только число сравнений. Самые простые алго ритмы сортировки, основанные на сравнении элементов, имеют сложность порядка а лучшие из них обходятся количеством сравнений Задачу сортировки можно сформулировать так: дана последо вательность из п элементов выбранных из множества, на котором задан линейный порядок, т.е. для любых выпол няется либо < либо либо = либо > либо Требуется найти перестановку = этих элементов, которая отобразит данную последовательность в неубывающую последовательность Как правило, далее будем получать саму упорядоченную последовательность, а не упорядо чивающую перестановку п.

Методы сортировки классифицируются на внутренние (когда данные размещаются в оперативной памяти) и внешние (когда данные размещаются на внешней Внешняя сортировка составляет часть таких приложений, в которых в работу вовлека ется гораздо больше элементов, чем можно сразу запомнить в оперативной памяти. Поэтому методы внешней сортировки при 92 Глава 5. Сортировка и поиск к данным, находящимся на внешних устройствах памя ти, и имеют огромное коммерческое значение.

Внутренняя сортировка важна как для разработки алгоритмов, так и для коммерческих приложений. Сортируемые данные раз мещаются в оперативной памяти. Здесь рассматриваются именно методы внутренней сортировки данных. Известно много алго ритмов сортировки данных. Почему же так много методов сорти ровки? Ответ состоит в том, что каждый метод имеет свои преи мущества и недостатки, поэтому он оказывается эффективнее других при некоторых структурах данных и аппаратной части.

Здесь же мы не пытаемся охватить даже те из них, которые счи таются важными;

скорее, мы ограничимся методами, оказавши мися полезными в разработке алгоритмов и в практической их ре ализации. Рассматриваемые здесь методы сортировки активно используются при разработке алгоритмов во многих разделах данного пособия. Полезно изучить характеристики каждого ме тода сортировки, чтобы можно было производить разумный вы бор для конкретных приложений. К счастью, задача изучения этих алгоритмов не столь уж громоздка.

Сортировка вставками Сортировка вставками элементов относится к наи более очевидным методам (алгоритм 5.1). Для компактности ал горитма вводится фиктивный элемент значение которого устанавливается равным -оо. Сортировка проходит цикл = 2, для каждого j элемент вставляется в свое правильное место среди При вставке элемент разме щается в просматриваются имена они сравни ваются с и сдвигаются вправо, если обнаруживается, что они больше w. Имеется фиктивный элемент значение которого служит для остановки просмотра слева.

Алгоритм 5.1. Сортировка вставками = forj = I while w do { 5.2. Пузырьковая сортировка Сложность алгоритма определяется числом проверок условия < цикле. Сравнение < для конкретного = 2) вы полняется 1 + где dj Ч число элементов, больших и стоя щих слева от него, т.е. dj Ч это число инверсий, у которых второй элемент Числа dj составляют таблицу инверсий а так как 0 fl"i л - 1, 0 - О 1, = 0, то в худшем п случае сортировка элементов + 2ч = Ч - - = 0(n ) сравнении. Сложность сортировки вставками является квадратичной.

5.2. Пузырьковая сортировка Рассматриваемый метод пузырьковой сортировки последова тельности представляет собой наиболее очевидный метод систематического обмена местами слева направо смежных элементов, не отвечающих выбранному порядку, до тех пор пока каждый элемент не оказывается на правильном месте. Эта техни ка получила название пузырьковой сортировки, так как большие элементы пузырьками всплывают вверх в конец списка. Реали зация метода представлена алгоритмом 5.2. В алгоритме исполь зуется переменная значение которой при каждом проходе цик ла устанавливается равным наибольшему индексу t, такому, что все элементы уже находятся на своих окончатель ных позициях. Ясно, что не имеет смысла продолжать просмотр для указанных элементов.

Алгоритм 5.2. Пузырьковая сортировка while if > then I (b=t.

Сложность алгоритма определяется числом проверок условия > в цикле и числом обменов которое равно числу инверсий в исходной перестановке элементов Опре делим число сравнений. В худшем случае верхняя граница b - 94 _ Глава 5. Сортировка и поиск вложенного for на каждом шаге внешнего цикла while будет уменьшаться на 1, тогда число сравнений равно -1) = (я - 1) + + - 2) +...+ 1 = Ч - = Сложность пузырьковой сорти ровки является квадратичной.

В алгоритме 5.3 представлена полная пузырьковая сортиров ка. Это наиболее популярный и упрощенный вариант алгоритма 5.2. Ясно, что основным достоинством алгоритма полной пузы рьковой сортировки является легкость программирования.

Сложность же алгоритма 5.3 остается постоянной, равной п = (п -1) + (п = - = и не зависит от рас положения исходных данных.

Алгоритм 5.3. Полная пузырьковая сортировка for i = 1 to n do begin forj = 1 to n - i do begin > then end;

end.

5.3. Сортировка перечислением Идея сортировки едовательности пере числением состоит в том, чтобы сравнить попарно все элементы и подсчитать, сколько из них меньше каждого отдель ного элемента (алгоритм Для подсчета числа элементов, ме ньших в алгоритме используется вспомогательный век тор После завершения алгоритма значения п определяют окончательное положение элементов в сор тированной последовательности Алгоритм 5.4. Сортировка перечислением for i = 1 to n do for i = п to 1 by -1 do begin forj = i - 1 to 1 by -1 do begin if > then = c, + else C = 5.4. Сортировка всплытием Флойда end;

for i = 1 to do begin;

сортированные Сложность алгоритма сортировки перечислением определяет ся парой вложенных циклов и составляет Величина слож ности не зависит от расположения данных в исходной последова тельности Пусть перестановка л = + 1, 1, п.

Алгоритм 5.4 сортировки перечислением определяет перестанов ку, которая соответствует расположению а исходных данных 5.4. Сортировка всплытием Флойда Все ранее упомянутые методы сортировки последовательно сти требовали сравнений порядка ), и лэто никуда не Рассмотрим один из наиболее элегантных и эффек тивных методов сортировки сложности предложенный До пор он остается самым оптимальным из сущест вующих методов. В алгоритме активно используется упорядочен ное двоичное дерево, пример которого представлен на рис. 5.1.

22 17 2 Рис. 5.1. Пример упорядоченного двоичного Значение в каждой его вершине не меньше, чем значение в его дерево называется частично упоря доченным, если свойство упорядоченности выполняется для каж дой из его вершин, однако для корня это свойство нарушается.

Пример частично упорядоченного дерева приведен на рис.

22 17 2 Рис. 5.2. Пример частично упорядоченного двоичного дерева 96 Глава 5. Сортировка и поиск Интересно отметить, что в ранее рассмотренных методах сор тировки сложности при выборе наибольшего (наименьше го) элемента, забывали информацию о других, забракованных элементах на эту роль, хотя эта проверка и выполнялась. Структу ра же дерева позволяет сохранить состояние процесса сортировки последовательности на каждом его шаге, с целью ис пользования этого состояния в дальнейших расчетах и уменьше ния числа операций сравнений при поиске наибольшего (наи меньшего) из оставшихся элементов.

Метод сортировки представлен в алгоритме 5.5, где исходная последовательность данных представляется в виде дерева на смежной памяти (одномерный массив В таком дереве ребра присутствуют неявно и вычисляются с помо щью арифметических операций над индексами элементов масси ва Ч смежной памяти. Пример двоичного дерева показан на рис. 5.3. Корень дерева Ч за каждой вершиной следуют вершины a[2k] и a[2k+l]. Использование смежной памяти для представления дерева имеет и другие преимущества, которые ста новятся очевидными после анализа алгоритма 5.5.

а[2] а[5] а[7] Рис. 5.3. Пример двоичного дерева на смежной памяти Основу алгоритма 5.5 составляет процедура SURFACE всплытия Флойда, которая за сравнений преобразует почти упорядоченное поддерево в упорядоченное. Поддерево представляется на одномерном массиве a[i..k], где Ч корень поддерева, a[k] Ч максимальный элемент массива, кото рый еще может принадлежать поддереву.

Рис. 5.4. Двоичное поддерево на смежной памяти a[i..k] 5.4. Сортировка всплытием Флойда Определим сложность процедуры SURFACE всплытия Флой да. Процедура заключается в том, что значение из корня (здесь может нарушаться условие упорядоченности) всплывает по на правлению к листьям (последний уровень вершин в дереве) до тех пор, пока дерево не преобразуется в упорядоченное. Во время всплытия на каждом уровне выполняется конечное число С опе раций сравнения элементов. Если положить, что высота дерева (число уровней в дереве) равна Л, то сложность одного всплытия составит С Х h = Высота h регулярного двоичного дерева из вершин легко находится из соотношения п 2 + +...+ где Ч количество вершин на уровне дерева, 1, п. От сюда высота дерева Л = + 1)1. Таким образом, сложность процедуры SURFACE всплытия Флойда составляет Рассмотренная процедура SURFACE всплытия Флойда позво ляет в почти упорядоченном дереве найти наибольший (наимень ший) элемент за число сравнений преобразуя дерево к упорядоченному виду. В результате найденный элемент будет располагаться в вершине дерева. Для сортировки же множества элементов из них по алгоритму 5.5 сначала организует ся почти упорядоченное двоичное дерево при помощи повторно го применения алгоритма SURFACE всплытия Флойда сначала к самым мелким его поддеревьям от листьев и затем ко все более крупным. Листья тривиально упорядочены, поэтому можно на чать с минимальных поддеревьев, содержащих несколько вер шин, и укрупнять их, каждый раз полностью, применяя алгоритм всплытия до тех пор, пока таким образом не будет достигнут ко рень дерева. Заметим, что каждое из поддеревьев, к которым при меняется алгоритм всплытия, удовлетворяет условию почти упо рядоченности, поскольку упорядочивание проходит от листьев к корню. Именно таким способом в алгоритме 5.5 осуществляется формирование исходного почти упорядоченного дерева.

После того как дерево упорядочено, наибольший (наимень ший) элемент оказывается в его корне. По алгоритму 5.5 найден ный элемент меняют местами с самым последним листом в дере ве (последний элемент рассматриваемого массива), дерево уме ньшается на одну вершину и все готово для определения нового наибольшего (наименьшего) элемента множества при помощи следующего применения процедуры SURFACE Флойда.

На рис. 5.5 показана полная последовательность перестановок и всплытий, которые происходят после формирования из исходно 98 Глава 5. Сортировка и поиск го множества почти упорядоченного дерева и вплоть до того, как в этом дереве останется всего одна вершина, а исходное множест во окажется отсортированным.

18 всплытие 66 / \ / \ \ 65 66 65 63 65 А /\56 А /\56 4А / 4 37 63 4 37 18 37 18 почти упорядоченное дерево всплытие перестановка 18 всплытие \ \ х \ 56 63 56 63 56 А 18 А /\ А 4 37 66 4 37 65 66 4 37 65 перестановка 37 всплытие 56 перестановка 56 18 37 18 37 4 63 65 66 4 63 65 66 56 63 65 всплытие 18 всплытие 4 56 63 65 перестановка 18 56 63 65 Рис. 5.5. Пример сортировки чисел методом Флойда Алгоритм 5.5. Сортировка всплытием Флойда сложности Program { Сортировка по всплытием Флойда } uses const = 1000;

массива данных для Vector = array[l..n] of Integer;

Var f файл для результатов 5.4. Сортировка всплытием Флойда procedure var a: vector;

n:

{ Заполнить вектор случайными числами } var i: integer;

begin for i:=l to n do end;

procedure var a: Vector;

{ Процедура всплытия Флойда по дереву } var begin while do begin if then if then else if a[j]>copy then begin end else break;

из end;

procedure var { Сортировка вектора методом Флойда } var i,k,w begin исходное частично упорядоченное for div 2 2 do процедуру всплытия Флойда для каждого for downto 2 do begin найденный максимальный элемент в конец end end;

100 Глава 5. Сортировка и поиск Var а : Vector;

исходных данных для i : Integer;

begin;

открыт для исходные for i:=l to n do сортированные for i:=l to n do ' [i] Оценим общую сложность алгоритма данных рас сматриваемым методом. Процедура SURFACE всплытия выполняется раз сначала для формирования исходного почти упорядоченного дерева (процедура применяется для каждой вер шины дерева) и затем п раз для всплытия каждого наибольшего (наименьшего) элемента в почти упорядоченном дереве. Так как сложность процедуры SURFACE всплытия Флойда составляет общая сложность алгоритма сортировки данных равна Это лучшая оценка, на что вообще можно надеяться при сор тировках, в основу которых положены сравнения данных. Дейст вительно, число возможных перестановок из элементов равно и только одна из них удовлетворяет условию нашей сортировки. Двоичный же поиск перестановки среди множества перестановок требует числа сравнений. Для упрощения воспользуемся формулой Стирлинга Тогда Задача. объединения отрезков. Текстовый файл содержит целые числа: Данная последовательность чи сел определяет на прямой п отрезков 1, п. Найти длину объединения указанных отрезков. Исходные данные пред ставлены в текстовом файле со следующей структурой. Первая строка файла: п Ч количество отрезков. Вторая, третья и т.д. стро ки файла содержат целые числа Ч границы соответствующих отрезков. Результаты расчетов длины объединения отрезков со хранить в текстовом файле.

5.4. Сортировка всплытием Флойда Пример файла исходных данных:

з О -1 О Пример файла выходных данных:

з Решение. Алгоритм 5.6 решения задачи основывается на пред варительной сортировке абсцисс в массиве Создается вспомогательный массив который поддерживает после сортировки массива отношение границ отрезков: = 1 Ч левая граница, g[i] = 0 Ч правая грани ца. Вычисление завершается простым просмотром массива за линейное время. Общая сложность алгоритма опреде ляется сложностью сортировки данных. В данном случае исполь зуется алгоритм пузырьковой сортировки сложности Алгоритм Программа расчета длины объединения отрезков Program uses const type of Integer;

var f ab отрезков g границ:

Procedure Var Var i, с :

begin перекрывающихся for i:=l to n do begin if then if then c:=c+l else end;

102 Глава 5. Сортировка и поиск границ и Var begin for i:=l to n do begin for j:=l to n-i do begin if ab[j] > then begin Var i, k n исходных :LongInt;

объединения begin Reset(f);

открыт для for i:=l to n do begin end;

открыт для Close 5.5. Последовательный поиск Задача поиска является фундаментальной в алгоритмах на ди скретных структурах. Удивительно то, что, накладывая незначи тельные ограничения на структуру исходных данных, можно по лучить множество разнообразных стратегий поиска различной степени эффективности.

5.5. Последовательный поиск При последовательном поиске подразумевается исследование элементов множества в том порядке, в котором они встречаются. Начни сначала и продвигайся, пока не найдешь нужный элемент;

тогда остановись. Такая последовательная процедура является очевидным способом поиска. Алгоритм 5. выполняет последовательный поиск элемента z в множестве Несмотря на свою простоту, последовательный поиск содержит ряд очень интересных идей.

Алгоритм Последовательный поиск с = 0;

поиска записи } с break;

then Запись найдена else Запись не найдена.

Оценим среднюю сложность поиска элементов множества Для нахождения элемента требуется сравнений.

Для вычисления же среднего времени поиска необходимо задать информацию о частоте обращения к каждому элементу множест ва. Будем предполагать, что частота обращения распределена рав номерно, т.е. что ко всем элементам обращаются одинаково час то. Тогда средняя сложность поиска элемента множества ся - / = = 0(п) линейной.

Рассмотрим распределение частот обращения к элементам в общем случае. Пусть обозначает частоту (распределение веро ятностей) обращения к элементу где и В этом случае средняя сложность (математическое ожидание) поиска элемента будет равна Хорошим приближением (= частот к действительности является закон для = 1, п. К. Зипф заметил, что наиболее употребите льное в тексте на естественном языке слово встречается с часто той, приблизительно обратно пропорциональной л.) п щая константа выбирается так, что = 1. Пусть элементы мно жества упорядочены согласно указанным частотам.

104 Глава 5. Сортировка и поиск Тогда с = = я Ч и среднее время успешного поиска со Я..с 1 п п + \ ставит = -п, что много меньше.

ft Последний пример показывает, что даже простой последовате льный поиск требует выбора разумной структуры данных множе ства, который бы повышал эффективность работы алгоритма. Бо лее того, это общепринятая стратегия, время от времени переупо рядочивать для большинства файлов во внешней памяти, когда последовательная природа файла диктует ся техническими характеристиками носителя информации.

Алгоритм последовательного поиска данных одинаково эф фективно выполняется при размещении множества на смежной или связанной памяти.

5.6. Логарифмический поиск Логарифмический (бинарный или метод деления пополам) по иск данных применим к сортированному множеству элементов < ХХХ < размещение которого выполнено на смежной па мяти. Для большей эффективности поиска элементов надо, чтобы пути доступа к ним стали более короткими, чем просто последова тельный перебор. Наиболее очевидный метод: начать поиск со среднего элемента, т.е. выполнить сравнение с элементом а, L J Результат сравнения позволит определить, в какой половине по следовательности tfj, продолжить поиск, применяя к ней ту же процедуру, и т.д. Основная идея бинарного поиска довольно проста, однако для многих хороших програм мистов не одна попытка написать правильную программу закон чилась Чтобы досконально разобраться в алгоритме, лучше всего представить данные <... < в виде двоичного дерева сравнений, которое отвечает бинарному поиску.

Двоичное дерево называется деревом сравнений, если для лю бой его вершины (корня дерева или корня поддерева) выполняет ся условие:

левого корня правого поддерева }.

5.6. Логарифмический поиск Пусть на очередном шаге деления пополам оказалось, что необ ходимо выполнить поиск среди элементов < В каче стве корня принимается элемент a,, где ] Ч наибольшее целое, меньшее или равное Левое поддерево располагает ся в векторе a,, а правое поддерево Ч в векторе )ХХХ. На рис. 5.6 показан пример двоичного дерева сравнений, ребра которого неявно выражаются рассмотренными выше отношениями между индексами элементов 5 Рис. 5.6. Пример дерева сравнений, отвечающего бинарному поиску среди сортированных 3,5,7,9,12,19,27, Поиск элемента z среди <...< методом деления попо лам представлен в алгоритме 5.8.

5.8. поиск z в <...< поиска = граница j = граница while i do begin т ;

текущего then I else > then i = т + 1 левая = т Ч 1 правая = 1 then Запись найдена;

else Запись отсутствует.

Глава 5. Сортировка и поиск Средняя сложность бинарного поиска среди элементов < <ХХХ< сравнима с двоичного дерева (рис В худ шем случае искомый элемент может оказаться либо на последнем уровне, либо вообще не будет найден. На каждом уровне необхо димо выполнить определенное число сравнений. В п.5.4 установ лено, что уровней в дереве + 1)1. Значит, сложность поис ка является логарифмической что оправдывает и назва ние самого метода поиска.

Необходимо отметить, что рассмотренный метод бинарного поиска предназначен главным образом для сортированных эле ментов <...< на смежной памяти фиксированного п раз мера. Если же размерность вектора динамически меняется, то экономия от использования бинарного поиска не покроет затрат на поддержание упорядоченного расположения <...< 5.7. Сортировка с вычисляемыми адресами Пусть Ч исходная последовательность сортируе мых целых чисел и л = Ч упорядочивающая переста новка этих элементов Принятое ограничение, что Ч целые числа, не ведет к потере общности рассматривае мых ниже алгоритмов. Сортированная последовательность подсказывает очевидный способ использования значений этих элементов в качестве индексов (адресов) их расположения в мас сиве где = Получим упорядоченную последо вательность <...< а значит, и упорядоченную последо вательность исходных данных В качестве примера рассмотрим частный случай сортировки элементов последовательности равных соответствен но 4, 1 Ч различные целые числа от 1 до 7. Значение каждого элемента показывает его место в сортированном спис ке <...< где определяются в цикле for 1 to = Сложность данного метода сортировки является линейной где п = значения а, определяют перестановку л = которая упорядочивает элементы Значения устанавливаются в цикле for to 7 =/'.

5.7. Сортировка с вычисляемыми адресами Сортировка стала возможной благодаря тому, что значения исходных данных 6, 3, 5, 7, 2, 4, 1 заполняют сплошной интервал последовательности натуральных чисел. Рассмотрим обобщение идеи сортировки с вычисляемыми адресами на случай произволь ных целых Алгоритм сортировки существенно упро щается, если все значения различные.

Значения Ч различные Реализация метода сортировки представлена в алгоритме 5.9.

Временный массив где и s = используется для сортированной упаковки элементов Свободные места в массиве инициализируются значением s + 1, отличным от значений эле ментов flj, Алгоритм 5.9. Сортировка с вычисляемыми адресами для различных и max значений среди } r = s = for i = 2 to do begin then else < then s = end;

значением отличным от for i 1;

упаковка элементов } for i = 1 to n do сортированных из k = for to s do begin 1 then begin k = = end;

end.

Сортированный вектор <...< является результатом последовательного просмотра массива удалении из него оставшихся незанятыми элементов, равных значению Глава 5. Сортировка и поиск s + 1. Алгоритм не содержит вложенных циклов, а значит, слож ность его линейная Допускаются одинаковые значения среди яД Реализация метода представлена в алгоритме Наличие одинаковых элементов среди например, = при = ведет к потере данных в исходном мно жестве flj, Ситуация, когда одновременно несколько эле ментов претендуют на одно место, называется коллизией. Такие элементы необходимо переразмещать на свободные места, сохра няя свойства сортировки с вычисляемыми адресами. С этой це лью на основании величин рассчитывается вектор ин дексов сортированной упаковки данных в массиве В алгоритме 5.9 роль индексов упаковки могли выполнять непосредственно сами значения элементов так как они были различные. В данном случае значения таким образом, что одинаковые по ве личине элементы из оказываются смежными при их упаковке в массиве Вектор используется для подсчета количества элементов каждого значения среди flj, формирования индексов упаковки Алгоритм 5.10. Сортировка с вычисляемыми адресами для и max значений среди аД } r s for i - 2 to n do begin then else ifs < then s = элементов каждого значения for i = r to s do = 0;

for i = 1 to n do +1;

индексов упаковки } for = to s do = flf,._! + упаковка элементов в for i = 1 to n do begin k = 5.7. Сортировка с вычисляемыми адресами _ end.

Результирующий сортированный исходных данных располагается в массиве... Алгоритм не со держит вложенных циклов, а значит сложность его линейная Сортировка с вычисляемыми адресами является очень быст рым методом, но она может быть крайне неэффективной при бо льших значениях s - точки зрения использования оперативной памяти, необходимой для хранения временных массивов данных и Введение в теорию графов.

Алгоритмы на графах самых разнообразных задач естественно форму лируется в терминах точек и связей между ними, т.е. в терминах графов. Так, например, могут быть сформулированы задачи со ставления расписания, анализа сетей в электротехнике, анализа цепей Маркова в теории вероятностей, в программировании, в проектировании электронных схем, в экономике, в социологии и т.д. Поэтому эффективные алгоритмы решения задач теории гра фов имеют большое практическое значение.

Основные понятия и определения Х Определение. Конечным графом называется тройка U, множество вершин;

UЧ конеч ное множество ребер (дуг);

Ф Ч отношение инцидентности;

Отношение инцидентности Ф является трехмест ным отношением и, у), где х, у X, и е U, которое может либо выполняться (быть истинным), либо не выполняться (быть ложным) и удовлетворяет свойствам:

1) е U Зх,у и, у) Ч ребро всегда соединяет пару вершин.

и, = = ребро и соответствует не более чем одной паре вершин х, у.

Х представление графов.

Элементы графов Геометрические элементы 1. х е вершина. 1. Х Ч точка в пространстве.

2. и, х) Ч 2. направленный отрезок.

ориентированное ребро, дуга.

3.

3. и, у) л и, х) - Ч отрезок.

неориентированное ребро.

4. и, х) Ч петля. 4. Ч замкнутый отрезок.

Основные понятия и определения Рис. Графы с тремя вершинами и двумя ребрами Х Определение. = и = называются изоморфными если существуют два взаимно одно значных соответствия : и : сохраняющие отношение инцидентности: = Из определения следует, что изоморфные графы можно оди наково изображать графически и отличаться они будут только метками вершин (рис. 6.2).

Рис. 6.2. Три изоморфных графа Определение. Граф называется ориентированным если каждое его ребро ориентировано: U и, у) и, Иногда удобно преобразовать неори ентированный граф в ориентированный Ч заменой каждого неориентированного ребра парой ориентированных ребер с противоположной ориентацией.

Определение. Подграфом графа (X, U, называется такой граф Ф), что Обозначают с Г.

Определение. Граф называется псевдографом, если в нем допус каются петли и кратные ребра, т. е. две вершины могут быть соединены более чем одним ребром. Псевдограф без петель называется (рис. 6.3).

Рис. 6.3. Псевдограф (слева) и (справа) 112 Глава 6. Введение в теорию графов. Алгоритмы на графах Определение. Неориентированный граф называется простым, если он не имеет петель и любая пара вершин соединена не бо лее чем одним ребром.

Определение. Простой граф называется полным, если каждая пара вершин соединена ребром. Такой граф с вершинами со держит ребер (рис. 6.4).

Рис. 6.4. Полные неориентированные графы Определение. Дополнением простого графа граф имеющий те же вершины, а его ребра являются дополнени ем до полного графа (рис. 6.5).

Рис. 6.5. Исходный граф Г и дополнительный Г Определение. Граф называется плоским если он может быть изображен на плоскости так, что все пересечения ребер являются его вершинами.

Рис. 6.6. Граф Ч плоский, а граф Ч неплоский Определение. Если х у соединены ребром и, то гово рят, что вершины х, у смежные, а ребро и инцидентно верши нам х и у. Два ребра называются смежными, если они имеют общую вершину.

Определение. Степенью вершины графа называется количест во ребер, инцидентных данной вершине. Вершина графа, име ющая степень 0, называется изолированной, а если степень ее равна 1, то такая вершина называется висячей.

Основные понятия и определения Определение. Граф называется помеченным (или перенумеро ванным), если его вершины отличаются друг от друга каки ми-либо пометками (рис. 6.7).

х, Рис. 6.7. Граф Ч помеченный, а граф Ч непомеченный Определение. Путь (маршрут) на графе (X, U, Ф) определя ется последовательностью вершин и ребер где X, е U. Ребро соединяет вершину с вершиной т.е. выполняется отношение инцидентности Х Маршрут называется цепью, если все его ребра различные.

Х Маршрут называется замкнутым, если = Х Замкнутая цепь называется циклом.

Х Цепь называется простой, если не содержит одинаковых вершин.

Х Простая замкнутая цепь называется простым циклом.

Х цепью называется простая цепь, содержащая все вершины графа.

Х циклом называется простой цикл, содержа щий все вершины графа.

Pages:     | 1 | 2 | 3 |    Книги, научные публикации