斐波那契数列和斐波那契数

一、什么是斐波那契数列

 

        斐波那契数列（Fibonacci sequence），又称黄金分割数列，因数学家莱昂纳多·斐波那契（Leonardo Fibonacci）以兔子繁殖为例子而引入，故又称为“兔子数列”，指的是这样一个数列：1、1、2、3、5、8、13、21、34、……在数学上，斐波那契数列以如下被以递推的方法定义：F(0)=0，F(1)=1, F(n)=F(n - 1)+F(n - 2)（n ≥ 2，n ∈ N*）

二、求有m位的斐波那契数列

        好啦，此时我们已经知道原理了，那就很容易啦，我们可以使用集合对象ArrayList，泛型为BigInteger的集合对象来存放数列，由于斐波那契数列前两位都是1，所以我们可以把集合对象的前两位单独处理，剩下的就是一个for循环的事情啦。

        代码如下：

    //求前m位的斐波那契数列，并把他们存到ArrayList集合中
    public static ArrayList fibBuffRec (int m) {
        ArrayList fibRec = new ArrayList<>(m);
        fibRec.add(BigInteger.ONE);
        fibRec.add(BigInteger.ONE);
        for(int i = 3;i<=m;i++){
            fibRec.add(fibRec.get(i-3).add(fibRec.get(i-2)));
        }
        return fibRec;
    }

三、求第m位的斐波那契数

        那么，我为什么不先把求第m位斐波那契数放到第二个标题呢？其实这里我想说的是，如果m的值比较大的话，比如说m>40的话，如果是在比赛的话，就不建议使用以下方法，因为这样执行过程会比较慢，建议先用上面方法求出有m位的斐波那契数列，然后直接使用ArrayList.get(m)，直接获得即可，这样算法的空间度虽然说比较大，但是速度很快。如果m<40的话，就可以直接用递归的方法求第m位斐波那契数。如果m>40的话，需要等待一下才可以出结果了，读者可以自行测验呢。

        代码如下：

    //求第m位斐波那契数列的值，如果m<3直接返回1
    public static BigInteger diGui_fibBuffRec(int m){
        if(m>=3){
            return diGui_fibBuffRec(m-1).add(diGui_fibBuffRec(m-2));
        }
        else
            return BigInteger.ONE;
    }