auffüllt 2 xn Array mit dominos

Question

i die Methode schreiben müssen:

public int domino(int num)

i haben eine zweidimensionale Integer-Array mit 2 x num Größe (2 Zeilen und num Spalten)

i brauchen um herauszufinden, wie viele Möglichkeiten ich das Board mit Domino-Blöcken füllen kann

(jeder Domino füllt 2 Zellen, die berühren und nicht diagonal)

ich sollte Rekursion verwenden, um dies zu tun, aber

ich, dass vielleicht Hink es eine Möglichkeit, dies zu tun, nur:

return(some sort of combinatorics formula) 

ist es eine Formel für das?

danke

Answer 1

Dies kann durch einfache Wiederholungsmethode erfolgen. Angenommen, T(n) ist eine Anzahl von Möglichkeiten, wie eine 2 x n-Karte gefüllt werden kann.

Betrachten Sie nun die Zelle oben links. Der Domino, der dies abdeckt, kann auf zwei verschiedene Arten ausgerichtet sein.

1) Horizontaler 2) Vertikale

Im Fall 1, da das Domino horizontal ist, müssen die Zellen auch unten durch einen horizontalen Domino gefüllt werden. Danach bleibt eine 2 x (n-2) Platte, die in T(n-2) Wege gefüllt werden kann.

Im zweiten Fall bleibt eine 2 x (n-1) Platine, die in T(n-1) Wege gefüllt werden kann.

So ist die Gesamtzahl von Möglichkeiten ein 2 x n Bord Füllung ist

T(n) = T(n-1) + T(n-2) und die Basis Fall ist, T (1) = 1, die leicht überprüft werden können.

Es ist im Grunde die Fibonacci Wiederholung, die eine geschlossene Form Lösung hat.