兔子生兔子问题详解(斐波那契数列)





有一只兔子,从出生后第3个月起每个月都生一只兔子,小兔子长到第三个月后每个月又生一只兔子,假如兔子都不死,问每个月的兔子总数为多少?

斐波那契数列(Fibonacci sequence),又称黄金分割数列、因数学家列昂纳多·斐波那契(Leonardoda Fibonacci)以兔子繁殖为例子而引入,故又称为“兔子数列”,指的是这样一个数列:1、1、2、3、5、8、13、21、34、……在数学上,斐波那契数列以如下被以递推的方法定义:F(1)=1,F(2)=1, F(n)=F(n - 1)+F(n - 2)(≥ 3,∈ N*)在现代物理、准晶体结构、化学等领域,斐波纳契数列都有直接的应用,为此,美国数学会从 1963 年起出版了以《斐波纳契数列季刊》为名的一份数学杂志,用于专门刊载这方面的研究成果。

这个问题可能我比较笨,看大多数解释都是一句话,f(n) = f(n-1) + f(n-2),但是总有点想不明白这个。列了个表格才看清楚咋回事。

月份 1 2 3 4 5 6 7
兔子总数 1 1 2 3 5 8 13
具有生育能力兔子 0 0 1 1 2 3 5

如果这个月是第n个月,那要求这个月兔子的总数,其实就是上个月的兔子总数加上新生出来的兔子。也就是f(n) = f(n-1) + x。这个x是比较难理解的地方。那这个月到底新生出来多少兔子呢?这就是求这个月已经有生育能力的兔子是多少,上上个月所有的兔子就是这个月所有的有生育能力的兔子,这里可以结合表格推一推就很好理解了。所以x就是f(n-2)。

因此可以得到递推f(n) = f(n-1) + f(n-2)。

其实比较简单的问题,不过自己光凭笨脑子想,突然没想明白,记一下这个思考过程。

还有就是牛客网上的高赞答案详解:

有人是以a表示一个月的兔子,b表示两个月的兔子,c表示三个月的兔子(原文这么注释的),我因为这个注释半天没看懂,后来明白了,c意思是已经成熟的兔子,也就是表示3个月及以上的兔子,也就是说c表示能生兔子的兔子。

那就可以以月份循环,每到达新的一个月,b都会成熟,所以c+=b,c就更新了,仍然表示所有成熟了的兔子,b怎么更新呢?b其实就是上个月那些成熟度是1个月的兔子,所以再更新b,用b=a;a呢?a就是现在更新后的c,因为更新后的c表示这个月成熟了的兔子,那这些兔子都会生一只新的兔子,新兔子就是成熟度为1个月的,所以用a=c。这样现在这个月的兔子总数就是a+b+c。

这是我自己没找到注释,自己总结出来的答案详解,这个方法比递归复杂度低,空间占用更是比用数组先去存要少很多。

参考链接


发布者

默默

默默码农

发表评论

电子邮件地址不会被公开。 必填项已用*标注