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

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

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


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


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

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


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


процедура получитьВсеКомбинации
| получитьПервуюКомбинацию
| вывести Комбинацию
| пока не текущаяКомбинацияПоследняя выполнять
| | получитьСледующуюКомбинацию
| | вывести Комбинацию
| конецЦикла
|конецПроцедуры



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



Задачи


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)

5.

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 расстановок:


  1. ((a...b)..c)..d
  2. .(a..(b...c)).d
  3. .(a...b).(c...d)
  4. ..a.((b...c)..d)
  5. ..a..(b..(c...d))

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


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


 
Файлов нет.[Показать файлы/форму]