生物信息学算法之 Python 实现|Rosalind 刷题笔记：007 兔子问题和递推

序列是一组有序对象的集合，它有如下特征：

1. 序列内元素可以重复；
2. 序列可以是有限的，也可以是无限的。

递推关系是一种用来定义序列的方法，可以通过前面的项，推导出后面的项。如斐波那契兔子问题，某月的兔子数，等于上一个月的兔子数，加上新生的兔子数；一个关键的现象是，因为新生的兔子要隔一代才有繁殖能力，所以某月新生的兔子数等于两个月前的兔子数。因此某月的兔子数可以通过下面的公式描述：

Fn = Fn-1 + Fn-2（F1=F2=1）

这便是递推。由递推启发的动态规划思想，是生物信息学中许多比对软件的算法基础。

给定：正整数 n 和 k。

需得：经过 n 个月后总共有多少对兔子。假定从一对兔子开始，每一代每对成年兔子生 k 对小兔子（不是一对）。

示例数据

5 3

示例结果

19

Python 实现

Rabbits_and_Recurrence_Relations.py

import sys

def fib(n, k):
    f = [1] * n
    for i in range(2, n):
        f[i] = f[i-1] + f[i-2] * k
    return f[n-1]

def fib2(n, k):
    return 1 if n < 3 else fib(n-1, k) + fib(n-2, k)*k

def test():
    return fib(5, 3) == 19 and fib2(5, 3) == 19

if __name__ == '__main__':
    if not test():
        print("fib: Failed")
        sys.exit(1)
    print(fib(35, 3))

解本题的关键是要理解：

1. 本月的兔子数 = 上月的兔子数 + 新生的兔子数
2. 由于兔子要隔一代才能繁殖，因此上月的新生兔子，在本月不繁殖，有繁殖能力的是上上月的兔子，并且要乘以繁殖系数 k。

本题用了两种方式解决，递推与递归，两者的区别是：

1. 递推：从已知到未知，从小到大；就本题来说，就是以第 1，2 个月为基础，逐步推导出后续每一个月的兔子数。
2. 递归：从未知到已知，从大到小。就本题来说，要计算某月的兔子数，先计算前面两个月的兔子数，如此循环，直到把任务都分解成计算第 1，2 个月的兔子数，而这两个月的兔子数是已知的。

Problem

A sequence is an ordered collection of objects (usually numbers), which are allowed to repeat. Sequences can be finite or infinite. Two examples are the finite sequence and the infinite sequence of odd numbers . We use the notation to represent the -th term of a sequence.

A recurrence relation is a way of defining the terms of a sequence with respect to the values of previous terms. In the case of Fibonacci's rabbits from the introduction, any given month will contain the rabbits that were alive the previous month, plus any new offspring. A key observation is that the number of offspring in any month is equal to the number of rabbits that were alive two months prior. As a result, if represents the number of rabbit pairs alive after the -th month, then we obtain the Fibonacci sequence having terms that are defined by the recurrence relation (with to initiate the sequence). Although the sequence bears Fibonacci's name, it was known to Indian mathematicians over two millennia ago.

When finding the -th term of a sequence defined by a recurrence relation, we can simply use the recurrence relation to generate terms for progressively larger values of . This problem introduces us to the computational technique of dynamic programming, which successively builds up solutions by using the answers to smaller cases.

Given: Positive integers and .

Return: The total number of rabbit pairs that will be present after months, if we begin with 1 pair and in each generation, every pair of reproduction-age rabbits produces a litter of rabbit pairs (instead of only 1 pair).

Sample Dataset

5 3

Sample Output

19