2022-11-19 【生信】Mortal Fibonacci Rabbits

ROSALIND | Mortal Fibonacci Rabbits

“
Problem

img

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.

Sample Dataset
6 3
Sample Output
4

思考

这道题是对之前兔子繁殖那道题的升级

感觉很难

想到是不是构建一个兔子类，创建兔子实例，然后规定多久进入繁殖，多久死？

尝试了一下，没弄出来

试一下传统递归办法

想了半天，不行

或许可以建立三个list

总感觉可以做出来，但是是真做不出来，看答案吧。

本来想放弃了，但是在等待答案的过程中又试了一下

我的解法

class Rabbit():
    __slots__ = ["lifespan", "age"]
    def __init__(self, lifespan):
        self.lifespan = lifespan
        self.age = 1
    def growUp(self):
        self.age += 1

    def death(self):
        if self.age > self.lifespan:
            return True
        return False

    def produce(self):
        if self.age > 2:
            return True
        return False

months = 6
lifespan = 3

totalRabbits = []
rabbit = Rabbit(lifespan)
totalRabbits.append(rabbit)

def rabbitSeason(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)

rabbitSeason(months,lifespan)
print(len(totalRabbits))

可以看到，我用的是定义 Rabbit 类，然后创建实例的方法。

没有用到递归，我是从正向开始一天一天的判断

同时为了减少创建大量实例的内存占用，我还查到了使用 __slots__ 降低内存占用

8.4 创建大量对象时节省内存方法 — python3-cookbook 3.0.0 文档

“
8.4 创建大量对象时节省内存方法

问题

你的程序要创建大量(可能上百万)的对象，导致占用很大的内存。

解决方案

对于主要是用来当成简单的数据结构的类而言，你可以通过给类添加 __slots__ 属性来极大的减少实例所占的内存。比如：
class Date:
 __slots__ = ['year', 'month', 'day']
 def __init__(self, year, month, day):
     self.year = year
     self.month = month
     self.day = day
当你定义 __slots__ 后，Python就会为实例使用一种更加紧凑的内部表示。实例通过一个很小的固定大小的数组来构建，而不是为每个实例定义一个字典，这跟元组或列表很类似。在 __slots__ 中列出的属性名在内部被映射到这个数组的指定小标上。使用slots一个不好的地方就是我们不能再给实例添加新的属性了，只能使用在 __slots__ 中定义的那些属性名。

但是的但是，最终因为这行代码的逻辑过于复杂，导致运行效率低下，

基本months设置成50左右，就需要等1-3min以上才能计算出结果了。

简单试了一下, months = 87, lifespan = 16 10min都没算出结果，估计可能要几个小时才能算完

所以最后我也没能答出来。

提示

浪费了三次机会之后，我去看了社区里的提示，有人找到规律如下

“

# m=3   [1, 1, 2, 2, 3, 4, 5, 7, 9, 12]        f(n) = f(n-2) + f(n-3)
# m=4   [1, 1, 2, 3, 4, 6, 9, 13, 19, 28]      f(n) = f(n-2) + f(n-3) + f(n-4)
# m=5   [1, 1, 2, 3, 5, 7, 11, 17, 26, 40]     f(n) = f(n-2) + f(n-3) + f(n-4) + f(n-5)
# m=6   [1, 1, 2, 3, 5, 8, 12, 19, 30, 47]     f(n) = f(n-2) + f(n-3) + f(n-4) + f(n-5) + f(n-6)
# m=7   [1, 1, 2, 3, 5, 8, 13, 20, 32, 51]     f(n) = f(n-2) + f(n-3) + f(n-4) + f(n-5) + f(n-6) + f(n-7)

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?

Thanks.

2022-11-24 当天试了很多次，然后遇到一些事情，搁置了几天

这道题一直没做出来（真的没脸说）

果然还是太菜了

决定上B站抄答案

【ROSALIND】【练Python，学生信】11 斐波那契数列与兔子繁殖问题之会死的兔子 - 哔哩哔哩 (bilibili.com)

https://www.bilibili.com/read/cv2017126

当时就是这个up主分享的Rosalind，可贵的是几年过去了，他也还在做这上面的题

总之我参考了他的解法

# 参考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)

print(f[n])

这里的 i 我理解的应该是从第 i 个月开始算

n 代表当前月，也就是你要计算的月份数

m 兔子可以活的月份数

总而言之，递归还是很难的。

别人的解法

终于来到这一part了，我当时抓耳挠腮想不出来，真心很想看大神们是怎么解的

ROSALIND | Solutions | Mortal Fibonacci Rabbits

#!/usr/bin/env python
def fib(n,k=1):
  ages = [1] + [0]*(k-1)
  for i in xrange(n-1):
    ages = [sum(ages[1:])] + ages[:-1]
  return sum(ages)

Python xrange() 函数 | 菜鸟教程 (runoob.com)

“
描述

xrange() 函数用法与 range 完全相同，所不同的是生成的不是一个数组，而是一个生成器。

语法

xrange 语法：
xrange(stop)
xrange(start, stop[, step])
参数说明：

start: 计数从 start 开始。默认是从 0 开始。例如 xrange(5) 等价于 xrange(0， 5)

stop: 计数到 stop 结束，但不包括 stop。例如：xrange(0， 5) 是 [0, 1, 2, 3, 4] 没有 5

step：步长，默认为1。例如：xrange(0， 5) 等价于 xrange(0, 5, 1)

返回值

返回生成器。

#!/usr/bin/python
#Mortal Fib
n=88
k=16
f=[1]*100
for i in xrange(2,n):
  f[i]=f[i-1]+f[i-2]
  if i>=k:
    f[i]-=f[(i-k)-1]  
print f[i]

尝试理解

我把第一个的代码改了一下，这样断点调试的时候运行起来好理解一点

def fib(n,k=1):
  ages = [1] + [0]*(k-1)
  for i in range(n-1):
      sums = [sum(ages[1:])]
      addition = ages[:-1]
      ages = sums + addition
  return sum(ages)
print(fib(6, 3))

用断点调试运行了几次上面的代码

大概理解了这个函数是怎么运行的了

先根据兔子能够存活的月数，创建一个 ages 的list

比如说输入 6, 3

那么初始的ages = [1, 0, 0]

根据上面提示的公式，当兔子存活月数是3个月的时候，当月兔子总数的计算公式 f(n) = f(n-2) + f(n-3)

然后接下来就看他怎么计算当月兔子数的

  for i in range(n-1):
      sums = [sum(ages[1:])]
      addition = ages[:-1]
      ages = sums + addition

这一段代码的意思大概就是，把 i 月出生的兔子放在 ages 列表中 index=0 的位置，index=1 放的是上个月出生的，也就是可以开始繁殖的，index=3 放的是下个月就会死掉的兔子

随着for循环的进行，不断地会把 index=3 的兔子数挤掉，

单为什么 i 到 n-2 就停了，这个我还没想明白，希望有大神可以解答一下？