14天阅读挑战赛（趣学算法）笔记2

14天阅读挑战赛

神奇的兔子序列

假设第1个月有1对刚诞生的兔子，第2个月进入成熟期，第3个月开始生育兔子，而1对成熟的兔子每月会生1对兔子，兔子永不死去……那么，由1对初生兔子开始，12个月后会有多少对兔子呢？
兔子数列即斐波那契数列，它的发明者是意大利数学家列昂纳多•斐波那契（Leonardo Fibonacci，1170—1250）。1202年，他撰写了《算盘全书》（《Liber Abaci》）一书，该书是一部较全面的初等数学著作。书中系统地介绍了印度—阿拉伯数码及其演算法则，介绍了中国的“盈不足术”；引入了负数，并研究了一些简单的一次同余式组。

1.问题分析

第一个月：兔子1无繁殖能力，1对兔子
第二个月：兔子1进入成熟区，1对兔子
第三个月：兔子1生了1对兔子，2对兔子
第四个月：兔子1又生了一对兔子，兔子2不生，3对兔子
第五个月：兔子1生了一对兔子，兔子2生了1对兔子，5对兔子
…
上述分析可由下图表示为：

由上述分析可知：
当月的兔子数=上月的兔子数+上上月的兔子数
从而构成一组斐波那契数列。
斐波那契数列构成如下：
1，1，2，3，5，8，13，21，34，…
从第二个数开始有F(n)=F(n-1)+F(n-2)。

2.设计算法

下列算法按照递归思想进行：

int Fib(int n)
{
	if(n==1||n==2)
	return 1;
	return Fib(n-1)+Fib(n-2);
}
1
2
3
4
5
6

3.时间复杂度的分析

对于F(n)有：

左侧树高为h1=n-1，右侧树高为h2=n/2，高度为h2的部分是满二叉树，节点数为2^h2-1,即2n/2-1,由此可见，时间复杂度为指数阶。
对于爆炸增量函数，在算法设计中应尽量避开，因此需要对上述算法进行改进。

4.算法的改进

除去开头两项外，斐波那契数列的每一项都是前两项之和，若记录前两项的值，则只需进行一次加法运算即可，因此，可用数组代替实现。
如下代码：

int Fib(int n)
{
	int *F=new int[n];
	F[1]=1;
	F[2]=1;
	for(int i=3;i<=n;i++)
	F[i]=F[i-1]+F[i-2];
	return F[n];
1
2
3
4
5
6
7
8

该代码时间复杂度降到了多项式，且空间复杂度为O(n)。
对算法再做进一步的改进：

int Fib(int n)
{
	if(n==1||n==2)
	return 1;
	int s1=1,s2=1;
	for(int i=3;i<n;i++)
	{
		int tmp=s1+s2;
		s1=s2;
		s2=tmp;
	}
	return s2;
}
1
2
3
4
5
6
7
8
9
10
11
12
13

该算法的空间复杂度降到了O(1)。