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

简介: 【2月更文挑战第6天】


一、什么是斐波那契数列

image.png
斐波那契数列(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<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;
}

相关文章
|
3月前
|
Java C++
简单斐波那契
简单斐波那契
58 0
|
5月前
|
C语言
斐波那契数列
C 语言实例 - 斐波那契数列
41 1
|
3月前
|
C++
斐波那契数(C++)
斐波那契数(C++)
16 0
|
8月前
Fibonacci数列的多种求法
Fibonacci数列的多种求法
39 0
|
9月前
(1188:1201:)斐波那契数列
(1188:1201:)斐波那契数列
|
9月前
|
机器学习/深度学习 开发工具
斐波那契数列的四种实现
在编程教程中提到斐波那契数列,通常都是用来讲解递归函数。当一个关于 N 的问题可以转换为关于 N - k 的同样问题时,它就可以尝试用递归的思路来解决。
|
10月前
斐波那契数列问题
斐波那契数列问题
58 0
斐波那契数
斐波那契数 (通常用 F(n) 表示)形成的序列称为 斐波那契数列 。该数列由 0 和 1 开始,后面的每一项数字都是前面两项数字的和。
56 0