java面试常用算法题深入剖析之兔子繁殖问题

时间:2022-12-04 11:24:16

1.背景

突发奇想的想补充下java算法中的知识,于是网上百度,java面试常用的的算法,千篇一律的很多都是直接copy题,然后后面补充答案,详细解答都没有,于是萌生往深入思考的想法,并且记录下来。

2.兔子繁殖问题

有一对兔子,从出生后第3个月起每个月都生一对兔子,小兔子长到第三个月后每个月又生一对兔子,假如兔子都不死,问每个月的兔子总数为多少?  简单介绍下问题背景 ,意大利的意味著名的数学家斐波那契在算盘全集中提出的该问题,后人把各个月份兔子数量称为“斐波那契数列”。 

3.分析问题,得出结论

java面试常用算法题深入剖析之兔子繁殖问题

4.代码实现

1.递归思想

    递归思想,无疑对于解决这种 子生孙,孙生子问题 起到重要作用。 java面试常用算法题深入剖析之兔子繁殖问题 分析:递归算法固然能实现,但是对于数据量比较大时候,运算速度大大降低,并且还只能用long 类型接收,int类型已不能满足。 java面试常用算法题深入剖析之兔子繁殖问题 弊端上面步骤可知,每次计算都会重复计算好多次,造成内存开销大,计算时间长

2.迭代实现

java面试常用算法题深入剖析之兔子繁殖问题

 分析:计算量比较小,按照从前往后的表达出来 f(n-2),f(n-1) 便于直接表达出f(n),算是递归算法的优化算法   适用范围:大数据量可以实现