Construyendo un rectángulo de tamaño NX2 con DominOS y trominos en forma de L [duplicado]

Question

Esta pregunta ya tiene una respuesta aquí :

Domino y Tromino combinados azulejos (1 respuesta)

Cerrado hace 4 meses .

La pregunta es de DP ¡Azulejo de una baldosa 2xn con azulejos en forma de l y azulejos 2x1? Quiero una explicación sobre esta pregunta o teoría

Answer 1

• Permitir $ f [m] $ Sé la cantidad de formas de cubrir la forma que se muestra a continuación, un $ m $ por $ 2 $ Rectangle. Nuestro objetivo final es $ F [n] $ .

     ┌───────────┐
   2 │           │ 
     └───────────┘
          m

• Permitir $ g [m] $ Be el número de formas de cubrir la primera forma que se muestra a continuación, un $ m $ por $ 2 $ Rectángulo con un cuadrado extra 1x1 en la esquina superior derecha. Por simetría, $ g [m] $ también es la cantidad de formas de cubrir la segunda forma que se muestra a continuación.

           m+1                     m
     ┌─────────────┐        ┌───────────┐
   2 │           ┌─┘      2 │           └─┐
     └───────────┘          └─────────────┘
          m                        m+1

Para encontrar la relación de recurrencia, intente cubrir el espacio en el límite más a la derecha de las formas anteriores en todas las formas posibles.

Considere $ f [m] $ . Tenemos las siguientes 4 maneras de cubrir el espacio más a la derecha.

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

Entonces, tenemos $ \ quad \ quad f [m]= f [m - 1] + f [m - 2] + g [m - 2] \ cdot 2 $ para $ m \ ge2 $ .

Considere $ g [m] $ . Tenemos las siguientes 2 formas de cubrir el espacio más a la derecha de la primera forma.

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

Entonces, tenemos $ \ quad \ quad g [m]= f [m - 1] + g [m-1] $ para $ m \ ge1 $ .

Aplicando las dos ecuaciones de recurrencias anteriores, podemos calcular todo $ f [m] $ y $ g [m] $ , en orden de creciente $ m $ , a partir de $ m= 2 $ , Dadas las condiciones iniciales, $ F [0]= 1 $ , $ f [1]= 1 $ , $ g [0]= 0 $ y $ g [1]= 1 $ .

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

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

---

Aquí hay una manera de obtener una relación de recurrencia más simple que involucra $ f $ solo.

La respuesta de Glorfindel explica cómo calcular el número de patrones "Cortar el bloque de primaria más a la derecha". Para resolver, hay un bloque elemental de tamaño $ 1 \ veces2 $ , un bloque elemental de $ 2 \ veces2 $ y dos bloques elementales de $ n \ tim times2 $ para $ n \ ge3 $ . Deje que $ f (n) $ sea el número de patrones para $ 2 \ veces n $ . Tenemos los siguientes casos base y relación de recurrencia, $$ 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 {para} n \ ge3 $$

Las fórmulas anteriores conducen a un algoritmo que calcula $ f (n) $ con $ o (n ^ 2) $ complejidad de tiempo y $ o (n) $ complejidad espacial.

Podemos hacerlo mejor. Reemplazo de $ n $ con $ n-1 $ , tenemos $$ F (N-1)= F (N-2) + F (N-3) + 2F (N-4) + 2F (N-5) + \ CDOTS + 2F (0), \ Text {for} n \ ge4 $$

restando las dos ecuaciones anteriores, obtenemos $$ F (N) -F (N-1)= F (N-1) + F (N-3) $$ Así que tenemos para $ n \ ge4 $ , $$ F (N)= 2F (N-1) + F (N-3) \ TAG {SIMPLE} $$ Desde $ f (3)= 5= 2f (2) + f (0) $ , la relación de recurrencia anterior tiene para todos $ n \ ge3 $ . Esto lleva a un algoritmo que calcula $ f (n) $ con $ o (n) $ tiempo- complejidad y $ O (1) $ complejidad espacial.

# 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] 

---

También podemos derivar la relación de recurrencia simple directamente de las dos primeras relaciones recursivas mutuas entre $ f $ y $ g $ .

La igualdad $ g [m]= F [m - 1] + g [m-1] $ nos dice $ F [M-1]= G [M] -G [M-1] $ , y, por lo tanto, $ f [m]= g [m + 1] -g [m] $ y $ f [m-2]= g [m-1] -g [M-2] $ . Aplicándolos para eliminar $ f $ lejos en $ f [m]= f [m - 1] + f [m - 2] + g [m - 2] \ CDOT 2 $ , obtenemos $ g [m + 1]= 2g [m] + g [m-2] $ .

Desde $ f [m] $ es una combinación lineal de $ g [m + 1] $ y $ g [m] $ , $ f $ Satisfi

es el mismo tipo de relación de recurrencia, es decir, $ f [m]= 2f [M-1] + F [M-3] $ .Verificación del rango válido del índice $ m $ , vemos que es valor para todos $ m \ ge3 $ .

Answer 2

Una forma de pensar que serían bloques elementales, es decir, bloques que no se pueden dividir cortándolos verticalmente.

• Hay un bloque elemental de tamaño 1x2 (una vertical B).
• Hay un bloque elemental de tamaño 2x2 (dos bs horizontales).
• Hay dos bloques elementales de tamaño 3x2 (los dos últimos que se muestran en su figura, ejemplo I).
• Hay dos bloques elementales de tamaño 4x2 (ambos aparecen en el patrón final del Ejemplo II).
• En general, hay dos bloques elementales de tamaño $ n \ veces 2 $ , $ n \ ge 3 $ .

Ahora, un $ n \ veces 2 $ rectangular se puede dividir en dos bloques más pequeños cortando el bloque de elemento más a la derecha. (Esto incluye el caso donde el bloque elemental es todo el rectángulo).

• un rectángulo 0x2 se puede inclinar en 1 vía .
• De un rectángulo 1x2, podemos cortar el bloque elemental más a la derecha (tenemos 1 de ellos) y nos quedamos con un rectángulo 0x2, por lo que se puede inclinar en 1 vía .
• de un rectángulo 2x2, podemos cortar un bloque de 2x2 (1 vía) o cortar un bloque de 1x2 y quedarnos con un rectángulo 1x2 (1 * 1= 1 forma), para un total de 2 ways < / fuerte>.
• de un rectángulo 3x2:
  • Cortar un bloque 3x2 (2 maneras)
  • Cortar un bloque 2x2 (1 vía) y quedarte con un rectángulo 1x2 (1 vía)
  • Corte un bloque 1x2 (1 vía) y se queda con un rectángulo 2x2 (2 formas)
  • TOTAL: 2 + 1 * 1 + 1 * 2= 5 maneras .

De esta manera, puede trabajar hasta 10x2.

Después de calcular algunos términos, encontré que la secuencia es a052980 en la enciclopedia en línea de las secuencias enteras :

a (n) es el número de paneles posibles de un tablero de 2 x N, utilizando DominOS y Trominos en forma de L. - Michael Tulskikh, 21 de agosto de 2019

Entonces, la respuesta final es 1255 para $ n= 10 $ .