序列是一组有序对象的集合,它有如下特征:
递推关系是一种用来定义序列的方法,可以通过前面的项,推导出后面的项。如斐波那契兔子问题,某月的兔子数,等于上一个月的兔子数,加上新生的兔子数;一个关键的现象是,因为新生的兔子要隔一代才有繁殖能力,所以某月新生的兔子数等于两个月前的兔子数。因此某月的兔子数可以通过下面的公式描述:
Fn = Fn-1 + Fn-2(F1=F2=1)
这便是递推。由递推启发的动态规划思想,是生物信息学中许多比对软件的算法基础。
给定:正整数 n 和 k。
需得:经过 n 个月后总共有多少对兔子。假定从一对兔子开始,每一代每对成年兔子生 k 对小兔子(不是一对)。
5 3
19
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))
解本题的关键是要理解:
本题用了两种方式解决,递推与递归,两者的区别是:
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).
5 3
19