let A=1, K=11
The recursive formula:
NumberOfPaths(11) = 0;
NumberOfPaths(10)=1
NumberOfPaths(9)=2;
NumberOfPaths(x) = NumberOfPaths(x+1) + NumberOfPaths(x+2);
we are looking for NumberOfPaths(1).
Even if this looks as an streightforward solution it is O(2^n) algo.
So it is fine for 11 stones but what about 50 000?
The O(n) solution for this problem is:
define array numofpaths[n];
numofpaths[11]=0;
numofpaths[10]=1;
numofpaths[9]=2;
Come from the tail.
for(i=8;i>=1;i--){
numofpaths[i]=numofpaths[i+1]+numofpaths[i+2];
}
print(numofpaths[1]);
assuming the first index of array is 1 not 0;
The simmilar solution for printing the paths.
Best,
Ridvan
On Feb 23, 4:16 pm, Dave <[EMAIL PROTECTED]> wrote:
> Please provide more details.
>
> Dave
>
> On Feb 22, 8:11 am, Ridvan <[EMAIL PROTECTED]> wrote:
>
> > Dinnamic programming problem.
>
> > Just read any example about it.
>
> > On Feb 12, 8:13 am, "Abhijeet Singh" <[EMAIL PROTECTED]> wrote:
>
> > > I have stones numbered from A-K and I have a Frog which can make a jump
> > > of one stone at a time or two stones at a time but no more then that.
> > > I will explain , assumes my stones are ABCDEFG.... K
> > > 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.
>
> > > In how many ways can he reach from A-K, give a recursive formula for that.
>
> > > Print all possible paths that the Frog can choose while moving from A-K-
> > > Hide quoted text -
>
> > - Show quoted text -
--~--~---------~--~----~------------~-------~--~----~
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 [EMAIL PROTECTED]
For more options, visit this group at http://groups.google.com/group/algogeeks
-~----------~----~----~----~------~----~------~--~---
