Figure 4. A figure illustrating the propagation of Fibonacci's rabbits if they die after three months.
Recall the definition of the Fibonacci numbers from “Rabbits and Recurrence Relations”, which followed the recurrence relation Fn=Fn−1+Fn−2Fn=Fn−1+Fn−2 and assumed that each pair of rabbits reaches maturity in one month and produces a single pair of offspring (one male, one female) each subsequent month.
Our aim is to somehow modify this recurrence relation to achieve a dynamic programming solution in the case that all rabbits die out after a fixed number of months. See Figure 4 for a depiction of a rabbit tree in which rabbits live for three months (meaning that they reproduce only twice before dying).
Given: Positive integers n≤100n≤100 and m≤20m≤20.
Return: The total number of pairs of rabbits that will remain after the nn-th month if all rabbits live for mm months.
defrabbitSeason(months, lifespan): for month in range(1, months): temp = [r for r in totalRabbits] for rab in temp: rab.growUp() if rab.produce(): newRabbit = Rabbit(lifespan) totalRabbits.append(newRabbit) if rab.death(): totalRabbits.remove(rab)
I found this rule in this problem, but I'm not sure that I will always lucky. Can I ask whether there is any principle to finding a rule for sequence of numbers?
# 参考B站上的解法 # 作者:未琢 https://www.bilibili.com/read/cv2017126 出处:bilibili i = 3 n = 6 m = 3 f = [0, 1, 1] s = 0 while i <= n: if i <= m: s = f[i-1] + f[i-2] elif i == m+1: s = f[i-1] + f[i-2] - 1 elif i > m+1: s = f[i-1] + f[i-2] - f[i-m-1] i += 1 f.append(s)