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

To find total number of ways, we can divide the 1XN tile into two parts from the middle, and keep dividing it till the size becomes, then we start merging them. At every merge there will be one more way, which can be created by combining last tile and first tile of the two merging tiles.

when the tile size is 1X1, then there is only 1 way.

Thus, return 1 when size is 1X1

return 1+numberOfWays(a,x-1) + numberOfWays(x,b) , where 0<=a<x<b<=N

//PseudoCode __________________________________________________________________

numberOfWays (low,high):
if(high-low==1) then
return 1;
mid = (high-low)/2;
return 1 + numberOfWays(low,mid) + numberOfWays(mid+1,high)
end numberOfWays

//Assuming 1*N tile
//N is length of Tile
TotalWays = numberOfWays(0,N-1)

//End of PseudoCode

___________________________________________________________________________________

Related Questions

Navigate

• Browse (All)
• Browse C
• Subjects

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