Вопрос по algorithm – Количество комбинаций для 4xN домино

1

Я хочу найти количество возможных различных комбинаций для области размером 4 x N (4 единицы ширины и N единиц высоты, N & # x2265; 1) кирпичей доминоusing dynamic programming .

Кирпичи домино имеют размер 2х1, например.

==

для горизонтального и

|
|

для вертикального кирпича.

Сейчас,

Пример 4x1 (два кирпича домино под друг другом)

====

Примеры конфигурации кирпича 4х2 (всего 5)

1)

||||
||||

2) (поверните два кирпича справа)

||==
||==

3)

|==|
|==|

4)

====
====

5)

==||
==|| 

Количество уникальных комбинаций, известных к настоящему времени

4x1 : 1 possibility
4x2 : 5 possibilites
4x3 : 11 possibilites
4x4 : 36 possibilites
Да, и я понятия не имею, как это решить. user3001
@ BlueRaja-DannyPflughoeft Сa(n) имеетΘ(n) цифры, это толькоO(1) так долго какdouble Точность достаточна. Daniel Fischer
Oeis.org / A005178 дает для этого формулу O (1):a(n)=((5*sqrt(29))/145)*(((1+sqrt(29)+sqrt(14+2*sqrt(29)))/4)^n+((1+sqrt(29)-sqrt(14+2*sqrt(29)))/4)^n-((1-sqrt(29)+sqrt(14-2*sqrt(29)))/4)^n-((1-sqrt(29)-sqrt(14-2*sqrt(29)))/4)^n) Удачи, объяснив это твоему учителю BlueRaja - Danny Pflughoeft
Я предпочитаю рекурсивную формулуa(n) = a(n-1)+5*a(n-2)+a(n-3)-a(n-4); написав подходящую матрицу, вы должны получить O (log n). Я предполагаю, что формула O (1) получена диагонализацией матрицы. sdcvvc
Есть простая функция повторения / генерации. Почему динамическое программирование так важно? Это домашнее задание? DSM

Ваш Ответ

2   ответа
2

тки 4 × N, где могут быть заняты некоторые позиции в верхнем ряду. Свяжите каждую позицию со степенью 2, крайний левый соответствует 1, второй 2, третий 4, крайний правый 8. ПустьT(N,k) будет количеством углов сетки 4 × N, где позиции соответствуютk в верхнем ряду уже заняты.k == 0 означает, что позиция не занята,k == 6 означает, что две средние позиции заняты (6 = 2 + 4) и т. д.

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

Например, если две средние позиции заняты, единственный способ заполнить оставшуюся часть верхнего ряда - поместить доминошко вертикально в крайнее левое и крайнее правое положение, что приведет к

|xx|
|  |

и конфигурации, в которой заняты две крайние позиции в следующем ряду, что соответствует1+8 = 9, такT(N,6) = T(N-1,9). И дляk == 9, ситуация, с которой мы начинаем, выглядит

|  |

и у нас есть две возможности,

|==|     ||||
          ||

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

T(N,9) = T(N-1,0) + T(N-1,6)

Используйте эти переходы для построения таблицыT(n,k).

Значение, которое вы хотите найти, этоT(N,0).

1
F[n] = number of ways to tile a 4-by-n grid
G[n] = number of ways to tile a 4-by-n grid with top-right and bottom-right
    squares uncovered
H[n] = number of ways to tile a 4-by-n grid with bottom-right 2
        squares uncovered
  = number of ways to tile a 4-by-n grid with top-right 2
        squares uncovered
if n >= 2, the right end of any tiling can be
    two vertical dominoes (F[n-1] ways)
    horz, horz vert (H[n-1] ways)
    horz, vert, horz (G[n-1] ways)
    vert, horz, horz (H[n-1] ways)
    4 horizontal dominoes (F[n-2] ways)
 F[n] = F[n-1] + G[n-1] + 2*H[n-1] + F[n-2];
 For G: the right end can be a vertical domino (F[n-1] ways)
        or two horizontal dominoes => top & bottom are horz = G[n-2]
        G[n] = F[n-1] + G[n-2];
 For H: the right end can be a vertical domino (F[n-1] ways)
        or two horizontal dominoes (H[n-1] ways)
        H[n] = F[n-1] + H[n-1];
 F[0] = 1, F[1] = 1, G[0] = 0, G[1] = 1, H[0] = 0, H[1] = 1

Похожие вопросы