Primeira vez aqui? Seja bem vindo e cheque o FAQ!
x

De quantas maneiras podemos preencher um tabuleiro 2xn usando peças de tamanho 2x1?

0 votos
13 visitas
perguntada Jun 12 em Ciência da Computação por Adriana Molinari (1 ponto)  

Dado um tabuleiro 2xn e peças de tamanho 2x1, de quantas maneiras podemos preencher o tabuleiro considerando que uma peça pode ser colocada horizontalmente (1x2) ou verticalmente (2x1)?

Compartilhe

1 Resposta

0 votos
respondida Jun 12 por Adriana Molinari (1 ponto)  
editado Jun 12 por Adriana Molinari

Um tabuleiro 2xn pode terminar com duas peças na horizontal ou uma peça na vertical.

Para ilustrar, vejamos as figuras abaixo para um tabuleiro 2x6

A imagem será apresentada aqui.

  1. Na primeira figura podemos observar que posicionando a última peça horizontalmente, a segunda peça também deverá será colocada na horizontal. Neste caso, o problema se reduz a posicionar (n-2) peças em um tabuleiro 2x(n-2)

  2. Já na segunda figura, fica claro que ao posicionar a última peça na vertical, o problema se reduz a posicionar (n-1) peças em um tabuleiro 2x(n-1)

Considerando que \(tabuleiro(n)\) nos retorna de quantas maneiras podemos preencher um tabuleiro 2xn, temos que:

\( \begin{eqnarray*} tabuleiro(n) = tabuleiro(n-1) + tabuleiro(n-2) \end{eqnarray*} \)

Sendo que \(tabuleiro(n) = n\) para \(n = 1\) e \(n = 2\).

Perceba que a relação de recorrência exposta acima nada mais é do que a sequência de Fibonacci, com a diferença de que para n = 1 a sequência de Fibonacci assume valor 0 e para n = 2 assume valor 1.

Abaixo segue o código que nos retorna de quantas maneiras podemos preencher um tabuleiro 2xn com peças 2x1 ou 1x2.

def tabuleiro(n):
if(n>2):
    combinacoes = tabuleiro(n-1) + tabuleiro(n-2)
    return combinações  
else:
    if(n==2): 
        return 2
    else:
        return 1 

Para n = 4, temos o seguinte output:

tabuleiro(4) 

5

comentou 1 dia atrás por CP (6 pontos)  
Em programação computacional, um problema bastante parecido com o problema da maior subsequência comum é o problema da maior susbtring comum. No primeiro caso, como apresentado na solução, a maior subsequência comum não precisa ser contínua. Ou seja, deve-se preservar a relação de ordenação presente nas sequências que estão sendo comparadas, entretanto a continuidade não é necessária. Já no problema da maior substring comum, a continuidade deve ser preservada. O seguinte exemplo ilustra a diferença entre os dois problemas.

Considere as seguintes sequências: abcdaf e bcdf. A maior subsequência comum é dada por bcdf. Já a maior substring comum é dada por bcd.
...