本文主要是介绍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 1else:return fibonacci_digui(month - 1) + fibonacci_digui(month - 2)
# 迭代
def fibonacci_diedai(month):a, b = 0, 1for _ in range(month-1):a, b = b, a + breturn 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 1else:return (rabbit_born_digui(month - 1, produce)) + (rabbit_born_digui(month - 2, produce) * produce)def rabbit_born_diedai(month, produce):a, b = 0, 1for _ in range(month - 1):a, b = b * produce, a + breturn b
同时对于递归和迭代两种方法,迭代会更快,我们通过下面一段代码进行检验:
import time
def rabbit_born_digui(month, produce):if month == 1 or month == 2:return 1else:return (rabbit_born_digui(month - 1, produce)+ rabbit_born_digui(month - 2, produce) * produce)def rabbit_born_diedai(month, produce):a, b = 1, 1for _ in range(month - 2):a, b = b, a * produce + breturn bdef main():month = 30 # 可以调整这个值来测试较大的 monthproduce = 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 = 1else:result = rabbit_born_digui_memo(month - 1, produce, memo) + rabbit_born_digui_memo(month - 2, produce, memo) * producememo[month] = resultreturn resultdef rabbit_born_diedai(month, produce):if month == 1 or month == 2:return 1dp = [0] * (month + 1)dp[1], dp[2] = 1, 1for i in range(3, month + 1):dp[i] = dp[i - 1] + dp[i - 2] * producereturn dp[month]def main():month = 78 # 可以调整这个值来测试较大的 monthproduce = 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()
![在这里插入图片描述](https://img-blog.csdnimg.cn/direct/831767a7ee8f4ecca69403a0d01642d6.png
加入Rosalind,开始你的生物信息学探索之旅吧!
纸上得来终觉浅,绝知此事要躬行。
公众号:BIoYfan,之后会坚持同步更新生信方面内容
与君共勉💪
这篇关于Bio-Info 每日一题:Rosalind-04-Rabbits and Recurrence Relations的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!