文章目录
题目解题思路代码(三种方法实现)题目
最开始有一对小兔子,一个月后成熟。第二个月,母兔妊娠,第三个月,生一对小兔。小兔也花一个月成熟,然后,如同它们的父母,从第三个月开始每月生一对小兔。第n个月共有多少对兔子。
解题思路
看图大概可以知道该题目符合斐波那契数列。以下分析为什么符合斐波那契数列。
第一个月有一对小兔子,数量为1对;
第二个月小兔子长成大兔子,数量为1对;
前两个月属于初始条件,从第三个月开始出现规律。
第n月兔子的对数 = 第(n - 1)月兔子的对数 + 第n月新出生的小兔子对数;
第n月新出生的小兔子的对数= 第(n - 1)月大兔子的对数;
第(n - 1)月大兔子的对数= 第(n - 2)月大兔子的对数 + 第(n - 2)月小兔 子对数(小兔子经过一个月长成大兔子);
即,第n月新出生的小兔子的对数 = 第(n - 1)月大兔子的对数 = 第(n - 2)月兔子对数;
所以,第n月兔子的对数 = 第(n - 1)月兔子的对数 + 第(n - 2)月兔子的对数;
以5月为例:
第5月兔子对数 = 第4月兔子对数 + 第5月新出生的小兔子对数;
第5月新出生的小兔子对数 = 第4月大兔子对数;
第4月大兔子对数 = 第3月大兔子对数 + 第3月小兔子对数( 第4月长成大兔子);
即,第5月新出生的小兔子对数 = 第4月大兔子对数 = 第3月所有兔子对数;
所以第5月兔子对数 = 第4月兔子对数 + 第3月兔子对数;
代码(三种方法实现)
public class Demo {public static void main(String[] args) {int n;Scanner sc = new Scanner(System.in);System.out.println("input n:");n = sc.nextInt();//递归long begin = System.currentTimeMillis();System.out.println("递归:" + Fib(n));long end = System.currentTimeMillis();System.out.println("递归用时:" + (end - begin));//数组long[] fib = new long[n];fib[0] = fib[1] = 1;begin = System.currentTimeMillis();for (int i = 2; i < n; i++) {fib[i] = fib[i - 1] + fib[i - 2];}end = System.currentTimeMillis();System.out.println("数组:" + fib[n - 1]);System.out.println("数组用时:" + (end - begin));//三个变量long a = 1, b = 1, c;begin = System.currentTimeMillis();while(n > 2) {c = a + b;a = b;b = c;n--;}end = System.currentTimeMillis();System.out.println("三个变量" + b);System.out.println("三个变量用时:" + (end - begin));}public static long Fib(long n) {if (n == 1 || n == 2) {return 1;} else {return Fib(n - 1) + Fib(n - 2);}}}
运行结果: