Construindo um retângulo de tamanho nx2 com dominós e trominós em forma de L [duplicado]
https://cs.stackexchange.com/questions/126237
-
29-09-2020 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianPergunta
A pergunta é de DP colocando um ladrilho 2xN com ladrilhos em forma de L e ladrilhos 2x1?Quero uma explicação sobre esta questão ou teoria
Solução
- Deixar $f[m]$ seja o número de maneiras de cobrir a forma mostrada abaixo, um $m$ por $2$ retângulo.Nosso objetivo final é $f[n]$.
┌───────────┐
2 │ │
└───────────┘
m
- Deixar $g[m]$ seja o número de maneiras de cobrir a primeira forma mostrada abaixo, um $m$ por $2$ retângulo com um quadrado 1x1 extra no canto superior direito.Por simetria, $g[m]$ é também o número de maneiras de cobrir a segunda forma mostrada abaixo.
m+1 m
┌─────────────┐ ┌───────────┐
2 │ ┌─┘ 2 │ └─┐
└───────────┘ └─────────────┘
m m+1
Para encontrar a relação de recorrência, tente cobrir o espaço no limite mais à direita das formas acima de todas as maneiras possíveis.
Considerar $f[m]$.Temos as seguintes 4 maneiras de cobrir o espaço mais à direita.
┌─────────┬─┐ ┌──────┬────┐ ┌───────┬───┐ ┌─────────┬─┐
│ │ │ │ ├────┤ │ └─┐ │ │ ┌─┘ │
└─────────┴─┘ └──────┴────┘ └─────────┴─┘ └───────┴───┘
What is left: (m-1)x2 (m-2)x2 (m-2)x2+1 (m-2)x2+1
Então nós temos $\quad\quad f[m] = f[m - 1] + f[m - 2] + g[m - 2] \cdot 2 $ para $m\ge2$.
Considerar $g[m]$.Temos as 2 maneiras a seguir de cobrir o espaço mais à direita da primeira forma.
m+1 m+1
┌─────────┬───┐ ┌─────────┬───┐
│ │ ┌─┘ │ └─┬─┘
└─────────┴─┘ └───────────┘
What is left: (m-1)x2 (m-1)x2+1
Então nós temos $\quad\quad g[m] = f[m - 1] + g[m-1]$ para $m\ge1$.
Aplicando as duas equações de recorrência acima, podemos calcular todos $f[m]$ e $g[m]$, em ordem crescente $m$, Começando de $m=2$, dadas as condições iniciais, $f[0]=1$, $f[1]=1$, $g[0]=0$ e $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]
Aqui está uma maneira de derivar uma relação de recorrência mais simples que envolve $f$ apenas.
A resposta de Glorfindel Explica como calcular o número de padrões "cortando o bloco elementar mais à direita". Para recapitular, há um bloco elementar de tamanho $1\vezes2$, um bloco elementar de $2\vezes2$ e dois blocos elementares de $n\vezes2$ para $n\ge3$.Deixar $f(n)$ seja o número de padrões para $2\vezes n$.temos os seguintes casos base e relação de recorrência,$$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), ext{ para }n\ ge3 $$
As fórmulas acima levam a um algoritmo que calcula $f(n)$ com $O(n^2)$ complexidade de tempo e $O(n)$ complexidade do espaço.
Podemos fazer melhor.Substituindo $n$ com $n-1$, Nós temos $$f(n-1)=f(n-2)+f(n-3)+2f(n-4)+2f(n-5)+\cdots+2f(0), ext{ para } n\ge4 $$
Subtraindo as duas equações acima, obtemos$$f(n)-f(n-1)=f(n-1)+f(n-3)$$Então temos para $n\ge4$, $$f(n)=2f(n-1)+f(n-3) ag{simples}$$Desde $f(3)=5=2f(2)+f(0)$, a relação de recorrência acima vale para todos $n\ge3$.Isso leva a um algoritmo que calcula $f(n)$ com $O(n)$ complexidade de tempo e $O(1)$ complexidade do espaço.
# 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]
Também podemos derivar a relação de recorrência simples diretamente das duas primeiras relações recursivas mútuas entre $f$ e $g$.
A igualdade $g[m] = f[m - 1] +g[m-1]$ diga-nos $f[m-1] = g[m]-g[m-1]$, e, portanto, $f[m] = g[m+1]-g[m]$ e $f[m-2] = g[m-1]-g[m-2]$.Aplicá-los para eliminar $f$ longe em $f[m] = f[m - 1] + f[m - 2] + g[m - 2] \cdot 2$, Nós temos $g[m+1]=2g[m]+g[m-2]$.
Desde $f[m]$ é uma combinação linear de $g[m+1]$ e $g[m]$, $f$ satisfaz o mesmo tipo de relação de recorrência, ou seja, $f[m]=2f[m-1]+f[m-3]$.Verificando o intervalo válido do índice $m$, vemos que é valor para todos $m\ge3$.
Outras dicas
Uma maneira de pensar nisso seria blocos elementares, isto é, blocos que não podem ser divididos cortando-os verticalmente.
- Há um bloco elementar de tamanho 1x2 (um vertical B).
- Há um bloco elementar de tamanho 2x2 (duas horizontais BS).
- Existem dois blocos elementares de tamanho 3x2 (os dois últimos mostrados na sua figura, exemplo I).
- Há dois blocos elementares de tamanho 4x2 (ambos aparecem no padrão final do Exemplo II).
- Em geral, há dois blocos elementares de tamanho $ n \ vezes 2 $ , $ n \ GE 3 $ .
Agora, uma $ n \ vezes 2 $ retângulo pode ser dividido em dois blocos menores, cortando o bloco elementar mais à direita. (Isso inclui o caso em que o bloco elementar é todo o retângulo).
- um retângulo 0x2 pode ser revestido em 1 caminho .
- de um retângulo 1x2, podemos cortar o bloco elementar mais à direita (temos 1 deles) e ficamos com um retângulo 0x2, para que possa ser revestido em 1 caminho .
- de um retângulo 2x2, podemos cortar um bloco 2x2 (1 caminho) ou cortar um bloco 1x2 e ser deixado com um retângulo 1x2 (1 * 1= 1 caminho), para um total de 2 maneiras < / forte>.
- de um retângulo 3x2:
- Corte um bloco 3x2 (2 maneiras)
- Corte um bloco 2x2 (1 caminho) e seja deixado com um retângulo 1x2 (1 caminho)
- Corte um bloco 1x2 (1 caminho) e seja deixado com um retângulo 2x2 (2 maneiras)
- total: 2 + 1 * 1 + 1 * 2= 5 maneiras .
Desta forma, você pode trabalhar todo o caminho para 10x2.
Após a computação alguns termos, encontrei a sequência é A052980 na enciclopédia on-line de sequências inteiras :
.a (n) é o número de tilings possíveis de uma placa de 2 x n, usando dominós e trominos em forma de L. - Michael Tulskikh, 21 de agosto de 2019
Então a resposta final é 1255 para $ n= 10 $ .
