user16655 - 6 months ago 35

Java Question

I am trying to solve this question as the preparation for a programming interview:

A frog only moves forward, but it can move in steps 1 inch long or in jumps 2 inches long. A frog can cover the same distance using different combinations of steps and jumps.

Write a function that calculates the number of different combinations a frog can use to cover a given distance.

For example, a distance of 3 inches can be covered in three ways: step-step-step, step-jump, and jump-step.

I think there is a quite simple solution to this, but I just can't seem to find it. I would like to use recursion, but I can't see how. Here is what I have so far:

`public class Frog {`

static int combinations = 0;

static int step = 1;

static int jump = 2;

static int[] arr = {step, jump};

public static int numberOfWays(int n) {

for (int i = 0; i < arr.length; i++) {

int sum = 0;

sum += arr[i];

System.out.println("SUM outer loop: " + sum + " : " + arr[i]);

while (sum != 3) {

for (int j = 0; j < arr.length; j++) {

if (sum + arr[j] <= 3) {

sum += arr[j];

System.out.println("SUM inner loop: " + sum + " : " + arr[j]);

if (sum == 3) {

combinations++;

System.out.println("Combinations " + combinations);

}

}

}

}

}

return combinations;

}

public static void main(String[] args) {

System.out.println(numberOfWays(3));

}

}

It doesn't find all combinations, and I think the code is quite bad. Anyone have a good solution to this question?

Answer

Think you have an oracle that knows how to solve the problem for "smaller problems", you just need to feed it with smaller problems. This is the recursive method.

In your case, you solve `foo(n)`

, by splitting the possible moves the frog can do in the last step, and summing them):

```
foo(n) = foo(n-1) + foo(n-2)
^ ^
1 step 2 steps
```

In addition, you need a stop clause of `foo(0) = 1, foo(1)=1`

(one way to move 0 or 1 inches).

Is this recursive formula looks familiar? Can you solve it better than the naive recursive solution?

**Spoiler:**

_{Fibonacci Sequence}