Во сколько способов вы можете сразить прямоугольник 3xn с домино 2x1?

Question

Каждый день я борюсь с вопросами алгоритма и пытаюсь задать здесь, на которые я не могу ответить. Извините, если у меня возникнет головная боль. Во всяком случае,

Вот проблема из конкурса программирования ACM Университета Ватерлоо.

Сколько способов вы можете выложить прямоугольник 3xn с 2x1 домино?

Нирвана: пахнет рекурсия дух

Answer 1

Просто явное решение уравнений, неявно приведенных в ответе таскинора:

Или

f[n]=((1 + (-1)^n)*((2 - Sqrt[3])^(n/2)*(-1 + Sqrt[3]) + 
     (1 + Sqrt[3])* (2 + Sqrt[3])^(n/2)))/(4*Sqrt[3]) 

, если кому-то все равно.

Покажем 10 значений (для нечетных n решений нет) {n, f [n]}:

{6, 41.},   
{12, 2131.},   
{18, 110771.},   
{24, 5.75796*10^6},   
{30, 2.99303*10^8},   
{36, 1.5558*10^10}, 
{42, 8.08717*10^11},  
{48, 4.20377*10^13}, 
{54, 2.18515*10^15}, 
{60, 1.13586*10^17}

Answer 2

Вы можете решить эту проблему с помощью динамического программирования. Проверьте это для возможного решения.

Answer 3

Просто заметка о том, как получить явную формулу решения, хитрость заключается в том, чтобы записать ее повторение в виде умножения матриц, а затем использовать формулу собственных значений для n -ой степени матрицы.Для приведенной выше рекурсии уравнение имеет вид

(недоступно)

В явной формуле Велизария

можно увидеть четыре собственных значения