@correction.. Though the code implements it, i missed factor '2' in the recurrence that i have provided above...
F(n) = F(n - 1) + F(n - 2) + sum over all i ( 0 to (n-3) ) { 2 * F(i) } -------------------- On Jan 12, 12:44 am, Lucifer <sourabhd2...@gmail.com> wrote: > @above.. > > There is a memory leak in the above code.. but that shouldn't cause a > problem .. :) > > On Jan 12, 12:42 am, Lucifer <sourabhd2...@gmail.com> wrote: > > > > > > > > > @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 <sourabhd2...@gmail.com> 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 <sourabhd2...@gmail.com> wrote: > > > > > @correction: > > > > > F(2) = F(1) + F(0).. > > > > > On Jan 11, 11:59 pm, Lucifer <sourabhd2...@gmail.com> 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 <ravi.cool2...@gmail.com> 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 algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.