Construire un rectangle de taille NX2 avec des dominos et des trominos en forme de L [duplicate]

Question

Cette question a déjà une réponse ici :

carrelage combiné Domino et Tromino (1 réponse)

fermée Il y a 4 mois .

La question est de DP carrelez une tuile 2xn avec des carreaux en forme de L et des carreaux 2x1? Je veux une explication sur cette question ou la théorie

Answer 1

• Soit $ f [m] $ le nombre de façons de couvrir la forme indiquée ci-dessous, une $ m $ par $ 2 $ rectangle. Notre objectif ultime est $ f [n] $ .

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

• Soit $ g [m] $ le nombre de façons de couvrir la première forme représentée ci-dessous, une $ m $ par $ 2 $ rectangle avec un carré supplémentaire 1x1 dans le coin supérieur droit. Par symétrie, $ g [m] $ est également le nombre de façons de couvrir la deuxième forme indiquée ci-dessous.

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

Pour trouver la relation de récurrence, essayez de couvrir l'espace à la limite la plus à la droite des formes ci-dessus de toutes les manières possibles.

considérer $ f [m] $ . Nous avons les 4 moyens suivants de couvrir l'espace le plus à droite.

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

Alors, nous avons $ \ quad \ quad f [m]= f [m - 1] + f [m - 2] + g [m - 2] \ cdot 2 $ pour $ m \ ge2 $ .

considérer $ g [m] $ . Nous avons les 2 façons suivantes de couvrir l'espace le plus à droite de la première forme.

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

nous avons donc $ \ quad \ quad g [m]= f [m - 1] + g [m-1] $ pour $ m \ ge1 $ .

L'application de ce qui précède deux équations de récurrence, on peut calculer tous les $ f [m] $ et $ g [m] $ , dans l'ordre d'augmenter $ m $ , à partir de $ m= 2 $ , Compte tenu des conditions initiales, $ f [0]= 1 $ , $ f [1]= 1 $ , $ g [0]= 0 $ et $ 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] 

---

Voici un moyen de dériver une relation de récurrence plus simple qui implique $ f $ seulement.

réponse de Glorfindel explique comment calculer le nombre de motifs par « couper le bloc élémentaire extrême droite. » Pour résumer, il y a un bloc élémentaire de taille $ 1 \ times2 $ , un bloc élémentaire de $ 2 \ times2 $ et deux blocs élémentaires de $ n \ fois2 $ pour $ n \ ge3 $ . Laissez $ f (n) $ Soyez le nombre de motifs pour $ 2 \ fois n $ . Nous avons les cas de base et la relation de récurrence suivants, $$ 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 $$

Les formules ci-dessus conduit à un algorithme qui calcule $ f (n) $ avec $ O (n ^ 2) $ complexité du temps et $ O (n) $ complexité spatiale.

Nous pouvons faire mieux. Remplacer $ n $ avec $ n-1 $ , nous avons $$ f (n-1)= f (n-2) + f (n-3) + 2f (n-4) + 2f (n-5) + \ cdots + 2f (0), \ Text {for} n \ ge4 $$

soustraire les deux équations ci-dessus, nous obtenons $$ f (n) -f (n-1)= f (n-1) + f (n-3) $$ Donc nous avons pour $ n \ ge4 $ , $$ f (n)= 2f (n-1) + f (n-3) \ tag {simple} $$ Depuis $ f (3)= 5= 2f (2) + f (0) $ , la relation de récurrence ci-dessus est valable pour tous $ n \ ge3 $ . Cela conduit à un algorithme qui calcule $ f (n) $ avec $ O (n) $ de temps Complexité et $ O (1) $ Complexité spatiale.

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

---

Nous pouvons également déduire la relation simple de récurrence directement à partir des deux premières relations récursives mutuelles entre $ f $ et $ g $ .

L'égalité $ g [m]= f [m - 1] + g [m-1] $ nous dit $ f [m-1]= g [m] -g [m-1] $ , et, par conséquent, $ f [m]= g [m + 1] -g [m] $ et $ f [m-2]= g [m-1] -g [m-2] $ . Les appliquer pour éliminer les $ f $ loin dans $ f [m]= f [m - 1] + f [m - 2] + g [m - 2] \ cdot $ 2 , nous obtenons $ g [m + 1]= 2 g [m] + g [m-2] $ .

Comme $ f [m] $ est une combinaison linéaire de $ g [m + 1] $ et $ g [m] $ , $ f $ satisfixes

es le même type de relation de récurrence, c'est-à-dire $ f [m]= 2f [m-1] + f [m-3] $ .Vérification de la plage valide de l'index $ M $ , nous voyons qu'il est de valeur pour tous $ m \ ge3 $ .

Answer 2

Un moyen d'y penser serait des blocs élémentaires, c'est-à-dire des blocs qui ne peuvent pas être divisés en les coupant verticalement.

• Il y a un bloc élémentaire de taille 1x2 (une verticale B).
• Il y a un bloc élémentaire de taille 2x2 (deux BS horizontales).
• Il y a deux blocs élémentaires de taille 3x2 (les deux derniers représentés dans votre figure, exemple I).
• Il y a deux blocs élémentaires de taille 4x2 (ils apparaissent tous deux dans le schéma final de l'exemple II).
• En général, il existe deux blocs élémentaires de taille $ n \ fois 2 $ , $ n \ ge 3 $ .

MAINTENANT, UNE $ N \ TIMES 2 $ Le rectangle peut être divisé en deux blocs plus petits en coupant le bloc élémentaire le plus à droite. (Cela inclut le cas où le bloc élémentaire est le rectangle entier).

• Un rectangle 0x2 peut être carrelé dans 1 manière .
• à partir d'un rectangle de 1x2, nous pouvons couper le bloc élémentaire le plus à droite (nous en avons 1) et nous sommes partis avec un rectangle de 0x2, il peut donc être carrelé dans 1 manière .
• à partir d'un rectangle 2x2, nous pouvons soit couper un bloc 2x2 (1 moyen) ou couper un bloc 1x2 et être laissé avec un rectangle 1x2 (1 * 1= 1 manière), pour un total de 2 façons < / fort>.
• à partir d'un rectangle 3x2:
  • Couper un bloc 3x2 (2 façons)
  • Coupez un bloc 2x2 (1 moyen) et laissez-le avec un rectangle de 1x2 (1 moyen)
  • Coupez un bloc 1x2 (1 moyen) et laissez-le avec un rectangle 2x2 (2 façons)
  • Total: 2 + 1 * 1 + 1 * 2= 5 façons .

De cette façon, vous pouvez travailler jusqu'au 10x2.

Après avoir calculé quelques termes, j'ai trouvé que la séquence est A052980 dans l'encyclopédie en ligne des séquences entier :

A (N) est le nombre d'éventuelles éventuelles d'une planche de 2 x N, à l'aide de dominos et de trominos en forme de L. - Michael Tulskikh, 21 août 2019

La réponse finale est donc 1255 pour $ n= 10 $ .

.

.