What's the right transition equation of this problem?

user_9428398 0
Viewed 73

For every mouse, it takes two months for them to become mature after birth, then they are able to give birth to baby mouses. A mature mouse can give birth to 12 baby mouses every month. We have one mouse initially, and what's the total numebr of mouse after ten months? My transition equation is F(n) = F(n-1) + 12 * F(n-2), but my classmate told me this is not right. So what's the right equation of this question?

recurrence dynamic-programming algorithm
3 Answers

Your transition equation needs to be a matrix (3x3) so that given 3 states as a vector (newborn, 1m old, 2m+ old) gives you new vector of new states after 1m. Logic to build such matrix is similar as your reasoning.

new_state = matrix * current_state

EDIT:

matrix that we build represents 3 linear equations.

# abbreviations
ns = new state
nb = newborn
1m = 1 month old
2m = 2 mounts old or more
cs = current state
mXX = matrix index

# 3 scalar questions from matrix eqution ->
# ns = matrix * cs 
ns_nb = m00 * cs_nb + m01 * cs_1m + m02 * cs_2m
ns_1m = m10 * cs_nb + m11 * cs_1m + m12 * cs_2m
ns_2m = m20 * cs_nb + m21 * cs_1m + m22 * cs_2m

Now you need to figure out what m00 - m22 are based on your requrements

user_1310570

Enlightened by answer by Luka above, I figure out these coefficients

ns_nb = 12 * cs_2m + 12 * cs_1m

ns_1m = cs_nb

ns_2m = cs_2m + cs_1m

user_94283980

From the posts of Luka Rahne and KningTG,

I think the python code below will work fine for the problem using dynamic programming:

# Initial Conditions
new_born = 1
one_month_old = 0 
mature_mouse = 0 

n = 10  # Month upto which we want to find
i = 1 

while(i<n):
    
    # Finding updated new value
    new_born_update = 12*(one_month_old+mature_mouse)
    one_month_old_update = new_born
    mature_mouse_update = one_month_old + mature_mouse

    # Updating values
    new_born,one_month_old,mature_mouse = new_born_update,one_month_old_update,mature_mouse_update
    
    i = i + 1
    
# Calculating the total number of mouses for month n
Total_mouses = new_born+one_month_old+mature_mouse

# Printing total number of mouses
print(Total_mouses)
user_136519780
Related