Рекурсивный перебор комбинаторных объектов

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

Упражнения

A: Двоичные последовательности

По данному натуральному $n⩽10$ выведите все двоичные последовательности длины $n$ в лексикографическом порядке.

3

0 0 0
0 0 1
0 1 0
0 1 1
1 0 0
1 0 1
1 1 0
1 1 1

B: $k$-ичные последовательности

По данным натуральным $n$ и $k$ ($2⩽k⩽10$) выведите все последовательности длины $n$, составленные из символов $0,...,k-1$ в лексикографическом порядке.

Пример

2 3

0 0
0 1
0 2
1 0
1 1
1 2
2 0
2 1
2 2

C: Двоичные последовательности без двух единиц подряд

По данному натуральному $n⩽20$ выведите все двоичные последовательности длины $n$, не содержащие двух единиц подряд, в лексикографическом порядке.

3

0 0 0
0 0 1
0 1 0
1 0 0
1 0 1

D: Двоичные последовательности длины $n$ содержащие не более $k$ единиц

По данным натуральным $n$ и $k$ ($0⩽k⩽n$) выведите все двоичные последовательности длины $n$, содержащие не более $k$ единиц в лексикографическом порядке.

4 2

0 0 0 0
0 0 0 1
0 0 1 0 
0 0 1 1
0 1 0 0 
0 1 0 1
0 1 1 0
1 0 0 0
1 0 0 1
1 0 1 0
1 1 0 0

E: Двоичные последовательности длины $n$ содержащие $k$ единиц

По данным натуральным $n$ и $k$ ($0⩽k⩽n$, $n⩾1$) выведите все двоичные последовательности длины $n$, содержащие ровно $k$ единиц в лексикографическом порядке.

4 2

0 0 1 1
0 1 0 1
0 1 1 0
1 0 0 1
1 0 1 0
1 1 0 0

F: Двоичные последовательности длины $n$ содержащие не более $k$ единиц без двух единиц подряд

По данным натуральным $n$ и $k$ ($0⩽k⩽n$, $n⩾1$) выведите в лексикографическом порядке все двоичные строки длины $n$ содержащие не более $k$ единиц и не содержащие двух единиц подряд.

4 2

0 0 0 0
0 0 0 1
0 0 1 0
0 1 0 0 
0 1 0 1
1 0 0 0
1 0 0 1
1 0 1 0

G: Двоичные последовательности длины $n$ содержащие $k$ единиц без двух единиц подряд

По данным натуральным $n$ и $k$ ($0⩽k⩽\lceil \frac{n}{2}\rceil$, $n⩾1$) выведите в лексикографическом порядке все двоичные строки длины $n$ содержащие $k$ единиц и не содержащие двух единиц подряд.

4 2

0 1 0 1
1 0 0 1
1 0 1 0

H: Возрастающие последовательности

По данным натуральным $n$ и $k$ ($n⩽k$) выведите все возрастающие последовательности длины $n$, состоящие из чисел $1,...,k$.

3 5

1 2 3
1 2 4
1 2 5
1 3 4
1 3 5
1 4 5
2 3 4
2 3 5
2 4 5
3 4 5

I: Убывающие последовательности

По данным натуральным $n$ и $k$ ($n⩽k$) выведите все убывающие последовательности длины $n$, состоящие из чисел $1,\dots ,k$ в обратном лексикографическом порядке.

3 5

5 4 3
5 4 2
5 4 1
5 3 2
5 3 1
5 2 1
4 3 2
4 3 1
4 2 1
3 2 1

J: Разбиение на невозрастающие слагаемые

Дано натуральное число $n$. Выведите всевозможные его разбиения на слагаемые, упорядоченные в порядке невозрастания. Сами разбиения необходимо выводить в лексикографическом порядке.

5

1 1 1 1 1
2 1 1 1
2 2 1
3 1 1
3 2
4 1
5

K: Разбиение на неубывающие слагаемые

Дано натуральное число $n$. Выведите всевозможные его разбиения на слагаемые, упорядоченные в порядке неубывания. Сами разбиения необходимо выводить в лексикографическом порядке.

5

1 1 1 1 1
1 1 1 2
1 1 3
1 2 2
1 4
2 3
5

L: Разбиение на k невозрастающих слагаемых

Даны натуральные числа $n$ и $k$ ($1⩽k⩽n$). Выведите всевозможные разбиения числа $n$ на $k$ слагаемых, упорядоченных в порядке невозрастания. Сами разбиения необходимо выводить в лексикографическом порядке.

8 3

3 3 2
4 2 2
4 3 1
5 2 1
6 1 1

M: Разбиение на k неубывающих слагаемых

Даны натуральные числа $n$ и $k$ ($1⩽k⩽n$). Выведите всевозможные разбиения числа $n$ на $k$ слагаемых, упорядоченных в порядке неубывания. Сами разбиения необходимо выводить в лексикографическом порядке.

8 3

1 1 6
1 2 5
1 3 4
2 2 4
2 3 3

N: Перестановки

Дано натуральное число $n$. Выведите всевозможные перестановки чисел от 1 до $n$ в лексикографическом порядке.

3

1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1

O: Правильные скобочные последовательности

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

3

((()))
(()())
(())()
()(())
()()()

P: Правильные скобочные последовательности вложенности не более k

Даны натуральные числа $n$ и $k$. Выведите все правильные скобочные последовательности, состоящие из $n$ открывающихся круглых скобок и $n$ закрывающихся скобок так, что максимальная вложенность не превосходит $k$ в лексикографическом порядке.

4 2

(()()())
(()())()
(())(())
(())()()
()(()())
()(())()
()()(())
()()()()

Q: Правильные скобочные последовательности — 2

Дано натуральное числo $n$. Выведите все правильные скобочные последовательности, состоящие из $n$ открывающихся скобок и $n$ закрывающихся скобок в лексикографическом порядке. Используются круглые и квадратные скобки, их порядок следующий:

2

(())
()()
()[]
([])
[()]
[[]]
[]()
[][]

R: Правильные скобочные последовательности - 3

Дано натуральное числo $n$. Выведите k первых в лексикографическом порядке правильных скобочных последовательности, состоящих из $n$ открывающихся скобок и $n$ закрывающихся скобок в лексикографическом порядке. Используются круглые, квадратные и фигурные скобки. Лексикографичесчкий порядок для скобок задается в тестовых данных. Программа получает на вход число $n$ - количество открывающихся скобочек в исходной последовательности, количество правильных скобочных последовательностей $k$, которые необходимо вывести ($nk⩽{10}^6$). Затем идет строка из 6 символов, являющаяся некоторой перестановкой строки "()[]{}", задающая лексикографический порядок.

Гарантируется, что существует $k$ правильных последовательностей указанной длины.

3 10
[}{)](

[[[]]]
[[{}]]
[[][]]
[[]{}]
[[]][]
[[]]{}
[[]]()
[[]()]
[[()]]
[{[]}]

S: Расстановки ферзей

Известно, что на шахматной доске размером 8×8 можно расставить 8 ферзей не бьющих друг друга, причем сделать это можно 92 способами.

Дано натуральное $n⩽10$. Определите сколькими способами на доске $n\times n$ можно расставить n мирных ферзей.

8

92

T: Расстановки ферзей — 2

Решите предыдущую задачу, если расстановки ферзей, которые можно получить друг из друга поворотами и отражениями доски считать за одно.

8

12

ZA: Грузоподъемность - 2

Решите задачу “Грузоподъёмность” в ограничениях $n\le 23$. Используйте следующие оптимизации:

1. Отсортировать массы грузов по убыванию. Перебор начинать с более тяжелых грузов, сначала рассматриваем вариант, когда очередной груз берется.
2. Делается отсечение, если суммарная масса всех взятых грузов превышает вместимость машины.
3. Делается отсечение, если суммарная масса всех взятых грузов и всех оставшихся грузов меньше наилучшего уже найденного результата (т.е. если заведомо не удастся улучшить результат).
4. Для быстрого определения суммарной массы всех оставшихся грузов используется предподсчет.

Формат входных данных отличается от формата данных в первой задаче. Программа получает на вход действительное число $M$, затем количество ящиков $n\le 23$, затем $n$ действительных чисел: массы ящиков.

Программа должна вывести единственное число: максимальную массу, которую можно увезти на машине.

10
4
1
3
5
8

9.0

1073.15936137
5
359.840622077
640.476657457
63.7703847126
345.949354785
635.448660233

1064.0876642465998

ZB: Задача коммивояжера

На плоскости даны $n$ точек. Соедините их замкнутой ломаной линией минимальной длины.

Программа получает на вход число $n\le 10$. Далее идет $n$ пар действительных чисел: координаты точек.

Выведите одно действительное число: минимальную длину замкнутой ломаной, проходящей через все эти точки. Ответ выводите с точностью в 15 знаков.

4
0 0
1 0
1 1
2 1

4.82842712474619

ZC: Задача коммивояжера - 2

Решите задачу коммивояжёра в ограничениях $n\le 11$. Используйте следующую оптимизацию:

ZD: Задача коммивояжера - 3

Решите задачу коммивояжёра в ограничениях $n\le 12$. Используйте следующую оптимизацию:

ZE: Пятнашки

Головоломка “игра в пятнашки” состоит из 15 квадратиков, уложенные в рамку размером 4×4, при этом одно место остается незанятым. За один ход можно передвинуть один квадратик, соседний с незанятым местом, в незанятое место. Цель головоломки: упорядочить квадратики до такого положения:

Вам дана некоторое начальное положение головоломки. Известно, что ее можно решить не более, чем за 20 ходов. Найдите решение этой головоломки.

Программа получает на вход 4 строки, содержащие по 4 числа: значения, записанные на квадратиках в начальном расположение. Число 0 соответствует пустой клетке.

Программа должна вывести последовательность перемещений, решающих головоломку в виде строки из букв L, R, U, D решающую головоломку, где буква L соответствует движению квадратика с числом влево, R — вправо, U — вверх, D — вниз.

 1  2  3  4
 5  6  7  8
 9 10 15 11
13 14  0 12

DLU

ZF: Пятнашки - 2

В условиях предыдущей задачи найдите и выведите кратчайшее решение (т.е. решение содержащее наименьшее число перемещений). Гарантируется, что головоломку всегда можно решить не более чем за 20 перемещений.