Решение проблемы «без трещин»

Question

Вот формулировка проблемы: рассмотрим проблему строительства стены из кирпичей 2x1 и 3x1 (горизонтальные × вертикальные размеры), чтобы при дополнительной прочности зазоры между горизонтально смежными кирпичами никогда не выстраивались в последовательные слои, то есть никогдаобразуют «бегущую трещину».

Существует восемь способов образования стены без трещин размером 9х3, обозначенной W (9,3) = 8.

Рассчитать W (32,10).<Обобщите его для W (x, y)>

http://www.careercup.com/question?id=67814&form=comments

Приведенная выше ссылка дает несколько решений, но я не могу понять логику, стоящую за ними .. IЯ пытаюсь закодировать это в Perl и до сих пор:

input : W(x,y)
find all possible i's and j's such that x == 3(i) + 2(j);
for each pair (i,j) ,
find n = (i+j)C(j)            # C:combinations

Добавление всех этих n должно дать счет всех возможных комбинаций.Но я понятия не имею, как найти реальные комбинации для одного ряда и как двигаться дальше .. Pl help ..

Answer 1

Основываясь на утверждении, что W (9,3) = 8, я делаю вывод, что «бегущая трещина» означает любую непрерывную вертикальную трещину высотой два или более. Прежде чем заняться поставленной двумерной проблемой, я хочу обсудить аналогичную одномерную проблему и ее решение. Я надеюсь, что это сделает более понятным, как двумерная проблема воспринимается как одномерная и в конечном итоге решается.

Предположим, вы хотите посчитать количество списков длиной, скажем, 40, чьи символы взяты из достаточно небольшого набора, скажем, пяти символов {a, b, c, d, e}. Конечно, есть 5 ^ 40 таких списков. Если мы добавим дополнительное ограничение на то, что никакая буква не может появляться дважды подряд, математическое решение все равно будет простым: существует 5 * 4 ^ 39 списков без повторяющихся символов. Однако, если мы вместо этого хотим запретить использование согласных комбинаций, таких как bc, cb, bd и т. Д., То все становится сложнее. Конечно, мы хотели бы подсчитать количество способов выбора первого символа, второго и т. Д. И умножить их, но количество способов выбора второго символа зависит от выбора первого и т. Д. Эта новая проблема достаточно сложна, чтобы проиллюстрировать правильную технику. (хотя и не достаточно сложно, чтобы сделать его полностью устойчивым к математическим методам!)

Чтобы решить проблему списков длиной 40 без согласных комбинаций (назовем это f (40)), мы могли бы представить себе использование рекурсии. Можете ли вы рассчитать F (40) в терминах F (39)? Нет, потому что некоторые списки длиной 39 заканчиваются согласными, а некоторые заканчиваются гласными, и мы не знаем, сколько у нас каждого типа. Таким образом, вместо вычисления для каждой длины n <= 40 f (n) мы вычисляем для каждого n и для каждого символа k f (n, k) количество списков длины n, заканчивающихся на k. Хотя f (40) не может быть рассчитывается только по f (39), f (40, a) может быть вычислено по f (30, a), f (39, b) и т. д. </p>

Описанная выше стратегия может быть использована для решения вашей двумерной задачи. Вместо символов у вас есть целые горизонтальные кирпичные ряды длиной 32 (или х). Вместо 40 у вас есть 10 (или у). Вместо ограничения без консонансных комбинаций у вас есть ограничение без смежных трещин.

Вы конкретно спрашиваете, как перечислить все кирпичные строки заданной длины, и вы правы, что это необходимо, по крайней мере, для этого подхода. Сначала решите, как будет представлен ряд. Ясно, что достаточно указать местоположения 3-кубиков, и, поскольку у каждого есть четко определенный центр, представляется естественным дать список местоположений центров 3-кубиков. Например, при длине стены 15 последовательность (1,8,11) будет описывать строку следующим образом: (ooo | oo | oo | ooo | ooo | oo). Этот список должен удовлетворять некоторым естественным ограничениям:

1. Начальная и конечная позиции не могут быть центрами 3-кубика. Выше 0 и 14 являются недействительными записями.
2. Последовательные различия между числами в последовательности должны быть нечетными и не менее трех.
3. Позиция первой записи должна быть нечетной.
4. Разница между последней записью и длиной списка также должна быть нечетной.

Существуют различные способы вычисления и хранения всех таких списков, но концептуально самым простым является рекурсия по длине стены, игнорируя условие 4, пока вы не закончите. Создайте таблицу всех списков для стен длиной 2, 3 и 4 вручную, затем для каждого n выведите таблицу всех списков, описывающих стены длины n, из предыдущих значений. Когда вы закончите, наложите условие 4, потому что это не очень хорошо с рекурсией.

Вам также понадобится способ, для любого кирпичного ряда S, чтобы быстро описать все кирпичные ряды S ', которые могут по закону находиться под ним. Для простоты предположим, что длина стены составляет 32. Немного подумать должно убедить вас, что

1. S 'должен удовлетворять тем же ограничениям, что и S, приведенный выше.
2. 1 находится в S 'тогда и только тогда, когда 1 не в S.
3. 30 в S ', если и только если 30 не в S.
4. Для каждой записи q в S, S 'должна иметь соответствующую запись q + 1 или q-1, и наоборот, каждый элемент из S' должен быть q-1 или q + 1 для некоторого элемента q в S.

Например, список (1,8,11) может быть юридически размещен поверх (7,10,30), (7,12,30) или (9,12,30), но не (9,10,30), поскольку это не удовлетворяет условию «по крайней мере три».Основываясь на этом описании, нетрудно написать цикл, который вычисляет возможных преемников данной строки.

Теперь мы собрали все вместе:

Сначала, для фиксированного x, создайте таблицу всех допустимых строк длины x.Затем напишите функцию W (y, S), которая должна вычислить (рекурсивно) число стен шириной x, высотой y и верхней строкой S. Для y = 1, W (y, S) = 1.В противном случае W (y, S) представляет собой сумму по всем S ', которая может быть связана с S, как указано выше, со значениями W (y-1, S').

Это решение достаточно эффективно для решенияпроблема W (32,10), но потерпит неудачу при большом x.Например, W (100,10) почти наверняка будет невозможно рассчитать, как я описал.Если бы x было большим, но y было маленьким, мы бы нарушили все разумные правила укладки кирпича и считали, что стена строится слева направо, а не снизу вверх.Это потребует описания действительного столбца стены.Например, описание столбца может быть списком, длина которого равна высоте стены, и записи которого находятся среди пяти символов, представляющих «первый квадрат кирпича 2x1», «второй квадрат кирпича 2x1», «первый квадрат кирпича».Кирпичи 3x1 "и т. Д. Конечно, будут ограничения на описание каждого столбца и ограничения, описывающие взаимосвязь между последовательными столбцами, но тот же подход, что и выше, будет работать и в этом случае и будет более подходящим для длинных коротких стен.1041 *