Fibonacci 问题

这个问题很经典,相关的讨论和研究也算是很成熟了。它是算法问题的典型素材,仍然非常值得在此记录和思考——即使是重复别人的思考。

来源

传说 Fibonacci 研究过这个假定的兔子繁殖问题:

  1. 月初有一对刚出生的兔子
  2. 兔子出生两月后开始生育,每月都生一次,每次都生一对
  3. 兔子万寿无疆(不会死去)

到某月的兔子数量是多少呢?

假设第 n 月的兔子数量是 f(n), 则该月的兔子总数为上月的兔子数加上新生的兔子数,上月的兔子数就是 f(n-1),而新生的兔子数是多少?本月新生兔子数,即上月的成熟兔子数,上月的成熟兔子数,即上上月的兔子总数,即 f(n-2)

即可得到公式: f(n)=f(n-1)+f(n-2)

衍生数列:每月新增兔子数量。

简单用代码实现求 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);
    }

完整的可运行的代码参这里

参考:

维基百科的《Fibonacci 数列

百度Hi空间的《奇妙的 Fibonacci 数列