Wiederholungsprobleme der Kachel Box

Question

A. Ein Domino ist 2 x 1 Rechteck. Eine Kachelung eines 2 x n-Rechtecks ​​ist eine nicht überlappende Abdeckung durch Dominosteine. Bestimme die Anzahl von was wir tun können. Richten Sie eine Wiederholungsbeziehung ein.

B. Eine Fliese ist eine dreidimensionale Kiste der Größe 2 x 2 x 1. Eine Kachelung einer Kiste der Größe 2 x 2 x n ist eine nicht überlappende Bedeckung dieser Kiste durch Fliesen (in irgendeiner Weise orientiert). Bestimmen Sie die Anzahl der Möglichkeiten, wie wir dies tun können. Richten Sie eine Wiederholungsbeziehung ein.

Für Frage A, die Rekursionsformel I tat ist: T (n) = T (n-1) + T (n-2), die eine Fibonacci-Sequenz ist. Aber für Frage B, irgendwelche Ideen für diese?

Answer 1

Mit der gleichen Logik wie A haben Sie 3 Optionen an jedem Ort, und sie "konsumieren" 1, 2 oder 2 "Slots". Das heißt, die Rekursion ist

T (n) = T (n-1) + 2T (n-2)