IT Notes‎ > ‎Algorithms‎ > ‎

Fibonacci 问题

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

来源
传说 Fibonacci 研究过这个假定的兔子繁殖问题:
  1. 月初有一对刚出生的兔子
  2. 兔子出生两月后开始生育,每月都生一次,每次都生一对
  3. 兔子万寿无疆(不会死去)
到某月的兔子数量是多少呢?
假设第 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);
    }
完整的可运行的代码参这里

参考:
维基百科的《Fibonacci 数列
百度Hi空间的《奇妙的 Fibonacci 数列


Comments