- •Часть 1. Курс лекций
- •Введение.
- •Цели освоения дисциплины
- •Место дисциплины в структуре ооп впо
- •Компетенции обучающегося, формируемые в результате освоения дисциплины (модуля)
- •Тема 1. Алгоритмы на графах (6 часов).
- •Лекция 1. Начальные понятия теории графов.
- •Определение графа
- •Графы и бинарные отношения
- •Откуда берутся графы
- •Число графов
- •Смежность, инцидентность, степени
- •Некоторые специальные графы
- •Графы и матрицы
- •Взвешенные графы
- •Изоморфизм
- •Инварианты
- •Операции над графами
- •Локальные операции
- •Подграфы
- •Алгебраические операции
- •Лекция 2. Поиск в глубину и ширину. Поиск в ширину
- •Процедура поиска в ширину
- •Процедура поиска в глубину
- •Глубинная нумерация
- •Построение каркаса
- •Шарниры
- •Маршруты, пути, циклы
- •Связность и компоненты
- •Метрические характеристики графов
- •Маршруты и связность в орграфах
- •Эйлеровы пути и циклы
- •Построение эйлерова цикла
- •Гамильтоновы пути и циклы
- •Тема 2. Алгоритмы комбинаторного перебора (6 часов).
- •Размещения с повторениями
- •Перестановки
- •Подмножества
- •Разбиения
- •Лекция 5. Коды Грея. Коды Грея и аналогичные задачи
- •Лекция 6. Применение методов комбинаторного перебора.
- •Подсчет количеств
- •Тема 3. Общие методы разработки алгоритмов (6 часов).
- •Ферзи, не бьющие друг друга: обход дерева позиций
- •Лекция 8. Рекурсия. Примеры рекурсивных программ
- •Рекурсивная обработка деревьев
- •Лекция 9. Построение итеративных алгоритмов по рекурсивным.
- •Стек отложенных заданий
- •Более сложные случаи рекурсии
- •Библиографический список
- •Содержание
- •Тема 1. Алгоритмы на графах. 6
- •Тема 2. Алгоритмы комбинаторного перебора. 48
- •Тема 3. Общие методы разработки алгоритмов. 66
- •Шутов Антон Владимирович Медведев Юрий Алексеевич
- •600014, Г. Владимир, ул. Университетская, 2, тел. 33-87-40
Подсчет количеств
Иногда можно найти количество объектов с тем или иным свойством, не перечисляя их. Классический пример: - число всех -элементных подмножеств -элементного множества - можно найти, заполняя таблицу по формулам
или по формуле
(Первый способ эффективнее, если надо вычислить много значений .)
Приведем другие примеры.
Число разбиений; предлагалась на Всесоюзной олимпиаде по программированию 1988 года. Пусть - число разбиений целого положительного на целые положительные слагаемые (без учета порядка, и - одно и то же разбиение). При положим (единственное разбиение не содержит слагаемых). Построить алгоритм вычисления для заданного .
Решение. Можно доказать (это нетривиально) такую формулу для :
(знаки у пар членов чередуются, вычитаемые в одной паре равны и ; сумма конечна - мы считаем, что при ).
Однако и без ее использования можно придумать способ вычисления , который существенно эффективнее перебора и подсчета всех разбиений.
Обозначим через (для , ) число разбиений на целые положительные слагаемые, не превосходящие . (При этом считаем равным для всех .) Очевидно, . Все разбиения на слагаемые, не превосходящие , разобьем на группы в зависимости от максимального слагаемого (обозначим его ). Число равно сумме (по всем от до ) количеств разбиений со слагаемыми не больше и максимальным слагаемым, равным . А разбиения на слагаемые не более с первым слагаемым, равным , по существу представляют собой разбиения на слагаемые, не превосходящие (при ). Так что
что позволяет заполнять таблицу значений функции .
Счастливые билеты; предлагалась на Всесоюзной олимпиаде по программированию 1989 года. Последовательность из цифр (каждая цифра от до ) называется счастливым билетом, если сумма первых цифр равна сумме последних цифр. Найти число счастливых последовательностей данной длины.
Решение. (Сообщено одним из участников олимпиады; к сожалению, не могу указать фамилию, так как работы проверялись зашифрованными.) Рассмотрим более общую задачу: найти число последовательностей, где разница между суммой первых цифр и суммой последних цифр равна ( ). Пусть - число таких последовательностей.
Разобьем множество таких последовательностей на классы в зависимости от разницы между первой и последней цифрами. Если эта разница равна , то разница между суммами групп из оставшихся цифр равна . Учитывая, что пар цифр с разностью бывает , получаем формулу
(Некоторые слагаемые могут отсутствовать, так как может быть слишком велико.)
В некоторых случаях ответ удается получить в виде явной формулы.
Доказать, что число Каталана (количество последовательностей длины из единиц и минус единиц, в любом начальном отрезке которых не меньше единиц, чем минус единиц) равно .
Указание. Число Каталана есть число ломаных, идущих из в шагами и , не опускающихся в нижнюю полуплоскость, т.е. разность числа всех ломаных (которое есть ) и числа ломаных, опускающихся в нижнюю полуплоскость. Последние можно описать также как ломаные, пересекающие прямую . Отразив их кусок справа от самой правой точки пересечения относительно указанной прямой, мы установим взаимно однозначное соответствие между ними и ломаными из в . Остается проверить, что .