По личному опыту, могу сказать, что довольно популярными на собеседованиях являются задачи, так или иначе связанные с покрытиями доминошками каких-либо поверхностей. Условия могут варьироваться, но суть у всех остается одна.
Пример 1.
Имеется шахматная доска 8 на 8 клеток, левый нижний и правый верхний углы которой отрезаны.
Можно ли полностью покрыть такую доску доминошками размера 2×1 клетку?
На доске остается четное число клеток (62), так что на первый взгляд решение возможно. Однако, давайте сделаем одну очень простую вещь:
Мы раскрасили клетки через одну. Теперь все становится очевидным. Каждая доминошка может занимать строго две клетки: одну белую и одну черную. Других вариантов не дано. Смотрим, какие клетки на доске отрезаны – обе черные, соответственно мы имеем 32 белых и 30 черных клеткок и полностью покрыть такую доску не представляется возможным.
Условия задачи могут варьироваться, но в целом, задачи на возможность-невозможность сразу бросаются в глаза.
Пример 2.
Имеется большой куб сыра 3x3x3 состоящий из 27 одинаковых кубиков сыра и мышонок, который съедая один кубик принимается за соседний с ним по грани кубик сыра. Сможет ли мышонок полностью съесть весь сыр, если центральный кубик заменить на несъедобный муляж?
Задача та же самая, только в пространстве, а не на плоскости. Считаем клеточки: в изначальном раскладе это 14 на 13, после удаления центрального кубика: 14 на 12 и как следствие, решения нет.
Следующими по популярности идут задачи на подсчет количества вариантов решений.
Пример 3.
Даны две доски:
На каждой вырезано по 2 клетке. Количество вариантов покрытия доминошками какой из досок больше? В обоих случаях вырезаны клетки разного цвета, так что все познания с раскраской из предыдущих примеров нам здесь не помогут. Времени на собеседованиях на задачи отводится мало, так что нужно искать какую-то зацепку. А она есть. Исключим из первого варианта все покрытия содержащие вырезанные клетки второй доски, а из второго варианта – первой. (Если так проще представить – то можно считать, что вырезанные клетки изначально покрыты доминошкой – которую нельзя двигать, и, очевидно, что таким образом мы приводим доски к идентичному состоянию и количество вариантов покрытий будет тоже идентичным). После этого рассмотрим нижний угол 3 на 2 клетки. Во втором варианте, левая нижняя клетка может быть покрыта только одним способом. Сопоставим этому покрытию вариант для первой доски:
Оставшася часть за исключением этого угла идентична, соответственно и количество покрытий тоже идентично. Таким образом, каждому варианту покрытия второй доски, сопоставлен вариант покрытия первой доски. Однако в первом случае также еще возможен вариант, где все доминошки расположены вертикально, не соответветсвующий ни одному варианту второй доски. Следовательно, число вариантов покрытия доски с клетками, отрезанными в углу больше.
Пример 4.
Найти количество вариантов покрытия доминошками доски 2хN клеток.
Пусть ее можно покрыть X(N) способов. Рассмотрим вариант покрытия левой верхней клетки:
Оставшуюся часть в первом случае можно покрыть X(N-1) способами, а во втором, очевидно, X(N-2).
Так как перечислены все варианты покрытия и никакие из них не будут совпадать, то получаем уравнение X(N) = X(N-1) + X(N-2)
X(1) = 1, X(2) = 2, а Х(N) будет равно N+1 числу последовательности Фибоначчи.
Пример 5.
Написать программу, вычисляющую количество способов покрытия доски 3xN клеток доминошками.
Сразу скажу, возможно, для этого примера есть тоже оптимальное решение, но я перейду тут уже от частных решений к общему. По сути, все что стоит за такими задачами можно представить двудольным графом, одно из множеств вершин которого – черные клетки, а другое – белые. Покрытие доминошками – есть не что иное как максимальное паросочетание такого графа. Для его поиска могут применяться различные алгоритмы (например Куна), с подсчетом количества вариантов все несколько сложнее. В любом случае, это за пределами данной статьи.
В заключение, для демонстрации, реализация алгоритма “в лоб” на питоне:
from itertools import combinations # формирование матрици инцидентности опущено для краткости # оно тривиально # Например, для доски 2x2 с номерами клеток: # 1 2 # 3 4 # это: # mat = [ # [0, 1, 1, 0], # [0, 0, 0, 1], # [0, 0, 0, 1], # [0, 0, 0, 0] #] # 1 => 2, 1 => 3, 2 => 4, 3 => 4 # Обратные направления ( напр. 3 => 1 ) # не представляют для нас интереса N = len(mat) # создаем итератор со всеми парами вершин all_edges = combinations(xrange(N), 2) # фильтруем по матрице инцидентности edges = [(x,y) for x,y in all_edges if mat[x][y]] # отфильтровываем все максимальные варианты matchings = [tuples for tuples in combinations(edges, N/2) \ if len(set(reduce(lambda x, y: x+y, tuples))) == N] print len(matchings) # осторожно, сложность O(N!) |
Пример 3.
<<Однако в первом случае также еще возможен вариант, где все <<доминошки расположены вертикально,
Это какой случай? Объясните плз, никак не доходит 🙁
Это так:
