CareerCup

Fabnocii number f(n)

Agreed, Fibonnaci sequence. Your f(3) should be 5. Using your notation:

_123_
_13_
_23_
_2_
_12_

i am studied b-tech with eee branch having aggregate 58.85% is it sufficient to get a job with 40k salary?

Guys, there is one more constraint that frog should always step on the first and last steps. He can jump max one step between the first and last but can not escape first and last steps. so, in the above example for f(3): _2_, _23_, _12_ will be eliminated and answer would be only two paths: _123_ and _13_ available.

It can be solve by recursion. Given a current step (say ith) a frog can jump to i+1 or i+2. In either case, the problem is reduced by recursion. The termination is when the frog reach the last stone or the river bank. Hence we can make the recursive call as the frog is on the previous stone (or a river bank):

boolean stones = new boolean[N];
frog(stones,0); //a frog is at the river bank.

void frog(int j){
  if(j >= N-1) print_all_steps(stones);
  else{
    stones[j] = true; //case I: jump to jth
    frog(j+1);
    stones[j] = false;//case II: don't jump to jth
    stone[j+1] = true;//case II: then it has to land on (j+1)th
    froh(j+2);
  }
}

I hope you don't need a code on print_all_steps(boolean[]) as it is clear what to do on stones[N] right :).

Saimok : above solution is great
but a small tweak needed to discard all solution that don't land the frog on the last step :)

i think ans is (2^n - 1) .... as frog either jump on nth step or it may not also , so 2 posibilities for each step ..... As frog should jump atleast one of the steps we have to exclude this case.

//solution below does not print the paths but returns number of possible paths for a given //start index and number of stone
int pp(int n,int start)
{
int end = start+n-1;
if(start>end)return 0;
else if((start == end) || (end == start+1))return 1;
else if(end == (start+2))
return 2;
else
return pp(n-2,start+1)+pp(n-3,start+1)+pp(n-3,start+2)+pp(n-4,start+2);

}

solution below does not print the paths but returns number of possible paths for a given start index and number of stone
int pp(int n,int start)
{
int end = start+n-1;
if(start>end)return 0;
else if((start == end) || (end == start+1))return 1;
else if(end == (start+2))
return 2;
else
return pp(n-2,start+1)+pp(n-3,start+1)+pp(n-3,start+2)+pp(n-4,start+2);

}

#include<stdio.h>

int no_path(int a[], int n, int start)
{
    static int count =0;
    if(start == n-1)
    {
        count++;
        return count;
    }
    if(start+1<n)
        no_path(a,n,start+1);
    if(start+2<n)
            no_path(a,n,start+2);

    return count;
}


 main()
  {
     int a[] = {1,2,3,4,5};
     printf("%d",no_path(a,5,0));
     getch();
  }

Seems its viral...:)
As mentioned it can be solved by fibonacci.
Suppose steps are :
_ a1 a2 a3 a4 a5 ..........an_

f(n)=f(n-1)+f(n-2)
f(n-1)------frog simply goes to a1 and we are left with subproblem to find number of solutions for a2 a3 a4 a5 ....an
f(n-2)------frog can jump a1 and goes to a2,now the left subproblem is a3 a4 a5.....an

Seems its viral...:)
As mentioned it can be solved by fibonacci.
Suppose steps are :
_ a1 a2 a3 a4 a5 ..........an_

f(n)=f(n-1)+f(n-2)
f(n-1)------frog simply goes to a1 and we are left with subproblem to find number of solutions for a2 a3 a4 a5 ....an
f(n-2)------frog can jump a1 and goes to a2,now the left subproblem is a3 a4 a5.....an

public class frog_problem {

public static void frog_path(int a[],int k, int n)
{
if(k==n)
{
if(issafe(a,n)==1)
{
for(int i = 0 ; i<n ;i++)
{
if(a[i]==1)
System.out.print((i+1)+" ");


}

System.out.println();

}
}
else
{
k++;
for(int j=0;j<2;j++)
{
a[k-1] = j;
frog_path(a,k,n);
}

}

}
public static int issafe(int a[],int n)
{
int i ;
for(i=1;i<n-1;i++)
{
if((a[i]==0 && a[i-1]==0) || (a[i]==0 && a[i+1]==0))
return 0;


}

return 1;
}
public static void main(String args[])
{

int n = 4;
int a[] = new int[n];
frog_path(a,0,n);


}

}