Bioinformatics Stronghold - FIB: Rabbits and Recurrence Relations

Wascally Wabbits

1902年，斐波纳契的Leonardo提出了一个关于兔子群体繁殖的数学算式，他首先提出以下几个基本假设：

1. 第一个月，该群体只有一对新出生的兔子；

2. 一个月之后，兔子进入繁殖期；

3. 在之后的任何一个月，一只处在生殖期的兔子会与另一只处于生殖期的兔子交配；

4. 在两只兔子交配之后的一个月，它们生下了一只雌性和一只雄性兔子；

5. 兔子从不死亡，也从不停止繁殖。

Leonardo的算法是计算该兔子群体一年之后的数量。按照Leonardo的假设，第二个月兔子进入繁殖期，然后交配（一共一对兔子）；第三个月生下一对雌雄兔，然后再交配（一共两对兔子）；第四个月第一对兔子生下一对雌雄兔，然后再交配，之前的一对兔子成熟，进行交配（一共三对兔子）。。。到了一年后，该群体共144对雌雄兔。

The growth of Fibonacci's rabbit population for the first six month.

可能Leonardo对于兔子群体的假设有点牵强，但其在没有食肉动物的环境中还是有可能成立的。比如，19世纪中期，兔子被引进澳大利亚，然而澳大利亚本土并没有兔子的天敌。在接下来的50年里，兔子几乎摧毁了该大陆的许多植物物种，导致了澳大利亚生态系统不可逆的改变，使得澳大利亚原有的一些草原被破环，变得不在适合居住。

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 (π, -, 0, π) and the infinite sequence of odd numbers (1,3,5,7,9,…). We use the notation (记号) an to represent the n-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 Fn represents the number of rabbit pairs alive after the n-th month, then we obtain the Fibonacci sequence having terms Fn that are defined by the recurrence relation Fn = Fn-1 + Fn-2 (with F1 = F2 = 1 to initiate the sequence). Although the sequence bears Fibonacci's name, it was known to Indian mathematicians over two millennia ago.

When finding the n-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 n. 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 n≤40 and k≤5.

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

Sample Dataset

5 3

Sample Output

19

Solution

>>>

首先确定计算公式为Fn = Fn-1 + k * Fn-2，其中F1 = F2 = 1。n = 5和k＝3是给定的条件，a = 1和b = 1就是F1与F2，然后开始迭代就可以了。

Rosalind is a platform for learning bioinformatics and programming through problem solving. Take a tour to get the hang of how Rosalind works.