Consider the 1-2 tiling problem. You are given a 1×n area that you need to tile

Question

Consider the 1-2 tiling problem. You are given a 1×n area that you need to tile with some combination of 1 × 1 and 1 × 2 tiles, and you need to determine how many ways there are to tile this area

For example, there are 3 ways to tile a 1 × 3 area:

Give pseudocode for a divide-and-conquer algorithm for this problem. There is an O(n) solution, though a less efficient solution may be acceptable, as long as it is sub-exponential

Hint: you will probably want to consider odd and even n separately. One useful observation is that there are only 3 ways to cover a tile in the middle of the area: a 1 × 1 tile, a 1 × 2 tile that extends to the left, and a 1 × 2 tile that extends to the right. Also, when dividing up your problem, don’t forget about the possibility of a 1×2 block crossing the boundary between two subproblems.

Explanation / Answer

Given (1 x n) area and tiles of size (1 x 1) and (1 x 2).

Let us try to get a pattern here.

A (1 x 1) area can only be tiled 1 way i.e. using (1 x 1) tile.
A (1 x 2) area can be tiled 2 ways: either using two (1 x 1) tile or using one (1 x 2) tile.
A (1 x 3) area can be tiled 3 ways: three (1 x 1) tiles, OR a combination of (1 x 2) tile and (1 x 1) tiles OR using (1 x 1) tile and (1 x 2) tiles.
A (1 x 4) area can be tiled 5 ways...

As we see here, the number of ways will turn out to be Fibonacci numbers.

So, the problem boils down to find the (n+1)th Fibonacci number for a (1 x n) area.

CODE:

//O(logn) approach

int fib(int n)
{
// Array to store Fibonacci numbers
int f[n+1];
int i;

// 0th and 1st number of the series are 0 and 1
f[0] = 0;
f[1] = 1;

for (i = 2; i <= n; i++)
{
f[i] = f[i-1] + f[i-2];
}

return f[n];
}

To find number of ways to fill the (1 x 4) area, pass the input as 5 to the above
function, the value returned will be 5, which is the answer.

Related Questions

Navigate

• Browse (All)
• Browse C
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.