A magazine where the digital world meets the real world.
On the web
- Home
- Browse by date
- Browse by topic
- Enter the maze
- Follow our blog
- Follow us on Twitter
- Resources for teachers
- Subscribe
In print
What is cs4fn?
- About us
- Contact us
- Partners
- Privacy and cookies
- Copyright and contributions
- Links to other fun sites
- Complete our questionnaire, give us feedback
Search:
Programming Puzzle 1 Solutions Part 4: new naked mole-rats
![Naked Mole Rat Eating](images/nakedmolerateating.jpg)
We've seen an elegant recursive answer and improved part of it by making it take fewer options. We've then seen how an iterative version building up the Fibonacci sequence from the bottom up could avoid repeatedly computing the same values. However, is there an even faster way? You get really fast algorithms using divide and conquer algorithms, where on each step you halve the size of the problem. Is there such a solution to this. We would need to find a pattern relating numbers in the sequence to ones half way down the sequence.
Remember the sequence is:
1 2 3 4 5 6 7 8 9 10 11 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ...
You would have to be pretty good at pattern matching (or maths) to see it, but there is such a pattern. It is written mathematically as follows:
F(2n) = F(n)*[2F(n+1) - F(n)] F(2n+1) = F(n+1)**2 + F(n)**2
So depending on whether the position in the sequence you are after is odd or even, the pattern is different. In both cases though you can work out the answer by combining the answer from the Fibonacci numbers halfway down the list. With an odd number you add the squares of the numbers, for example.
Take for example the 8th Fibonacci number. It can be calculated using
F(2*4) = F(4)[2*F(5) - F(4)] = 3 (2*5 - 3) = 3 * 7 = 21
Similarly, the 9th Fibonacci number can be calculated using:
F(2*4 + 1) = F(5)**2 + F(4)**2 = 5*5 + 3*3 = 25 + 9 = 34
When used to calculate large fibonacci numbers this will be much faster than the equivalent simple recursive version we already saw as it wont need to calculate all the intermediate numbers. With each calculation it takes a big jump towards the answer.
Can you turn that recursive specification in to a recursive method to calculate fibonacci sequences, and then use it to work out the naked mole-rat totals?