- let $ f [m] $ Sei die Anzahl der Möglichkeiten, die unten gezeigte Form zu decken, ein $ M $ von $ 2 $ Rechteck. Unser ultimatives Ziel ist $ F [N] $ .
generasacodicetagpre.
- let $ g [m] $ Sei die Anzahl der Möglichkeiten, die erste unten gezeigte Form zu decken, ein $ m $ von $ 2 $ Rechteck mit einem zusätzlichen 1x1-Quadrat in der oberen rechten Ecke. Durch Symmetrie, $ g [m] $ ist auch die Anzahl der Möglichkeiten, die zweite unten dargestellte Form abzudecken.
generasacodicetagpre.
Um die Wiederholungsbeziehung zu finden, bedecken Sie den Raum an der rechten Grenze der obigen Formen auf alle möglichen Wege.
Erwägen Sie, $ F [M] $ . Wir haben die folgenden vier Möglichkeiten, um den rechten Platz zu decken.
generasacodicetagpre.
also haben wir $ \ quad \ quad f [m]= f [m - 1] + f [m - 2] + g [m - 2] \ cdot 2 $ für $ m \ ge2 $ .
Betrachten Sie, $ g [m] $ . Wir haben folgende 2 Möglichkeiten, um den rechten Platz der ersten Form abzudecken.
generasacodicetagpre.
wir haben also $ \ quad \ quad g [m]= f [m - 1] + g [m-1] $ für $ M \ GE1 $ .
Anwenden der obigen zwei Wiederholungsgleichungen können wir alle $ F [M] $ und $ g [m] berechnen $ , in der Reihenfolge der zunehmenden $ M $ , beginnend von $ m= 2 $ , Angesichts der Anfangsbedingungen $ f [0]= 1 $ , $ f [1]= 1 $ , $ g [0]= 0 $ und $ g [1]= 1 $ . .
generasacodicetagpre.
Hier ist ein Weg, um eine einfachere Rezidivrelation abzuleiten, die nur $ F $ umfasst.
Glorfindels Antwort erläutert, wie die Anzahl der Muster berechnet wird, indem Sie den Rightout-Elementarblock ausschneiden.
Um zu rekapieren, gibt es einen Elementarblock der Größe $ 1 \ times2 $ , einem Elementarblock von $ 2 \ times2 $ und zwei Elementarblöcke von $ n \ times2 $ für $ n \ ge3 $ . Lassen Sie $ f (n) $ die Anzahl der Muster für $ 2 \ fimes n $ . Wir haben folgende Basisfälle und Rezidivreinigung,
$$ F (0)= 1, \ F (1)= 1, \ F (2)= 2, $$
$$ f (n)= f (n-1) + f (n-2) + 2f (n-3) + 2f (n-4) + \ cdoten + 2f ( 0), \ text {für} n \ ge3 $$
Die obigen Formeln führen zu einem Algorithmus, der $ F (n) $ mit $ O (N ^ 2) berechnet $ Zeitkomplexität und $ o (n) $ Raumkomplexität.
wir können es besser machen. Ersetzen von $ N $ mit $ n-1 $ , haben wir
$$ F (N-1)= F (N-2) + F (N-3) + 2F (N-4) + 2F (N-5) + \ CDs + 2f (0), \ text {für} n \ ge4 $$
subtrahieren Sie die obigen beiden Gleichungen, erhalten wir
$$ F (N) -F (N-1)= F (N-1) + F (N-3) $$
Also haben wir für $ n \ gE4 $ ,
$$ F (N)= 2F (N-1) + F (N-3) \ Tag {Simple} $$
Da $ F (3)= 5= 2f (2) + F (0) $ , gilt das obige Wiederauftrittsrelation für alle $ n \ ge3 $ .
Dies führt zu einem Algorithmus, der berechnet $ F (n) $ mit $ o (n) $ Time- Komplexität und $ O (1) $ Raumkomplexität.
generasacodicetagpre.
Wir können auch die einfache Wiederholungsbeziehung direkt aus den ersten beiden gegenseitigen rekursiven Beziehungen zwischen $ F $ und $ g ableiten $ .
Die Gleichheit $ g [m]= f [m - 1] + g [m-1] $ sagt uns $ f [m-1]= g [m] -g [m-1] $ , und daher $ f [m]= g [m + 1] -g [M] $ und $ F [M-2]= G [M-1] -G [M-2] $ . Anwenden, um sie zu entfernen, um $ F $ in $ f [m]= f [m - 1] + f [m - 2] + g [m - 2] \ cdot 2 $ , wir erhalten $ g [m + 1]= 2g [m] + g [m-2] $ .
Da $ f [m] $ ist eine lineare Kombination von $ g [m + 1] $ und $ g [m] $ , $ F $ zufrieden
Es ist die gleiche Art von Rezidivrelation, d. H.
$ F [M]= 2f [M-1] + F [M-3] $ .Überprüfen des gültigen Bereichs des Index
$ M $ , sehen wir, dass es Wert für alle
$ M \ GE3 $ .
https://cs.stackexchange.com/questions/126237
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
Russian