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

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

Упражнения

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

По данному натуральному \(n\leqslant 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\leqslant k \leqslant 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\leqslant 20\) выведите все двоичные последовательности длины \(n\), не содержащие двух единиц подряд,
в лексикографическом порядке.






Ввод
Вывод





3


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








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



По данным натуральным \(n\) и \(k\) (\(0 \leqslant k \leqslant 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\leqslant k \leqslant n\), \(n\geqslant 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\leqslant k \leqslant n\), \(n \geqslant 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\leqslant k \leqslant \lceil\frac{n}{2}\rceil\), \(n \geqslant 1\)) выведите 
в лексикографическом порядке все двоичные строки длины \(n\)
содержащие \(k\) единиц и не содержащие двух единиц подряд.






Ввод
Вывод





4 2


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








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



По данным натуральным \(n\) и \(k\) (\(n \leqslant 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 \leqslant k\)) выведите все убывающие последовательности длины \(n\),
состоящие из чисел \(1, \ldots, 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\leqslant k \leqslant 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\leqslant k \leqslant 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\), которые необходимо вывести (\(n k \leqslant 10^6\)).
Затем идет строка из 6 символов, являющаяся некоторой перестановкой строки "()[]{}", задающая лексикографический порядок.


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






Ввод
Вывод





3 10
[}{)](


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









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



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


Дано натуральное \(n\leqslant 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\le10\). Далее
идет \(n\) пар действительных чисел: координаты точек.


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






Ввод
Вывод





4
0 0
1 0
1 1
2 1


4.82842712474619










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



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


    Делать отсечение, если суммарная длина текущего маршрута больше или равна наилучшему
    известному замкнутому маршруту (т.е. заведомо не удастся улучшить результат).




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



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


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




ZE: Пятнашки



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




    
  1  2  3  4 

    
  5  6  7  8 

    
  9 10 11 12 

    
 13 14 15   






Вам дана некоторое начальное положение головоломки. Известно,
что ее можно решить не более, чем за 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 перемещений.