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

一、什么是斐波那契数列

斐波那契数列（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*）

1202年，斐波那契在《计算之书（Liber Abaci）》中提出了斐波那契数列。根据该数列可折叠出斐波那契蜗牛；绘制出斐波那契螺旋线等。[3]此外，在现代物理、准晶体结构、化学等领域，该数列均有直接应用；为此，美国数学会从1963年起出版了一份名为《斐波那契数列季刊》的数学杂志，以专门刊载相关研究成果

斐波那契数列的定义者，是意大利数学家莱昂纳多·斐波那契（LeonardoFibonacci），生于公元1170年，卒于1250年，籍贯是比萨。他被人称作“比萨的莱昂纳多”。1202年，他撰写了《算盘全书》（Liber Abacci）一书。他是第一个研究了印度和阿拉伯数学理论的欧洲人。他的父亲被比萨的一家商业团体聘任为外交领事，派驻地点于阿尔及利亚地区，莱昂纳多因此得以在一个阿拉伯老师的指导下研究数学。他还曾在埃及、叙利亚、希腊、西西里和普罗旺斯等地研究数学。另外斐波那契还在计算机C语言程序题中应用广泛

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

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

        代码如下：

    //求前m位的斐波那契数列，并把他们存到ArrayList集合中
    public static ArrayList<BigInteger> fibBuffRec (int m) {
        ArrayList<BigInteger> 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;
    }

我正在参与2023腾讯技术创作特训营第三期有奖征文，组队打卡瓜分大奖！