NPTEL(WEEK-7.1)

Programming Assignment 7.1:Stepping Stones

Due on 2016-03-10, 23:55 IST

There are N stones placed on a shallow river to help people cross the river. The stones are placed in such a way that a person can jump from one stone to the next one, or skip one and jump to the one after that. Find the number of ways in which one can jump across the stones from one river bank to another.
Assume first stone is always used.

Input: Number of stones: N

Output: Number of ways.

Constrains 1<N<40

Example: If N=2, you can hop to bank directly from stone 1 or step to stone 2 and then to bank. Thus, there are two ways to cross a river that needs 2 stones. 

PROGRAM:

/********************************PREFIX*****************************/

#include <stdio.h>

#define MAX 40

/**

 * Find set number of ways to cross river using nSteps.

 * @param nSteps number of stepping stones

 * @param ways   array to be returned with ways[nStep] as answer.

 */

void getWays(int nSteps,int ways[]);

int main() {

int nSteps;

int ways[40];

        scanf("%d",&nSteps);

getWays(nSteps,ways);

printf("%d",ways[nSteps]);

return 0;

}

CODING:

void getWays(int nSteps,int ways[]) {

        //TODO

   int final;

        final=fun(0,nSteps);

        ways[nSteps]=final;

}

int fun(int current,int final)

{

  if(current==final-2)

  {

   return 2;

  }

  else if(current==final-1)

  {

   return 1;

  }

  else

  {

   return fun(current+1,final)+fun(current+2,final);

   }

 }