兔子繁衍 斐波那契数列 古典问题 java

兔子繁衍 斐波那契数列 古典问题 java

问题

古典问题：有一对兔子，从出生后第3个月起每个月都生一对兔子，小兔子第三个月开始每个月又生一对兔子， 假如兔子都不死，问每个月的兔子总数为多少？

分析

根据题意可知

1，1，2，3，5，8， 13， 21...

这是斐波那契数列，也就是说从第三项起每一项都是前两项的和

递归法

时间复杂度很大，有些数会被重复算很多次

	private static int recursion(int month) {if(month <= 2) {	return 1;}return recursion(month - 1) + recursion(month - 2);}

循环法

相比于递归法，效率高很多

private static long add(int month) {if(month <= 2) {	return 1;}long ago = 1;long result = 1;for(int i = 3; i <= month; i++) {result += ago;ago = result - ago;}return result;}

总结

递归法属于从需求项向前推算，导致很多项被重复计算，就算将重复计算存起来复用，又会占很多空间，这种情况可以考虑从第一项往后推到需求项。