10359  Tiling
Moderator: Board moderators
10359  Tiling
Can anyone tell me why the right answer for input "0" is "1" and not "0"?
Does it mean, that exists exactly one way to tile nothing by anything?
And if the answer is positf, what is this way?
Does it mean, that exists exactly one way to tile nothing by anything?
And if the answer is positf, what is this way?
@+!
DitriX
DitriX
The answer for 0 is 1. There is exactly one way to tile a 2x0 board  that is to tile it with 0 tiles. The reasoning is analogous to choosing 0 items from n items. I hope you'd agree that it's valid.
K M Hasan
http://www.cs.umanitoba.ca/~kmhasan/
http://www.cs.umanitoba.ca/~kmhasan/
Here's the solution:
f(0) = 1
f(1) = 1
f(n) = f(n  1) + 2 * f(n  2)
The recurrence follows from the fact that in general 2xn rectangle there are just three possible tiling schemes:
1. Use a vertical 2x1 piece, and recursively tile the remaining 2x(n1) rectangle.
2. Use a 2x2 piece and tile 2x(n2) rectangle.
3. Use two horizontal 1x2 pieces and tile 2x(n2) rectangle.
Graphically they look like (`#' and `*' stand for pieces, dots  the remaining part of the rectangle):
f(0) = 1
f(1) = 1
f(n) = f(n  1) + 2 * f(n  2)
The recurrence follows from the fact that in general 2xn rectangle there are just three possible tiling schemes:
1. Use a vertical 2x1 piece, and recursively tile the remaining 2x(n1) rectangle.
2. Use a 2x2 piece and tile 2x(n2) rectangle.
3. Use two horizontal 1x2 pieces and tile 2x(n2) rectangle.
Graphically they look like (`#' and `*' stand for pieces, dots  the remaining part of the rectangle):
Code: Select all
#.... ##... ##...
#.... ##... **...
1 2 3
10359  Tiling  CE
Could anyone take a look and tell me why I got CE? (it works on my computer)
// cut...
// cut...
Last edited by Ashganek on Tue Jan 24, 2006 7:24 pm, edited 1 time in total.

 Learning poster
 Posts: 99
 Joined: Sun Apr 06, 2003 5:53 am
 Location: Dhaka, Bangladesh
 Contact:
Re: 10359  Tiling  CE
I have found at least two lines where u can get CE
And by the way, I dont know about any C/C++ compiler where u can pass the latter case. Which compiler did u use ?
Code: Select all
1. c>len = max(a>len, b>len)+1; //'max' : undeclared identifier
2. if( n == 1 or n == 0 ) { return int_to_bint(1); } //'or' : undeclared identifier
Where's the "Any" key?

 New poster
 Posts: 14
 Joined: Mon Sep 03, 2007 10:11 am
 Contact:
Re: 10359  Tiling
Another Easy recursion is
for f(n=even) 2*f(n1)+1
for f(n=odd) 2*f(n1)1
convince yourself ........
for f(n=even) 2*f(n1)+1
for f(n=odd) 2*f(n1)1
convince yourself ........
>>>>>>>>> A2
Beliefs are not facts, believe what you need to believe;)
Beliefs are not facts, believe what you need to believe;)