@ravi..
A working code, in case u have test inputs against which u can test
the validity of the logic:
int tiles(int N)
{
if( N > 1)
{
int *a = (int*)malloc(N+1*sizeof(int));
a[0] = a[1] = 1;
int i = 1;
while (++i <= N)
{
a[i] = a[i-1] +a[i-2];
for( int k = 0; k <= (i-3); k++)
{
a[i] += (2*a[k]);
}
}
return a[N];
}
else
return 1;
}
Plz, let me know if the test inputs are failing...
On Jan 12, 12:32 am, Lucifer <[email protected]> wrote:
> @All
>
> I found a flaw in the recurrence provided above..
>
> Correct recurrence is as follows:
>
> F(n) = F(n - 1) + F(n - 2) + sum over all i ( 0 to (n-3) ) { F(i) }
>
> F(0) = F(1) = 1;
>
> On Jan 12, 12:03 am, Lucifer <[email protected]> wrote:
>
>
>
>
>
>
>
> > @correction:
>
> > F(2) = F(1) + F(0)..
>
> > On Jan 11, 11:59 pm, Lucifer <[email protected]> wrote:
>
> > > @ravi..
>
> > > The recurrence would be :
> > > F(N) = F(N-1) + F(N-2) + 2*F(N-3), for N>=3..
>
> > > F(0) = F(1) = 1,
> > > F(2) = F(1) + F(2) = 2
>
> > > On Jan 11, 11:08 pm, Ravi Ranjan <[email protected]> wrote:
>
> > > > *Problem 1: Number of Tilings, (K Narayan Kumar, CMI)*
>
> > > > You have to tile a room that is two units wide and *N* units long. You
> > > > have
> > > > with you two types of tiles: a rectangle that is one unit wide and two
> > > > units long, and an L-shaped tile covering three square units. Here are
> > > > pictures of the two types of tiles.
>
> > > > [image: Figure 1]
>
> > > > You are allowed to rotate the tiles when you lay them. You have an
> > > > infinite
> > > > supply of both types of tiles. Your objective is to calculate the
> > > > number of
> > > > different ways of tiling the room using these tiles.
>
> > > > For instance, a 2×3 room can be tiled in 5 different ways, as follows:
>
> > > > [image: Figure 2]
>
> > > > Notice that a tiling can use both types of tiles. Consider, for
> > > > instance,
> > > > the following tiling of a 2×4 room.
>
> > > > [image: Figure 3]
>
> > > > Given *N*, your task is to determine the number of ways to tile a room
> > > > of
> > > > size 2×*N*. Since this number may be very large, it is sufficient to
> > > > report
> > > > the last four digits of the answer. For instance the number of ways to
> > > > tile
> > > > a 2×13 room is 13465. Your program should just print 3465. If the answer
> > > > involves fewer than 4 digits then print the entire answer. For example,
> > > > if *
> > > > N* = 3 you should print 5.
>
> > > > *Input format*
>
> > > > A single integer *N*, indicating the size of the room.
>
> > > > *Output format*
>
> > > > The last four digits of the number of ways of tiling the 2×*N* room. If
> > > > the
> > > > answer involves fewer than 4 digits, print the entire answer.
>
> > > > *Test Data:*
>
> > > > You may assume *N* ≤ 1000000.
>
> > > > *Example:*
>
> > > > Here is the sample input and output corresponding to the example
> > > > discussed
> > > > above.
>
> > > > *Sample Input*
>
> > > > 13
>
> > > > *Sample Output*
>
> > > > 3465
>
> > > > source::http://www.iarcs.org.in/inoi/2006/zio2006/zio2006-qpaper.pdf
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to [email protected].
To unsubscribe from this group, send email to
[email protected].
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
