|
||||||||||||||
МИОО, МЦНМО, Оргкомитет Московской олимпиады по информатике
Дистанционные семинары
по подготовке к олимпиадам по информатике
Занятие 17. Комбинаторика - 3. Генерация объекта по номеру и номера по объекту.
Комбинаторика изучает множества однотипных объектов. Объекты в таком множестве можно упорядочить по некоторому признаку и затем занумеровать. Возникает задача определения объекта по его номеру и номера по объекту. Рассмотрим способ решения этой задачи на примере перестановок фиксированной длины N.
В качестве способа упорядочивания возьмем лексикографический (пример лексикографического порядка перестановок длины 3: (1,2,3), (1,3,2), (2,1,3), (2,3,1), (3,1,2), (3,2,1)). Сначала научимся определять перестановку по номеру. Для этого научимся отвечать на вопрос: "Сколько существует объектов с заданным началом?" Для перестановок ответ прост: (N-k)!, где k - длина префикса. Будем перебирать все префиксы длины 1 в лексикографическом порядке. Как только сумма количества перестановок с такими префиксами станет не меньше номера, начинаем перебирать все префиксы длины два, полученные продолжением последнего префикса длины один, и так далее. Обратная задача решается аналогично: перебираем все префиксы длины один, меньшие соответствующего префикса нашей перестановки, затем длины два, полученные продолжением префикса длины один нашей перестановки и т.д. Сумма по всем перебранным префиксам будет на 1 меньше номера перестановки.
Прочие задачи генерации номера по объекту и объекта по номеру решаются аналогично: мы последовательно строим объект, перебирая все возможные начала. Самой сложной частью, как правило, являлется определение количества объектов с заданным префиксом. Если явной формулы не существует, приходится прибегать к динамическому программированию.
| Задача 17-1. По номеру! |
| Задача 17-2. По размещению! |
| Задача 17-3. Гладкие числа. |
| Задача 17-4. Следующая... |