DominosとL字型トロミノのサイズNX2の長方形の構築[二重]

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

  •  29-09-2020
  •  | 
  •  

質問

Domino and Tromino Compult Tiling （1回）
閉じる 4月前>

質問は L型タイルと2×1タイルで2×nタイルをタイル張りしますか？ この質問や理論についての説明が欲しい

役に立ちましたか？

解決

  • $ f [m] $ 以下に示す形状をカバーする方法の数、 $ m $ $ 2 $ 矩形。私たちの究極の目標は $ f [n] $ です。 
     ┌───────────┐
   2 │           │ 
     └───────────┘
          m
.
  • $ g [m] $ 以下の最初の形状をカバーする方法の数、 $ m $ 2 $ 右上隅にある追加の1x1正方形の四角形。対称性によって、 $ g [m] $ はまた、下に示す2番目の形をカバーする方法の数です。
           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 $ 。

上記の2つの再発方程式の適用、すべての $ f [m] $ と $ g [m]を計算できます。 $ m $ を増やすために、 $ m= 2 $ から始まる$ 初期条件、 $ f [0]= 1 $ 、 $ f [1]= 1 $ 、 $ g [0]= 0 $ と $ 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]
.

これは、 $ f $ のみを含むより単純な再発関係を導き出す方法です。

glorfindelの答え「右端の小中線ブロックをカットする」という方法でパターンの数を計算する方法を説明しています。 リキングするには、 $ 1 \ times2 $ の1つの基本ブロックがあります。 $ 2 \ times2 $ $ n \ times2 $ の2つの基本ブロックは、 $ n \ ge3 $ です。 $ f（n）$ のパターンの数： $ 2 \倍$ のパターン数です。次の基本ケースと再発関係があります。 $$ f（0）= 1、\ f（1）= 1、\ f（2）= 2、$$ $$ f（n）= f（n-1）+ f（n-2）+ 2f（n-3）+ 2f（n-4）+ 2f（N-4）+ 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）+ + + 2f（0）、\ text {for} n \ ge4 $$

上記2方程式を差し引くと、 $$ f（n）-f（n-1）= f（n-1）+ f（n-3）$$ そのため、 $ n \ ge4 $ の場合はあります。 $$ f（n）= 2f（n-1）+ f（n-3）\ tag {simple} $$ $ 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の間の最初の2つの相互再帰的関係から直接単純な再発関係を導出することもできます。 $ 。

平等 $ 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 $ sementi

同じ種類の再発関係、すなわち $ f [m]= 2F [M-1] + F [M-3] $ 。index $ m $ の有効範囲の確認すべての $ m \ ge3 $ 。

他のヒント

それを考える1つの方法は、基本的なブロック、すなわちそれらを垂直に切断することによって分割できないブロックです。

  • サイズ1×2の基本ブロックが1×2です。
  • サイズ2x2の基本ブロックが1つあります（2つの水平BS）。
  • サイズ3x2の2つの基本ブロック（図に示されている最後の2つ、例1）があります。
  • サイズ4x2の2つの基本ブロックがあります（それらは両方とも例の最終パターンに現れます）。
  • 一般に、2つの基本ブロックのサイズ $ n \×2 $ 、 $ n \ ge 3 $ 。

今、 $ n \ whed 2 $ 矩形を2つの小さなブロックに分割することができます。 （エレメンリーブロックが四角形全体の場合は含まれます）。

  • 0x2の長方形は 1ウェイにタイルされます。
  • 1×2の長方形から、私たちは一番右端の小さなブロックを切ることができます（私たちはそれらのうちの1つ持っています）そして私達は0x2の長方形を備えていて、それは 1ウェイでタイルされることができます。
  • 2×2の長方形から、2×2ブロック（1ウェイ）を切り取るか、1×2ブロックを切り取り、1×2矩形（1×1= 1ウェイ）で残して、合計 2の方法で< / strong>。
  • 3x2矩形から：
    • 3×2ブロックをカット（2つの方法）
    • 2x2ブロックをカット（1つの方法）をカットし、1×2の長方形（1ウェイ）
      • で残します。
    • 1×2ブロック（1ウェイ）をカットし、2×2の長方形（2つの方法）で残して
    • 合計：2 + 1 * 1 + 1 * 2= 5つの方法。

このように、あなたは10x2までずっと動作させることができます。

いくつかの用語を計算した後、私はシーケンスが見つかりました A052980 整数シーケンスのオンライン百科事典：

a（n）は、ドミノとL字型のトロミノを用いて、2×N基板の可能なティールの数である。 - Michael Tulskikh、2019年08月21日2019

だから最終的な回答は $ n= 10 $ のための 1255 です。
ライセンス： CC-BY-SA と 帰属
所属していません cs.stackexchange
scroll top