Навчання / Бібліотека / Комбінаторика

Смужка з квадратів і доміно

КомбінаторикаЛегке

Смужка з $1$ рядка і $9$ клітинок повністю, без перекриття, вкривається плитками, які є або квадратами $1 \times 1$ , або доміно $1 \times 2$ . Скільки існує різних покриттів?

Для перевірки відповіді потрібен JavaScript. Підказка й розв’язок відкриваються і без нього.

Підказка

Подивись, що покриває останню клітинку.

Розв’язок

Нехай $a (n)$ — кількість покриттів смужки з $n$ клітинок.
Остання клітинка покривається або квадратом, що лишає $n - 1$ клітинок, або кінцем доміно, що лишає $n - 2$ клітинок.
Отже, $a (n) = a (n - 1) + a (n - 2)$ з $a (1) = 1$ і $a (2) = 2$ .
Значення для $n = 1, \dots, 9$ — це $1, 2, 3, 5, 8, 13, 21, 34, 55$ , тож $a (9) = 55$ .

Відповідь: $55$

Наступна задача Назад до бібліотеки