Школа179 : Oner Xaum / Комбин

Это старая версия OnerXaum/Комбин за 2013-10-07 01:20:08..

Порождение комбинаторных объектов

Решения задач на порождение комбинаторных объектов в своей основе имеют одну и ту же схему, которая предполагает ответ на следующие вопросы:

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

Примечание: вопросы 2 и 4, как правило, решаются крайне легко

Сама же процедура порождения всех комбинаций обычно имеет следующий вид:

В задачах этого листка:

Использование вышеописанной процедуры и, таким образом, всех ее подпрограмм обязательно.
Рекурсия запрещена.
Для хранения комбинаций используется глобальный массив и соответствующие константы; данные с клавиатуры не вводятся.
Время выполнения процедуры получитьСледующуюКомбинацию, по умолчанию не более C_n.

Задачи

07_01a (начальная)
Напечатать все последовательности длины n из чисел 0.. k-1 в лексикографическом порядке

07_01b (базовая)
Напечатать все последовательности длины n из чисел 0.. k-1 в обратном лексикографическом порядке

07_01c
Напечатать все последовательности длины n у которых i-ый член не превосходит i.
(базовая)

07_01d
Напечатать все последовательности длины n из чисел 0.. k-1 так, чтобы соседние последовательности (а также первая и последняя) отличались бы только в одной позиции и только на единицу.
(средняя)

07_02.c
Напечатать все подмножества множества 1 .. k.
(средняя)

07_01a.c
Напечатать все перестановки чисел 1 .. n. (то есть последовательности длины n, в которые каждое из этих чисел входит по одному разу).
(сложная)

07_01d.c То же, так, чтобы соседние последовательности (а также первая и последняя) получались бы друг из друга обменом лишь двух элементов

4. Перечислить все возрастающие последовательности длины k из чисел 1 .. n в лексикографическом порядке.

пример: при n=5, k=2 получаем 12 13 14 15 23 24 25 34 35 45)

a. Перечислить все разбиения целого положительного числа n на целые положительные слагаемые (разбиения, отличающиеся лишь порядком слагаемых, считаются за одно). разбиения представляются как невозрастающие последовательности, порядок перечисления – лексикографический.

пример: для n = 4, разбиения 1+1+1+1, 2+1+1, 2+2, 3+1, 4.)

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

пример: для n = 4, должно быть 4, 3+1, 2+2, 2+1+1, 1+1+1+1).

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

пример: для n = 4: 1+1+1+1, 1+1+2, 1+3, 2+2, 4;

6. Перечислить все вложения (т. е. функции, переводящие разные элементы в разные) множества {1..k} в {1..n}, где k не превышает n.

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

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

пример: для n = 4 существует 5 расстановок:

((a...b)..c)..d
.(a..(b...c)).d
.(a...b).(c...d)
..a.((b...c)..d)
..a..(b..(c...d))

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

10. Перечислить все способы разрезать выпуклый n–угольник на треугольники, проведя n–3 его диагонали.

Школа179: Oner Xaum/Комбин ...

Порождение комбинаторных объектов

Задачи