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 5: new naked mole-rats
![Naked Mole Rat Eating](images/nakedmolerateating.jpg)
So to create a divide and conquer version of a method to calculate the fibonacci numbers we need to implement the recursive equations:
F(2n) = F(n)*[2F(n+1) - F(n)] F(2n+1) = F(n+1)**2 + F(n)**2
First lets deal with the trivial cases. The first two numbers in the sequence are 1 and 1, so if we are given a number 1 or 2 then we just return 1:
def fib(k): if k<=2 : return 1 ...
The equation is in terms of doubled numbers (2n). So if we are given a number k, the n in the equations is actually half that. We then just work out the fibonacci numbers at position n and at position (n+1).
def fib(k): if k<=2 : return 1 else : n = k // 2 f = fib(n) f1 = fib(n + 1)
Given those we can do the appropriate one of the two possible calculations in terms of the values f and f1 and return the answer. We need to check whether the number we are working with is odd or even and we can do that just by taking the remainder when dividing by two and checking if it is 0 (meaning the number was even). That is done with the modulus operator. By storing the answer in a variable, we make sure we don't calculate the same answer multiple times.
def fib(k): if k<=2 : return 1 else : n = k // 2 f = fib(n) f1 = fib(n + 1) if ((k % 2) == 0) : return (f * (2*f1 - f)) else : return ((f1*f1) + (f*f))
Of course that hasn't yet answered our mole-rat question. To do that we need to note that our mole rat sequence starts at -1 so the year is two positions out from our n here.
def nakedMoleRat(year): return fib(year+2)
We then need to work out the total from our efficient algorithm to do that by jumping two further places in the sequence:
def totalNakedMoleRats (year): """An efficient divide and conquer way to compute the TOTAL number of naked mole-rats in the colony in the given year""" return nakedMoleRat (year + 2) - 1
Of course, if the Queen naked mole-rat dies young then the numbers won't get large enough to make this divide and conquer approach worthwhile. Let's hope she lives a long and fruitful life. With that we are done (for now) - though there are lots more variations on ways to calculate fibonacci numbers. Perhaps for example, you can think of a way to make recursive methods more efficient so they don't keep recomputing something that has already been computed!