DominoS와 L 자형 트로 모노가있는 크기 NX2의 직사각형 구축 [중복]

cs.stackexchange https://cs.stackexchange.com/questions/126237

  •  29-09-2020
  •  | 
  •  

문제

질문은 DP는 L 모양의 타일과 2x1 타일이있는 2xn 타일을 타일링합니까? 나는이 질문이나 이론에 대한 설명을 원한다

도움이 되었습니까?

해결책

  • $ f [m] $ 아래 표시된 모양을 덮을 수있는 방법의 수, $ m $ $ 2 $ 사각형에 의한 . 우리의 궁극적 인 목표는 $ f [n] $ 입니다. 
     ┌───────────┐
   2 │           │ 
     └───────────┘
          m
.
  • $ g [m] $ 아래에 표시된 첫 번째 모양을 덮는 방법의 수, $ m $ $ 2 $ 2 $ 사각형 오른쪽 상단 모서리에 추가 1x1 스퀘어가있는 사각형입니다. 대칭별로 $ g [m] $ 은 아래에 표시된 두 번째 모양을 덮을 수있는 방법의 수입니다. 
           m+1                     m
     ┌─────────────┐        ┌───────────┐
   2 │           ┌─┘      2 │           └─┐
     └───────────┘          └─────────────┘
          m                        m+1
.

재발성 관계를 찾으려면 모든 가능한 방법으로 위 모양의 가장 왼쪽의 우표 경계에서 공간을 덮어보십시오.

$ f [m] $ 을 고려하십시오. 가장 오른쪽 공간을 덮는 4 가지 방법이 있습니다. 

              ┌─────────┬─┐     ┌──────┬────┐     ┌───────┬───┐     ┌─────────┬─┐
              │         │ │     │      ├────┤     │       └─┐ │     │       ┌─┘ │
              └─────────┴─┘     └──────┴────┘     └─────────┴─┘     └───────┴───┘
What is left:   (m-1)x2         (m-2)x2            (m-2)x2+1         (m-2)x2+1
.

그래서, 우리는 $ \ quad \ quad f [m]= f [m - 1] + f [m - 2] + g [m - 2] \ CDOT 2 $ $ m \ ge2 $ .

$ g [m] $ 을 고려하십시오. 우리는 첫 번째 모양의 가장 오른쪽 공간을 덮을 다음 2 가지 방법을 가지고 있습니다. 

                     m+1                 m+1
               ┌─────────┬───┐     ┌─────────┬───┐
               │         │ ┌─┘     │         └─┬─┘
               └─────────┴─┘       └───────────┘
 What is left:   (m-1)x2              (m-1)x2+1
.

$ \ quad \ quad g [m]= f [m - 1] + g [m-1] $ $ M \ GE1 $ .

위의 두 재발 방정식을 적용하면 모든 $ f [m] $ 및 $ g [m] $ $ m $ 을 증가시켜 $ m= 2 $ 에서 시작하여 $ m $ 의 순서대로, 초기 조건을 감안할 때 $ f [0]= 1 $ , $ f [1]= 1 $ $ g [0]= 0 $ 및 $ g [1]= 1 $

여기서는 $ f $ 에만

를 포함하는 간단한 반복 관계를 도출하는 방법입니다.

Glorfindel의 답변 "가장 오른쪽 기본 블록을 절단하여 패턴 수를 계산하는 방법을 설명합니다. 요약하려면 $ 1 \ times2 $ 의 기본 블록 하나, $ 2 \ times2 $ $ n \ times2 $ $ n \ times2 $ 의 두 개의 기본 블록. $ f (n) $ $ 2 \ times n $ 의 패턴 수가되도록하십시오. 우리는 다음과 같은 기본 경우와 재발 관계를 보유하고 있습니다. $$ F (0)= 1, \ f (1)= 1, \ f (2)= 2, $$ $$F (n)= F (N-1) + F (N-2) + 2F (N-3) + 2F (N-4) + \ CDOTS + 2F ( 0), \ text {for} n \ ge3 $$

위의 수식은 $ f (n) $ $ o (n ^ 2)를 계산하는 알고리즘으로 이어집니다. $ 시간 복잡성 및 $ o (n) $ 공간 복잡성.

우리는 더 잘할 수 있습니다. $ N $ $ n-1 $ 을 사용하여 우리는 $$ F (N-1)= F (N-2) + F (N-3) + 2F (N-4) + 2F (N-5) + \ CDOTS + 2F (0), \ text {for} n \ ge4 $$

위의 두 방정식을 빼는 우리는 얻습니다. $$ F (n) -F (n-1)= f (n-1) + f (n-3) $$ 그래서 우리는 $ n \ ge4 $ , $$ F (n)= 2F (N-1) + F (n-3) \ 태그 {단순} $$ $ f (3)= 5= 2F (2) + F (0) $ , 위의 재발 관계는 모든 $ n \ ge3 $ . 이로 인해 $ f (n) $ > $ o (n) $ 시간 - 시간을 계산하는 알고리즘으로 이어집니다. 복잡성 및 $ o (1) $ 공간 복잡도. 

# Python program to compute the first n+1 values of f
def show_number_of_ways(n):
    f = [0] * (n+1)
    f[0] = f[1] = 1
    f[2] = 2
    for i in range(3, n+1):
        f[i] = 2 * f[i - 1] + f[i - 3]
    print(f)

show_number_of_ways(10)
# [1, 1, 2, 5, 11, 24, 53, 117, 258, 569, 1255]
.

우리는 $ f $ 와 $ g 사이의 첫 번째 두 상호 재귀 적 관계와 직접 간단한 재발 관계를 도출 할 수 있습니다. $ .

평등 $ g [m]= f [m - 1] + g [m-1] $ 은 $ f [m-1]= g [m] -g [m-1] $ 및 $ f [m]= g [m + 1] -G [m] $ 및 $ f [m-2]= g [M-1] -G [M-2] $ . $ F $ 수학 용기 "> $ F [m]= f [m - 1] + F [m] 2] + g [m - 2] \ CDOT 2 $ , 우리는 $ g [m + 1]= 2G [m] + g [m-2] $ .

$ f [m] $ 은 $ g [m + 1] $ 및 $ g [m] $ , $ f $ span>

ES는 동일한 종류의 재발 관계, 즉 $ f [m]= 2F [m-1] + f [m-3] $ . $ m $ 의 유효한 범위를 확인하십시오. 모든 $ m \ ge3 $ .

다른 팁

그것에 대해 생각하는 한 가지 방법은 기본 블록, 즉 세로로 절단하여 분할 할 수없는 블록이 될 것입니다.

  • 1x2 크기의 기본 블록이 있습니다 (하나의 수직 B).
  • 크기 2x2의 1 개의 기본 블록이 있습니다 (2 개의 수평 BS).
  • 크기 3x2의 두 개의 기본 블록이 있습니다 (그림 I 예의 마지막 두 개, i).
  • 크기 4x2의 두 가지 기본 블록이 있습니다 (둘 다 예제 II의 최종 패턴으로 나타남).
  • 일반적으로 크기 $ n \ times 2 $ , $ n \ ge 3 $ .

이제 $ n \ times 2 $ 사각형은 가장 오른쪽 기본 블록을 절단하여 두 개의 작은 블록으로 나눌 수 있습니다. (이것은 기본 블록이 전체 사각형 인 경우가 포함됩니다.

  • 0x2 직사각형은 1 way
    • 로 바둑판 식으로 배열 될 수 있습니다.
  • 1x2 직사각형에서 가장 오른쪽 기본 블록 (우리가 1 개를 가지고 있음)을자를 수 있으며 0x2 사각형으로 남아 있으므로 1 way 에 바둑판 식으로 바둑판 식으로 할 수 있습니다.
  • 2x2 사각형에서 2x2 블록 (1 웨이)을 자르거나 1x2 블록을 자르고 1x2 직사각형 (1 * 1= 1 방향으로 1x1= 1 방향으로) 왼쪽으로 2 forew < / strong>.
  • 3x2 직사각형 :
    • 3x2 블록 (2 가지 방법)
    • 는 2x2 블록을 자르고 1x2 직사각형 (1 way)
      • 로 좌회전합니다.
    • 는 1x2 블록을 자르고 2x2 직사각형 (2 가지 방법)
      • 로 둡니다.
    • 총량 : 2 + 1 * 1 + 1 * 2= 5 가지 방법

이렇게하면 10x2로 모든 방법으로 작동 할 수 있습니다.

몇 가지 용어를 계산 한 후 Sequence는 A052980 정수 시퀀스의 온라인 백과 사전에 있습니다. :

a (n)은 도미노 및 L 자형 트로 모노를 사용하여 2 x n 보드의 가능한 기울임을 사용할 수있는 시간입니다. - Michael Tulskikh, 2019 년 8 월 21 일

최종 대답은 $ n= 10 $ 에 대해 1255 입니다.

라이센스 : CC-BY-SA ~와 함께 속성
제휴하지 않습니다 cs.stackexchange
scroll top