:: алгоритмы  и методы :: :: олимпиадные задачи :: :: связь :: :: о сайте ::
Путь: Математика » Комбинаторика и перебор
  Комбинаторика и переборные задачи




Методы программрования: переборные алгоритмы
Описано, как создавать подобные программы. Доступно, и даны основные приемы..

Задача о рюкзаке z i p
Дано n целых ai>0 и целое S>0. Нужно найти подмножество ai, сумме которого равна S или показать, что такого нет.

Hапечатать все последовательности длины N из чисел 1,2..M

Подсчитать количество слов длины К из данных N букв, не содержащих данное подслово

Hапечатать все перестановки чисел 1..N

Сгенерировать все подмножества данного n-элементного множества {0,.., n-1}

Дана строка S и набор A слов А[1],.. , A[k]. Разбить строку S на слова набора всеми возможными способами

Перечислить все разбиения N на целые положительные слагаемые

Перечислить все различные представление числа N в виде всевозможных произведений (сумм) K натуральных чисел

У продавца и покупателя имеется неограниченное кол-во монет достоинством (1,2,5,10,20,50,100,200,500 к примеру). Покупатель купил товар на сумму n. Hужно найти минимальное кол-во монет, которые будут использованы при расплате. Деньги может давать как покупатель, так и продавец

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

A Story about the N-Queens Problem: From Exponential to (Almost) Constant Time
Перечислить все расстановки n ферзей на шахматной доске размера NxN, при которых никакие два не бьют друг друга. Намного более продвинутые методы, нежели в статье выше.

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

Ханойские башни

Информацию по решению конкретных задач этой области также можно найти в разделах
Олимпиадные задачи: переборные задачи
Олимпиадные задачи: рекуррентные соотношения и динамическое программирование


  Дополнительные материалы:




В. Липский "Введение в комбинаторику" z i p
Алгоритмы комбинаторики, немного алгоритмов на графах и матроиды.