04 Rabbits and Recurrence Relations
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 (π,−2–√,0,π)(π,−2,0,π) and the infinite sequence of odd numbers (1,3,5,7,9,…)(1,3,5,7,9,…). We use the notation anan to represent the nn-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 FnFn represents the number of rabbit pairs alive after the nn-th month, then we obtain the Fibonacci sequence having terms FnFn that are defined by the recurrence relation Fn=Fn−1+Fn−2Fn=Fn−1+Fn−2 (with F1=F2=1F1=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 nn-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 nn. 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≤40n≤40 and k≤5k≤5.
Return: The total number of rabbit pairs that will be present after nn months, if we begin with 1 pair and in each generation, every pair of reproduction-age rabbits produces a litter of kk rabbit pairs (instead of only 1 pair).
Sample Dataset
5 3
Sample Output
19 注: F1 = 1, F2 = 1, F3 = F2+F1*2,
这里k=3, 所以手写答案为 1,1,4,7,
方法一: def fibonacciRabbits(n, k):
F = [1, 1]
generation = 2
while generation <= n:
F.append(F[generation - 1] + F[generation - 2] * k)
generation += 1
return (F[n-1]) print fibonacciRabbits(5, 3) 方法二: def fibonacciRabbits(n,k):
if n <= 2:
return (1)
else:
return (fibonacciRabbits(n-1,k) + fibonacciRabbits(n-2,k)*k)
print fibonacciRabbits(5,3)
最新文章
- 【DS】About Stack
- go 数据类型转换
- Install MySQL on CentOS 7
- GDB配置与.gdbinit的编写
- python基础知识4——collection类——计数器,有序字典,默认字典,可命名元组,双向队列
- 重构Web Api程序(Api Controller和Entity)续篇
- jquery ajax error函数详解
- Paxos算法 Paxos Made Simple
- IDF 实验室部分题目WriteUp
- flume-agent实例
- codeigniter 该脚本在运行300s超时退
- 菜鸟的Xamarin.Forms前行之路——按钮的按下抬起事件的监控(可扩展至其他事件)
- netty基本用法
- 面试被问之-----sql优化中in与exists的区别
- socket keepalive理解
- 2-STM32物联网开发WIFI(ESP8266)+GPRS(Air202)系统方案数据篇(数据库简单说明)
- 【转】android:paddingLeft与android:layout_marginLeft的区别
- 1. RNN神经网络模型原理
- pandoc 基本使用
- python中常用的内建模块