Bio-Info 每日一题：Rosalind-04-Rabbits and Recurrence Relations

🎉 进入生物信息学的世界，与Rosalind一起探索吧！🧬
Rosalind是一个在线平台，专为学习和实践生物信息学而设计。该平台提供了一系列循序渐进的编程挑战，帮助用户从基础到高级掌握生物信息学知识。无论你是初学者还是专业人士，Rosalind都能为你提供适合的学习资源和实践机会。网址：https://rosalind.info
你是否想像专业人士一样分析DNA序列？这里有一个简单的任务来帮助你入门。
📝 任务说明:
请添加图片描述

斐波那契数列（Fibonacci sequence），又称黄金分割数列，因数学家莱昂纳多·斐波那契（Leonardo Fibonacci）以兔子繁殖为例子而引入，故又称“兔子数列”。其数值为：1、1、2、3、5、8、13、21、34……在数学上，这一数列以如下递推的方法定义：F(0)=0，F(1)=1, F(n)=F(n - 1)+F(n - 2)（n ≥ 2，n ∈ N*）。
假设每对兔子生育时只生下一对小兔子，生下的小兔子用一个月时间成熟，在生下来的第二个月长成大兔子，在第三个月又能够生一对小兔子。如此循环往复，且在这个过程中所有兔子不会死。
以上是简化的斐波那契数列，根据给出的求和公式我们可以较为轻松地写出代码：

def fibonacci_digui(month):
    if month == 1 or month == 2:
        return 1
    else:

        return fibonacci_digui(month - 1) + fibonacci_digui(month - 2)
# 迭代
def fibonacci_diedai(month):
    a, b = 0, 1
    for _ in range(month-1):
        a, b = b, a + b
    return b

但是在这个问题中，给了两个参数 n 和 k。n 代表月份数，k 代表每对兔子每次生下的小兔子对数（k≤5）。要求计算在 n（n≤40）月之后的兔子对数。。

示例：

请添加图片描述

我们可以简单分析一下：第一个月是1对，第二月也是1对，第三个月是3对，第四个月是7对，第五个月是19对。为了方便表示后面我们就用 F(n) 表示对应月份的兔子数量。可以将兔子分成老兔子和新兔子，其中老兔子数量是上个月的数量，新兔子是成熟的兔子生的。

F(1)=1
F(2)=1
F(3)=1+(1*3)=F(2)+F(1)*3
F(4)=1*3+3=F(3)+F(2)*3
......
这样我们又能推导出一个公式，以此为依据写代码会方便不少

这样我们就能推导出一个公式，以此为依据写代码会方便不少。
因为兔子需要一个月的时间长大，所以这个月的兔子数量等于上个月数量加上 k 倍的前个月数量（前个月的兔子这个月可以生）。
请添加图片描述

解答：

def rabbit_born_digui(month, produce):
    if month == 1 or month == 2:
        return 1
    else:
        return (rabbit_born_digui(month - 1, produce)) + (
            rabbit_born_digui(month - 2, produce) * produce
        )

def rabbit_born_diedai(month, produce):
    a, b = 0, 1
    for _ in range(month - 1):
        a, b = b * produce, a + b
    return b

同时对于递归和迭代两种方法，迭代会更快，我们通过下面一段代码进行检验：

import time
def rabbit_born_digui(month, produce):
    if month == 1 or month == 2:
        return 1
    else:
        return (
            rabbit_born_digui(month - 1, produce)
            + rabbit_born_digui(month - 2, produce) * produce
        )

def rabbit_born_diedai(month, produce):
    a, b = 1, 1
    for _ in range(month - 2):
        a, b = b, a * produce + b
    return b

def main():
    month = 30  # 可以调整这个值来测试较大的 month
    produce = 3
    # 测试递归实现的运行时间
    start_time = time.time()
    result_recursive = rabbit_born_digui(month, produce)
    end_time = time.time()
    print(
        f"递归实现：第{month}个月后共有 {result_recursive} 对兔子，运行时间：{end_time - start_time:.5f} 秒"
    )
    # 测试迭代实现的运行时间
    start_time = time.time()
    result_iterative = rabbit_born_diedai(month, produce)
    end_time = time.time()
    print(
        f"迭代实现：第{month}个月后共有 {result_iterative} 对兔子，运行时间：{end_time - start_time:.5f} 秒"
    )

if __name__ == "__main__":

    main()

在这里插入图片描述
请添加图片描述

题外话

让GPT帮忙改了改代码，用记忆化递归和动态规划两种方法实现，之前的递归方法当月份设置到七八十的时候就已经很吃力了，结果这两种方法依旧是丝滑运行。

import time
def rabbit_born_digui_memo(month, produce, memo=None):
    if memo is None:
        memo = {}
    if month in memo:
        return memo[month]
    if month == 1 or month == 2:
        result = 1
    else:
        result = rabbit_born_digui_memo(month - 1, produce, memo) + rabbit_born_digui_memo(month - 2, produce, memo) * produce
    memo[month] = result
    return result
  
def rabbit_born_diedai(month, produce):
    if month == 1 or month == 2:
        return 1
    dp = [0] * (month + 1)
    dp[1], dp[2] = 1, 1
    for i in range(3, month + 1):
        dp[i] = dp[i - 1] + dp[i - 2] * produce
    return dp[month]

def main():
    month = 78  # 可以调整这个值来测试较大的 month
    produce = 3
    # 测试记忆化递归实现的运行时间
    start_time = time.time()
    result_recursive_memo = rabbit_born_digui_memo(month, produce)
    end_time = time.time()
    print(f"记忆化递归实现：第{month}个月后共有 {result_recursive_memo} 对兔子，运行时间：{end_time - start_time:.5f} 秒")

    # 测试动态规划实现的运行时间
    start_time = time.time()
    result_iterative = rabbit_born_diedai(month, produce)
    end_time = time.time()
    print(f"动态规划实现：第{month}个月后共有 {result_iterative} 对兔子，运行时间：{end_time - start_time:.5f} 秒")

if __name__ == "__main__":

    main()