这个问题很经典，相关的讨论和研究也算是很成熟了。它是算法问题的典型素材，仍然非常值得在此记录和思考——即使是重复别人的思考。
传说 Fibonacci 研究过这个假定的兔子繁殖问题：
假设第 $n$ 月的兔子数量是 $f(n)$, 则该月的兔子总数为上月的兔子数加上新生的兔子数，上月的兔子数就是 $f(n-1)$，而新生的兔子数是多少？本月新生兔子数，即上月的成熟兔子数，上月的成熟兔子数，即上上月的兔子总数，即 $f(n-2)$
即可得到公式： $f(n)=f(n-1)+f(n-2)$
衍生数列：每月新增兔子数量。
| 时间（月） | 新生兔子数(对) | 成熟兔子数(对) | 兔子总数(对) |
|---|---|---|---|
| 1 | 1 | 0 | 1 |
| 2 | 0 | 1 | 1 |
| 3 | 1 | 1 | 2 |
| 4 | 1 | 2 | 3 |
| 5 | 2 | 3 | 5 |
| 6 | 3 | 5 | 8 |
简单用代码实现求 f(n) 的代码如下：
public int fibonnaci(int i) {
if (i < 0)
return 0;
if (i == 1 || i == 2)
return 1;
return fibonnaci(i - 1) + fibonnaci(i - 2);
}
完整的可运行的代码参这里。
还可以利用Java Stream的功能实现一个Fibonacci数列生成器
| 1 | 1 | 2 | 3 | 5 | 8 | 13 | 21 | 34 | |
|---|---|---|---|---|---|---|---|---|---|
| round 1 | i | j | |||||||
| round 2 | i | j | |||||||
| round 3 | i | j | |||||||
| … |
如上表，i的序列即是Fibonacci数列，
class FibSupplier implements LongSupplier {
private long i = 1, j = 1;
public long getAsLong() {
long k = i;
i = j;
j = k + j;
return k;
}
}
调用语句如下：
LongStream fib = LongStream.generate(new FibSupplier());
fib.limit(10).forEach(System.out::println);
完整的可运行的代码参这里。
这是廖雪峰讲解Stream时提到的一种解法。
参考：