Saturday, March 21, 2009

Frog Problem

There are stones numbered from A-K and A frog which can make a jump of one stone at a time or two stones at a time but no more than that. For example, at any point say A, the frog can jump from A-B or from A-C but not from A-D or otherwise, when it reaches J, it can only make a hop of 1 as there are no more stones after that. Frog can not jump backwards.

Now, question is how many ways can frog reach from A-K and Print all possible paths that the Frog can choose while moving from A-K?

Sol: I think, everyone knows Fibonacci's series.
Mathematically..To reach K
No. Of ways to reach K
F(K) = F(K-1)+F(K-2)
= F(J) + F(I)
= No. Of ways to reach J + No. Of ways to reach I (if K > 2)
= 1 , if K = 2 or K = 1
= 0 , if K = 0.

No comments: