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.
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:
If there are two stones, then the following options are available:
|Option||1 Stone||2 Stone|
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|
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)