Programming Puzzle 1 Solutions Part 5: new naked mole-rats

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!