Problem:
In the early 13th century the famed mathematician Fibonacci put forward a thought experiment about the population of rabbits, cute! ​He made a few assumptions about them:​
​
-
The population begins in the first month with a pair of newborn rabbits.
-
Rabbits reach reproductive age after one month.
-
In any given month, every rabbit of reproductive age mates with another rabbit of reproductive age.
-
Exactly one month after two rabbits mate, they produce one male and one female rabbit.
-
Rabbits never die or stop reproducing.
​
Although it sounds absurd, we will use it to model rabbit reproduction and population. But we will create a flexible model where rabbits can have as many offspring as they want (not just one) and where the population can be predicted after a certain number of months. You'll see what I mean!
​
Given: Positive integers n≤40 and k≤5k
​
Return: The total number of rabbit pairs that will be present after n months, if we begin with 1 pair and in each generation, every pair of reproduction-age rabbits produces a litter of k rabbit pairs (instead of only 1 pair)
​
Sample Dataset: 5 2
​
5 months and 2 offspring per adult rabbit
​
Sample Output: 11
Solution:
Before getting into the nitty gritty of programming, let's try to solve the sample problem with good old fashioned logic and see if we can come up with any patterns.
​
n = number of months
k = number of offspring an adult can have
​
So we start off with a newborn rabbit in the first month:
.png)
So after one month the newborn turns into an adult:
.png)
Now it can reproduce, we assume it can make 2 baby rabbits. So after three months:
.png)
So we follow the same pattern:
1. baby rabbits turn into adults
2. adults stay as adults and two baby rabbits
​
So after 4 months:
.png)
After 5 months:
.png)
So at the end of 5 months, where each adult has 2 offspring, we have 11 rabbits!
​
So you might have made a few observations:
-
A baby rabbit turns into an adult
-
An adult rabbit turns into one adult rabbit and two baby rabbits
​
We can now conclude that after one month, an adult rabbit transforms into one adult rabbit + k and all baby rabbits turn into adult rabbits alone.
So if we had 2 adult rabbits, after one month we would have 2 adult rabbits and 4 baby rabbits (number of adults * k).
​
Before generalizing this mathematical relationship, let's take n (months) = 5 and k (number of offspring) = 2:
< >
n = 5
​
k = 2
We will assume as the program starts with the first month and configure the baby as 1 and the parent as 0 (as can be seen in the first diagram):
< >
n = 5
​
k = 2
​
m_baby = 1
​
n_parent = 0
Then we code for converting baby rabbits into adults, and adults into adults and baby rabbits:
​
The number of baby rabbits = number of parents * k.
​
The number of parents = number of parents + number of babies
​
Refer back to the diagram if something doesn't make sense!
< >
n = 5
​
k = 2
​
n_baby = 1
​
n_parent = 0
​
for i in range(n-1):
n_baby, n_parent = n_parent * k, n_parent + n_baby
The above code iterates over the number of months.
There were 5 months but range(5) results in 0,1,2,3,4,5 which are 6 iterations, so range(n-1) is what we are looking for.
​
And finally we can add a print function and make the code a bit more user-friendly to input:
< >
def n_rabbits(n, k):
​
n_baby = 1
​
n_parent = 0
​
for i in range(n-1):
n_baby, n_parent = n_parent * k, n_parent + n_baby
​
return(n_baby + n_parent)
​
n_rabbits(5, 2)
Whew! Breeding like rabbits sure sounds like a lot of work.
Output:
11
Copy and paste the output you get from running your code on the sample data onto the Rosalind answer terminal and submit. Annnd get yourself a cookie!