Решение комбинаторных задач

Методические указания

В.А. Петухин

1 Понятие комбинаторной задачи
1.1 Процесс решения задачи
1.2 Понятие комбинаторной задачи
1.3 Пространство перебора
1.4 Как избежать перебора
2 Сокращение перебора
2.1 Отсечение лишних вариантов
2.2 Использование симметрии
2.3 Группирование элементов
3 Перебор с возвратом
3.1 Использование рекурсии для записи алгоритма
3.2 Примеры решения задач при помощи перебора с возвратом
3.3 Возврат
4 Перебор с распостранением ограничений
4.1 Распостранение ограничений
4.2 Изменение порядка перебора
5 Задачи
6 Тексты программ на Паскале
7 Тексты программ на Бейсике

Файлы с исходным текстом программ и exe-файлы под DOS (zip-архив)


Аннотация.

Рассматриваются задачи по программированию решаемые с помощью перебора вариантов или избегающие перебор. Основная проблема для подобных задач – сокращение перебора. Описываются алгоритмы перебора с возвратом и перебора с распостранением ограничений. Приводятся тексты программ на языках Паскаль и Бейсик.

Методические указания предназначены для школьников и преподавателей информатики.


Первая часть