Рубрики

Проблема с черепицей

С учетом доски «2 xn» и фишек размером «2 x 1» подсчитайте количество способов разложить данную доску, используя фишки 2 x 1. Плитка может быть размещена либо горизонтально, т. Е. Как плитка размером 1 x 2, либо вертикально, т. Е. Как плитка размером 2 x 1.

Примеры:

Input n = 3
Output: 3
Explanation:
We need 3 tiles to tile the board of size  2 x 3. 
We can tile the board using following ways
1) Place all 3 tiles vertically. 
2) Place first tile vertically and remaining 2 tiles horizontally.
3) Place first 2 tiles horizontally and remaining tiles vertically

Input n = 4
Output: 5
Explanation:
For a 2 x 4 board, there are 5 ways
1) All 4 vertical
2) All 4 horizontal
3) First 2 vertical, remaining 2 horizontal
4) First 2 horizontal, remaining 2 vertical
5) Corner 2 vertical, middle 2 horizontal

Пусть «count (n)» будет количеством способов размещения плиток на сетке «2 xn», у нас есть два способа размещения первой плитки.
1) Если мы поместим первую плитку вертикально, проблема сводится к «count (n-1)»
2) Если мы поместим первую плитку горизонтально, мы должны разместить и другую плитку горизонтально. Таким образом, проблема сводится к «считать (n-2)»

Следовательно, count (n) можно записать так, как показано ниже.

   count(n) = n if n = 1 or n = 2
   count(n) = count(n-1) + count(n-2) 

Вышеуказанное повторение — не что иное, как выражение числа Фибоначчи . Мы можем найти n-ое число Фибоначчи за O (Log n), см. Ниже для всех методов, чтобы найти n-ое число Фибоначчи.

Различные методы для n-го числа Фибоначчи .
Подсчитайте количество способов облицовать пол размером nxm, используя плитки размером 1 xm

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

Рекомендуемые посты:

Проблема с черепицей

0.00 (0%) 0 votes