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 3: 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. Can we now work out a quicker way?
We are using recursion and that is elegant in that there is a clear link from specification to algorithm. However, the recursive solution is slow because it computes the same Fibonacci numbers over and over again. A faster way is to build up the answer iteratively from the lowest values.
To compute the next value we are always going to want to add the previous two so we need to keep the last two values. The first two values are both 1 so we can set that up to start.
previous = 1 latest = 1
We then need to repeatedly calculate the new values from the existing ones. The previous value will become the one that was the latest one, and we will get a new latest value. The new value though is obtained by adding the latest and previous values. That means we need to make a copy of the previous value before we over-write it with the old latest value. We can then compute the new value, and finally copy the saved value into previous
temp = latest latest = latest + previous previous = temp
We do this in a loop, running up until we get to the year of interest:
for i in range(0,year) : temp = latest latest = latest + previous previous = temp
When the loop finishes the latest value will be the number we are after, so we return it.
def nakedMoleRat(year): previous = 1 latest = 1 for i in range(0,year) : temp = latest latest = latest + previous previous = temp return latest
We can cut out a few assignments here by doing a parallel assignment (and hope the compiler makes use of that)
def nakedMoleRat(year): previous = 1 latest = 1 for i in range(0,year) : previous, latest = latest, latest + previous return latest
This is a much faster way of computing a Fibonnaci number but we can actually do even better, especially for big numbers, by looking for a divide and conquer method. Can you see a pattern in the sequence that allows the problem size to be halved on each step?