Puzzle:

A frog wants to cross a river that is 11 feet across.

There are 10 stones in a line leading across the river, separated by 1 foot. He can either jump to the next stone or jump over a stone, and if he jumps over a stone he must land on the next one. The furthest he can jump is 2 feet. Also, he always moves forward (toward the other side of the river). **In how many different ways can he cross the river?**

For example, one way to cross would be 1,2,2,1,1,2,1 with representing the frog moving 1 foot forward to the next stone, and representing the frog jumping over one stone, moving 2 feet forward.

The total distance jumped must be 11 feet; that is, if the frog is at 10 feet, the frog can’t jump by 2 feet.

**Hint:** What are the possible conditions before getting to the stone?

**Bonus:** Try to come up with a recursive routine to calculate this value for stones.

**Solution**:

Correct answer: **144**

To get to (n+2)th stone, he could either come from (n+1)th stone or nth stone. For instance, the frog can either get to 5th stone from 4th stone or from the 3rd stone.

Let’s examine what this means with a few smaller examples. If there is one stone, then the frog can either jump on it, or jump over it:

Option | 1 Stone |

1 | On |

2 | Over |

If there are two stones, then the following options are available:

Option | 1 Stone | 2 Stone |

1 | On | On |

2 | On | Over |

3 | Over | On |

There are only 3 options, because the frog cannot jump over two stones straight to the other side. At most his jumps take him 2 feet forward.

If there are three stones, then the following options are available:

Option | 1 Stone | 2 Stone | 3 Stone |

1 | On | On | On |

2 | On | On | Over |

3 | On | Over | On |

4 | Over | On | On |

5 | Over | On | Over |

There are 5 options.

This is actually enough to start seeing a pattern. The number of ways to get to the 3 stone is a3 = a2+a1 or 5 = 3 +2 . If you continue with 4, 5, 6, etc. stones, you’ll find that this pattern continues. So, the number of ways to get to nth stone is an = an-1+ an-2 or the famous Fibonacci numbers.

With this formula we can predict the 11 stone as the 11 term of the Fibonacci sequence,

Simple algorithm for fibonacci series:

```
def fibonacci(n):
if n < 0:
raise ValueError("invalid index!")
if n==0:
return 0
if n==1:
return 1
return fibonacci(n-1) + fibonacci(n-2)
```